集合框架深入

Java 中级 · Java 进阶

初级我们用集合「存东西」，中级要搞清楚它为什么快、什么时候会退化、并发下为什么出事。集合是面试与生产事故的第一高发区（HashMap 死循环、ConcurrentModificationException、并发写丢数据），根源都在底层数据结构与扩容/并发策略。本篇把 JDK 8 之后的实现讲透。

一、HashMap 的底层结构与哈希定位

1.1 数据结构：数组 + 链表 + 红黑树

JDK 8 的 HashMap 内部是一个 Node<K,V>[] table 数组，每个槽位（桶，bucket）挂一条链表；当单桶链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转成红黑树，把最坏查找从 O(n) 降到 O(log n)。

1.2 哈希为什么这么算

static final int hash(Object key) {
    int h;
    // 高 16 位异或低 16 位：让高位也参与运算，减少低位相同的 key 撞车
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 定位桶：n 是 2 的幂，(n-1) & hash 等价于 hash % n，但位运算更快
int index = (n - 1) & hash;

三个关键点：

1. 扰动函数：h ^ (h >>> 16) 把高位的随机性「折叠」到低位。因为 (n-1) & hash 只用到低位，若不做扰动，高位差异会被直接丢弃。
2. 数组长度必须是 2 的幂：这样 (n-1) 的二进制是「低位全 1」，(n-1) & hash 才能均匀映射且等于取模。
3. 初始容量：默认 16，负载因子 0.75。0.75 是空间与冲突概率的经验折中点——太高冲突多，太低浪费空间。

1.3 put 的执行流程（JDK 8）

1.4 扩容（resize）的巧妙之处

扩容时容量翻倍。JDK 8 不像 JDK 7 那样重新计算每个节点的 hash，而是利用容量是 2 的幂这个性质：

// 旧容量 oldCap 的二进制只有一位是 1（如 16 = 0001 0000）
// 迁移时只看 hash 在 oldCap 这一位上是 0 还是 1
// 0 → 留在原索引 j；1 → 移动到 j + oldCap
if ((e.hash & oldCap) == 0) { /* 低位链 loHead */ }
else                        { /* 高位链 hiHead → 原索引 + oldCap */ }

一次位运算就能判断新位置，避免重新散列，这是 JDK 8 的性能关键优化。

JDK 7 扩容死循环（经典事故）

JDK 7 用头插法，并发扩容时链表可能被反转成环，之后 get 一个不存在的 key 会CPU 100% 死循环。JDK 8 改为尾插法消除了成环，但多线程 put 仍会丢数据——所以并发场景必须用 ConcurrentHashMap，而不是指望 HashMap 别再出 bug。

二、ConcurrentHashMap：并发下的正确选择

JDK 7 用「分段锁 Segment」；JDK 8 改为 CAS + synchronized(桶头节点)，锁粒度细化到单个桶，并发度大幅提升。

关注点	JDK 7	JDK 8
锁粒度	Segment（默认 16 段）	单个桶头节点 synchronized
空桶插入	加锁	CAS 无锁插入
统计 size	多次尝试 + 加锁	baseCount + CounterCell[] 分治计数
扩容	段内独立	多线程协同迁移（ForwardingNode 转发）

// 空桶：CAS 插入，失败则自旋重试
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break;
// 非空桶：synchronized 锁住头节点后再遍历插入
synchronized (f) { /* 链表 or 红黑树插入 */ }

• get 完全无锁：table 元素用 volatile 语义读写，保证可见性。
• 扩容协助迁移：迁移时旧桶放 ForwardingNode，其它线程发现后一边 get 转发到新表、一边帮忙迁移。
• size 是弱一致：size() 返回的是估算值（sumCount()），并发下不保证精确。

不允许 null

ConcurrentHashMap 的 key 和 value 都不允许 null。因为并发下无法区分「key 不存在」与「value 为空」，会引入歧义。

三、fail-fast 与 fail-safe

fail-fast（快速失败）：ArrayList、HashMap 等普通集合在迭代过程中被结构性修改（增删），会立刻抛 ConcurrentModificationException。

// 原理：内部维护 modCount，每次结构性修改 ++
// 迭代器创建时记录 expectedModCount = modCount
// next() 时校验 if (modCount != expectedModCount) throw CME
for (String s : list) {
    if (s.equals("a")) list.remove(s); // 抛 ConcurrentModificationException
}

正确删除方式：

// 方式一：迭代器自己的 remove
Iterator<String> it = list.iterator();
while (it.hasNext()) if (it.next().equals("a")) it.remove();
// 方式二：JDK 8 removeIf
list.removeIf(s -> s.equals("a"));
// 方式三：并发集合
List<String> safe = new CopyOnWriteArrayList<>(list); // 写时复制，弱一致

fail-safe（安全失败）：CopyOnWriteArrayList、ConcurrentHashMap 的迭代器基于快照，迭代期间的修改不影响本次遍历，不抛异常，代价是看不到最新数据（弱一致性）。

集合	迭代器	特点
ArrayList / HashMap	fail-fast	并发修改抛 CME
CopyOnWriteArrayList	fail-safe	写时复制，读多写少
ConcurrentHashMap	fail-safe（弱一致）	无锁读，不抛 CME

四、List/Set/Map 选型速查

需求	选择	底层
随机访问多、尾部增删	ArrayList	动态数组（1.5 倍扩容）
头尾频繁增删	ArrayDeque	循环数组（优于 LinkedList）
去重 + 不要求顺序	HashSet	基于 HashMap
去重 + 保持插入顺序	LinkedHashSet	哈希 + 双向链表
排序集合	TreeSet / TreeMap	红黑树
高并发读写	ConcurrentHashMap	CAS + synchronized

五、最佳实践

• 预估容量：new HashMap<>(预计元素数 / 0.75 + 1)，避免反复扩容（putAll 前尤其重要）。
• key 用不可变对象：String、Integer 最安全；自定义对象必须正确实现 equals/hashCode。
• 并发写一律用并发集合，别在普通集合外面套 Collections.synchronizedMap 后还复合操作（check-then-act 仍不安全）。
• 遍历时删除用迭代器 / removeIf，不要用增强 for + list.remove。
• 排序用 TreeMap，或先 ArrayList 再 Collections.sort，别在循环里反复 sort。

📚 官方文档与参考资料

• Java SE 21 · java.util 包
• Java 教程 · Collections
• HashMap 源码（OpenJDK）
• ConcurrentHashMap 源码（OpenJDK）

✏️ 练习与自测

1. 为什么 HashMap 的容量必须是 2 的幂？如果传入 new HashMap<>(17) 实际容量是多少？（提示：看 tableSizeFor）
2. 手写一段代码，用 ConcurrentHashMap 实现一个线程安全的计数器，并说明为什么 size() 在并发下可能不准。
3. modCount 的作用是什么？为什么用增强 for 遍历时调用 list.remove() 会抛异常，而 it.remove() 不会？
4. 解释 JDK 7 HashMap 并发扩容「成环」的原因，以及 JDK 8 为什么不会成环但仍不安全。

本节小结

集合深入的三个核心：HashMap 用扰动 + 位运算做哈希定位、扩容靠 (hash & oldCap) 判断去留、链表长 8 且表长 64 才树化；并发场景一律用 ConcurrentHashMap（CAS + 桶级 synchronized）；fail-fast 靠 modCount 校验，fail-safe 靠快照。理解这些，才能解释「为什么快」和「为什么并发会出事」。