S04-J02 · HashMap 源码：哈希、扩容、树化与线程不安全

适用读者：背过"数组+链表+红黑树"但说不清细节的人。
前置：S04-B08、S03-B04（哈希表）。
实测环境：OpenJDK 21.0.12.1（--add-opens java.base/java.util=ALL-UNNAMED 反射读 table，2026-11-05）。
覆盖旧文：A-1670(477) A-1109(426) A-2602(454) A-2633(293) = 1,650 点。
覆盖扩展：E-S04-012（2 的幂与树化）、E-S04-013（并发死循环史）。
上一篇：S04-J01 · List 与迭代器：ArrayList/LinkedList/ArrayDeque 源码
下一篇：S04-J03 · 类文件结构与字节码。

1. 一句话结论

HashMap = 数组（桶）+ 链表 + 红黑树；容量永远是 2 的幂（用位运算代替取模），负载因子 0.75 触发扩容（翻倍）。

2. 实测：`table` 长度什么时候变

HashMap<Integer,Integer> m = new HashMap<>();
for (int i = 1; i <= 40; i++) { m.put(i, i); 打印 table.length 变化 }

实测输出：

插入 1 个后 table 长度 = 16
插入 13 个后 table 长度 = 32
插入 25 个后 table 长度 = 64

读法：

时刻	原因
第 1 次 put	延迟分配 `table`（默认 16）
第 13 次	元素数 > 阈值 `16 × 0.75 = 12` → 扩容到 32
第 25 次	`32 × 0.75 = 24` → 扩容到 64

结论：扩容发生在"超过阈值"那一次，不是"满了"才扩。

3. 为什么容量必须是 2 的幂（E-S04-012）

// 桶下标计算
index = (n - 1) & hash;        // n 是 2 的幂时，等价于 hash % n

写法	等价条件	性能
`hash % n`	任意 n	除法，较慢
`(n-1) & hash`	n 必须是 2 的幂	位运算，快

这就是"容量永远 2 的幂"的原因；HashMap 构造时会把任意容量向上取整到 2 的幂（tableSizeFor）。

扩容时的高低位拆分：容量翻倍后，每个元素只需看 hash 的新一位决定留在原位还是移到 原位置 + oldCap——不需要重新计算 hash（这是 JDK 8 的优化）。

4. 树化：链表 → 红黑树

条件	阈值
链表长度	≥ 8
数组容量	≥ 64（不足则先扩容）

为什么是 8：哈希均匀时链表长度服从泊松分布，长度到 8 的概率约 6e-8——树化是"极端情况的保险"，不是常态。

场景	结构
正常	链表（遍历短）
恶意构造冲突	红黑树（保证 O(log n)）

5. 线程不安全：两个具体后果（E-S04-013）

问题	说明
数据丢失	并发 put 可能覆盖彼此
死循环（JDK 7 及以前）	并发扩容时链表反转形成环 → CPU 100%
JDK 8 起	修复了成环（用尾插），但仍可能丢数据/读到 null

判据：并发场景用 ConcurrentHashMap（S05 详讲），不要用 Collections.synchronizedMap（全表锁，性能差）。

6. 实践速查

需求	做法
已知元素数 n	`new HashMap<>((int)(n / 0.75f) + 1)` 避免扩容
遍历时删除	`map.entrySet().removeIf(...)` 或 `Iterator`
需要顺序	`LinkedHashMap`（插入序/访问序）
需要排序	`TreeMap`（红黑树，O(log n)）
key 的 `hashCode`	必须与 `equals` 一致（否则查不到）

7. 五个误区

误区	真相
"容量随便设"	会被向上取整到 2 的幂
"满了才扩容"	超过 `容量 × 0.75` 就扩
"链表长度 8 一定树化"	还要数组容量 ≥ 64
"JDK 8 之后 HashMap 并发安全"	仍不安全（丢数据）
"`hashCode` 随便写"	与 `equals` 不一致会导致"存进去查不到"

8. 自检

实测里 table 在插入第几个元素时变成 32？为什么是那个数？
为什么容量必须是 2 的幂？扩容时怎么做到"不重算 hash"？
树化的两个条件是什么？为什么阈值是 8？
JDK 8 之后 HashMap 并发还有什么问题？
hashCode 与 equals 不一致会有什么现象？

9. 下一篇

S04-J03 · 类文件结构与字节码

集合源码读完，下一篇把视角降到"字节码"：.class 里的常量池、方法表、指令，以及为什么能反编译。

本篇属于系列《S04 · Java 语言核心》。旧文来源：A-1670/1109/2602/2633；扩展点 E-S04-012/013。table 长度变化为 OpenJDK 21 实测（需 --add-opens）。