一、集合框架全景图

Java 集合框架以两个顶层接口为根：Collection（单元素）和 Map（键值对）。

1
2
3
4
5
6
7
8
9

Iterable
 └── Collection
      ├── List（有序、可重复）：ArrayList / LinkedList / Vector
      ├── Set（不可重复）：HashSet / LinkedHashSet / TreeSet
      └── Queue（队列）：ArrayDeque / PriorityQueue / LinkedList
Map（独立体系）
 ├── HashMap → LinkedHashMap（有序）
 ├── TreeMap（排序）
 └── Hashtable（遗留，勿用）

二、ArrayList：动态数组的扩容艺术

2.1 底层结构与关键字段

1
2
3
4
5
6
7

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    private static final int DEFAULT_CAPACITY = 10;  // 默认容量
    transient Object[] elementData;                  // 真正存数据的数组
    private int size;                                // 实际元素个数（≠ 数组长度）
}

注意 size 和 elementData.length 是两回事：size 是逻辑长度，数组长度是物理容量。无参构造时数组初始是空数组，第一次 add 才真正分配容量 10——这是懒加载设计。

2.2 扩容机制：为什么是 1.5 倍

1
2
3
4
5
6
7
8
9

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5 倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容流程：add → 判断容量够不够 → 不够则 grow → 新容量 = 旧容量 × 1.5 → Arrays.copyOf 整体拷贝到新数组。

1.5 倍是空间与拷贝次数的折中：扩太慢（如 1.1 倍）拷贝频繁，扩太快（如 2 倍）浪费内存。oldCapacity >> 1 用位移代替乘法，也是源码的小巧思。

2.3 modCount 与 fail-fast

ArrayList 内部维护一个 modCount（继承自 AbstractList），任何结构化修改（add/remove）都会自增。迭代器创建时会保存 expectedModCount，每次 next() 前校验：

1
2
3
4

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

三、LinkedList：双向链表的真实定位

1
2
3
4
5

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

LinkedList 是双向链表，实现了 List 和 Deque 双接口。但一个经典误区是”随机插入用 LinkedList 更快”——实际上：

中间插入时 LinkedList 先要 node(i) 走链定位，同样是 O(n)，且 CPU 缓存对连续数组极不友好。绝大多数场景 ArrayList 都优于 LinkedList；需要双端队列时用 ArrayDeque 而不是 LinkedList。

四、HashMap：源码的重头戏

4.1 put 全流程

1
2
3
4
5
6
7
8
9

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    // 扰动：高 16 位异或低 16 位
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put 一次的完整旅程：

1. 计算 hash(key)（扰动函数）；
2. 若数组为空，先 resize() 初始化；
3. (n - 1) & hash 定位桶下标——等价于 hash % n，但要求 n 是 2 的幂，位运算比取模快一个量级；
4. 桶为空 → 直接新建节点；
5. 桶非空 → 首节点 key 相同则覆盖；是 TreeNode 走红黑树插入；否则遍历链表尾插，长度达 8 且数组容量 ≥ 64 时树化；
6. ++size > threshold → resize() 扩容。

扰动函数的意义：直接用 hashCode 低位做下标，若 hashCode 只在高位有差异（如某些对象地址分布），桶会大量碰撞。h ^ (h >>> 16) 把高 16 位”混合”进低位，让散列更均匀——这是用一次异或换更低碰撞率的划算买卖。

4.2 为什么容量必须是 2 的幂

length - 1 的二进制形如 0000 1111，与 hash 相与后下标均匀落在 [0, n-1]。若长度不是 2 的幂，n-1 的二进制出现 0 位，某些下标永远取不到，散列性直接劣化。这也是为什么 tableSizeFor 会把任意初始容量向上取整到最近的 2 的幂：

1
2
3
4

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

指定 new HashMap<>(17)，实际容量会是 32。

4.3 树化：为什么阈值是 8 和 6

1
2
3

static final int TREEIFY_THRESHOLD = 8;     // 链表 → 红黑树
static final int UNTREEIFY_THRESHOLD = 6;   // 红黑树 → 链表
static final int MIN_TREEIFY_CAPACITY = 64; // 树化前提：数组容量达标

两个反直觉的点：

• 树化还需要数组容量 ≥ 64。容量小时碰撞多是因为”桶太少”而不是”散列差”，此时优先扩容而不是树化。
• 阈值 8 来源于泊松分布：在理想散列下，单桶链表长度达到 8 的概率约为千万分之六（0.00000006）。正常使用几乎触发不了树化，树化只是应对散列恶意攻击（哈希碰撞 DoS）的兜底。
• 退化阈值 6 而不是 7：留出缓冲带，防止节点数在 7、8 之间抖动导致链表/树反复转换。

4.4 扩容：JDK 8 的高低位拆分

扩容把数组翻倍，节点要么留在原下标 i，要么去 i + oldCap。判断依据只需看 hash 在 oldCap 对应位上是 0 还是 1：

1
2
3
4
5
6
7
8
9

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;
}

JDK 8 不需要重新计算每个元素的 hash，一次与运算完成分流，且链表保持原相对顺序——这是 JDK 8 相对 JDK 7 最大的性能改进之一。

4.5 JDK 7 vs JDK 8 关键差异

五、LinkedHashMap：三行代码的 LRU

LinkedHashMap 在 HashMap 的 Node 上加了 before/after 双指针，维护一条贯穿所有节点的双向链表：

1
2
3

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
}

• accessOrder = false（默认）：按插入顺序迭代；
• accessOrder = true：按访问顺序迭代，get 一次就把节点挪到链表尾。

配合 removeEldestEntry，一个 20 行的 LRU 缓存就出来了：

1
2
3
4
5
6
7
8
9
10
11
12
13

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxEntries;

    LruCache(int maxEntries) {
        super(16, 0.75f, true);          // accessOrder = true 是灵魂
        this.maxEntries = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxEntries;      // 超容量淘汰最久未访问的队头
    }
}

六、HashSet 与 TreeMap 的底层真相

HashSet 就是包装了 HashMap：

1
2
3
4
5
6

public class HashSet<E> ... {
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();  // 共享的 value 占位符

    public boolean add(E e) { return map.put(e, PRESENT) == null; }
}

所有元素作为 key 存入，value 用同一个哑对象填充。因此 LinkedHashSet = LinkedHashMap 的 key 视图，TreeSet = TreeMap 的 key 视图——一套代码三个容器。

TreeMap 底层是红黑树，按 key 排序，提供 firstKey/ceilingKey/floorKey/subMap 等范围 API。使用它要求 key 可排序：实现 Comparable 或构造时传入 Comparator，否则直接 ClassCastException。

七、集合选型速查表

八、高频避坑清单

参考阅读：并发容器（ConcurrentHashMap、CopyOnWriteArrayList、BlockingQueue）的原理与 JDK7/8 差异，见本站《Java 并发编程核心：volatile、synchronized、CAS 与 AQS 原理解析》；线程池的参数与执行流程见《Java 线程池详解》。