1 List
1.1 ArrayList
基于数组实现，按照插入顺序排序，可重复，线程不安全，默认初始化为空数组对象，在添加第一个元素时，初始化大小为10的数组。支持自动扩容，扩展因子为0.5，即 newCapacity=oldCapacity*1.5，扩容方式是 Arrays.copyOf(elementData, newCapacity);。
1.2 Vector
基于数组实现，按照插入顺序排序，可重复，通过 synchronized 来保证线程安全，默认初始化大小为10的数组。添加元素时。支持自动扩容，扩展因子为1，即 newCapacity=oldCapacity*2，扩容方式是 Arrays.copyOf(elementData, newCapacity);。
1.3 LinkedList
基于双向链表实现，按照插入顺序排序，实现了接口 Deque，所以它也是一个双端队列。
// 双端链表结构
private static class Node<E> {
E item; Node<E> next; Node<E> prev;
}
2 Map
2.1 HashMap
基于散列链表+红黑树实现，无序，链表长度>=8时转为红黑树，红黑树<=6时转为链表，首次添加元素时，初始化默认数组长度16，并且必须是2的幂次方大小，当指定的大小不够2的幂次方时自动补齐大小，默认加载因子0.75，默认扩展因子1，线程不安全。
// 散列链表结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 数组索引
final K key;
V value;
Node<K,V> next; // 下一个节点
}
// 红黑树结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
}
添加元素时为了更均匀地分布，对 key 进行两次的 hash 运算。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
扩容方式：resize()，扩容后的容量是之前的2倍。
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 索引没有变化
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 索引变为原索引+oldCap
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
线程安全性问题
1、put 导致数据丢失；
2、resize 导致的 get 操作时的死循环，JDK 8 已经解决此问题，利用 head 和 tail 来保证链表的顺序不变，避免导致死循环；
2.2 HashTable
基于散列链表实现，默认数组长度11，默认加载因子0.75，默认扩展2原数组长度+1，利用 synchronized 保证线程安全*。
2.3 TreeMap
基于红黑树实现，按 key 自然排序。key 不等于 null。
2.4 LinkedHashMap
利用 HashMap 来实现。散列双向链表的结构。
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
}
accessOrder 的排序方式：
- accessOrder=false（默认）表示按插入顺序排序
- accessOrder=true表示按访问顺序排序(最少被访问的靠前，最近访问的靠后)，可用于实现LRU算法（Least recently used，最近最少使用算法）
3 Set
3.1 HashSet
利用 HashMap 实现，无序，去重，默认初始化为默认的 HashMap，value 固定为 Object 对象，可以参考 HashMap 的实现。
// 初始化
public HashSet() {
map = new HashMap<>();
}
// 添加元素
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
3.2 TreeSet
利用 TreeMap 实现，自然排序，去重，不能添加 null，默认初始化为默认的 TreeMap，value 固定为 Object 对象，可以参考 TreeMap 的实现。
3.3 LinkedHashSet
继承了 HashSet，利用 LinkedHashMap 实现，可以参考 LinkedHashMap 的实现。
4 Stack
栈的结构，继承了 Vector 类，利用 synchronized 来保证线程安全。
5 Queue / Deque
队列 / 双端队列的结构，Deque 继承 Queue 接口。
常见实现：
- PriorityQueue，优先队列，默认初始化长度为 11，通过二叉小顶堆实现，保证每次取出值最小的元素。
- ArrayDeque，数组实现的双端队列，默认初始化长度为 16，FIFO 原则。
- LinkedList
- BlockingQueue，阻塞队列，详见《并发集合包》。
