java集合框架主要包含Collection和Map。这里主要解析一下collection。collection主要实现包括list、set、queue。
collection中稍微说下iterator，iterator.next返回的值为值传递，即是基本数据类型为返回值，引用类型返回引用值。
下面稍微说下list、set、queue的区别：
- set：不可重复
- list：有序可重复，可通过下标随机访问
- queue：队列，FIFO
Set
不可重复，通过对象的equals()、hashCode()判断唯一性。如果对象没有重写equals()、hashCode()则默认为Object的实现即判断是否为同一个对象引用。
HashSet
HashSet是Set接口的典型实现，实现了Set接口中的所有方法，并没有添加额外的方法。
java1.8内部实现通过HashMap实现，因为HashMap可存储null值，所以HashSet也可以存储空值
private static final Object PRESENT = new Object();
public boolean add(E var1) {
return this.map.put(var1, PRESENT) == null;
}
可以看出，HashSet通过Map的Key值唯一性做为HashSet保证。
所以HashSet有以下特性：
- 无序，存储与获取时顺序可能不同
- 非线程安全
- 元素可以为null
- 判断两个元素相等的标准是两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法返回值也相等
所以根据HashMap的特性，可以有下面四个特性：
- equals()、hashCode()都为false，存储在不同位置
- equals()为true，hashCode()为false，存储在不同位置
- equals()为false，hashCode()为true，存储在相同位置，通过链表式结构来保存多个对象
- equals()、hashCode()都为true，不进行保存
LinkedHashSet
继承与HashSet，底层通过LinkedHashMap实现有序,所以其特性和LinkedHashMap保持一致，无序、非线程安全、元素可以为null、通过equals()和hashCode()判断存储对象是否已经存在
---LinkedHashSet.java
public LinkedHashSet() {
super(16, .75f, true);
}
---HashSet.java
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
TreeSet
TreeSet实现于SortedSet接口。内部实现基于TreeMap(实现NavigableMap接口)。
TreeMap解析可以参考Java 集合系列12之 TreeMap详细介绍(源码解析)和使用示例
若TreeSet没指定Comparator则存储对象必须实现Comparable接口，若指定Comparator优先使用Comparator进行排序。
- first():返回最小元素。可能throw NoSuchElementException
- last(): 返回最大元素。可能throw NoSuchElementException
- lower(E e):返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。e元素不可为空
- higher(E e):返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。e元素不可为空
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
可以看出，和HashSet一样，通过Map的Key特性保证数据"唯一性"。
TreeMap为有序的key-value集合并通过红黑树实现。因为实现了NavigableMap接口，有一系列的导航方法，比如返回有序的key集合等。因为TreeMap为非线程安全集合，所以TreeSet一样是非线程安全。
注意的是，存储在Set中数据不要修改关键比较数值，修改后并不会重新排序，而且可能造成删除不成功。
HashSet、LinkedSet、TreeSet性能比较
HashSet>LinkedSet>TreeSet
因为TreeSet有额外的红黑树操作，LinkedSet有额外的链表操作，所以性能以HashSet最高。
所以，查询较多用HashSet，有排序需求用TreeSet，插入删除较多可以考虑用LinkedSet。
List
List判断两个对象相等只要通过equals()方法比较返回true即可
ArrayList、Vector
ArrayList和Vector类都是基于数组实现的List类，封装了一个动态的、允许再分配的Object[]数组。
ArrayList为非线程安全，Vector为线程安全
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList在添加数据时，若添加完数据后的长度大于现在数据数组长度，则通过grow方法增加数组长度。新的数组长度 = 旧数组长度 + 旧数组长度/2 。
而Vector可以定义每次增长长度，不定义则新数组长度增长是翻倍。
Stack
Stack继承于Vector，通过提供API模拟LIFO模式。因为继承与Vector，若无需考虑线程安全问题可以使用LinkedList
LinkedList
实现了List<E>, Deque<E>，所以既支持随机访问也支持双端队列访问。所以可以模拟Stack操作。
内部通过链表保存数据
LinkedList的内部节点类定义
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
内部只保存了链头和链尾两个节点。所以随机存取效率较慢。而表头表尾的插入删除是指Node.next和Node.prev的指向修改，所以效率很高。
Queue
一般为FIFO操作，有时根据情况可能回使用双端队列或者循环队列
PriorityQueue/PriorityBlockingQueue
前者为非线程安全类，后者为线程安全类。可通过自然排序（实现Comparable接口）或者自定义Comparator，可以参考TreeSet
内部实现类似于ArrayList通过数组实现，且不允许插入null。
//增长数组方法
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
//自然排序时，从指定位置向上遍历调整位置
//一般为添加节点时调用
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
//自然排序时，从指定位置向下遍历调整位置
//一般用于删除节点后从0开始调整位置
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
PriorityQueue长度小于64时成倍增长，长度超过64后每次增长一半。
PriorityQueue内部数据结构主要为一棵完全二叉树，通过小顶堆方式排序元素。如果需要实现大顶堆可以通过自定义Comparator实现。
Deque接口
实现该接口为提供双端队列实现
ArrayDeque
内部由循环队列的数组实现。通过head(int)、tail(int)确定队头及队尾。
因为是非线程安全的，所以作为栈的话，效率比Stack高。因为仅是通过head(int)、tail(int)确定队头及队尾且数组天生可以随机访问，所以作为队列效率比LinkedList高。
