HashMap 扩容：一条链为什么能拆成两条？
我最初理解扩容的方式很直接：数组变长，每个元素重新计算位置，再放到新数组里。这句话不算错，但“重新计算位置”很容易被说成“重新调用所有键的 hashCode”，也容易让人以为扩容之后原有碰撞都会消失。
先设一道具体问题：容量为16时，桶5里依次放着 A、B、C、D 四个节点。容量翻倍以后，为什么它们只可能去桶5或桶21？为什么不是任意一个新桶？
本文以Amazon Corretto 17.0.12，运行时17.0.12+7-LTS为准，核对本机lib/src.zip中的 HashMap 实现。讨论普通链表桶的一次16→32扩容，不把这个结论泛化到树桶、并发访问或所有Java版本。
1. 先区分三个东西
| 名称 | 本文中的含义 |
|---|---|
| 键的 hashCode | 调用key.hashCode()得到的原始int |
| 节点保存的 hash | 本版本经h ^ (h >>> 16)扰动后的int |
| 桶下标 | hash & (capacity - 1)，依赖当前容量 |
扩容改变的是容量和下标，不必改变节点保存的hash。在本文测试的迁移过程中，也不必重新调用已有键的hashCode。
这里说的“hash不变”有前提：键本身遵守hashCode与equals约定，影响这两个方法的字段不要在入表后修改。后续执行get、put查找键，仍会计算查询键的hash；不要把迁移路径的性质理解成“以后再也不会调用hashCode”。
2. 为什么只多两个选择？
设旧容量为n，且n为2的幂。旧下标是：
oldIndex = hash & (n - 1) newIndex = hash & (2*n - 1)以16为例，掩码从低4位变成低5位：
15 = 0 1111 31 = 1 1111新掩码只多保留了数值为16的那一位，其余低位没有变化。因此：
如果 (hash & n) == 0：newIndex = oldIndex 否则： newIndex = oldIndex + n注意判断的是hash & n，不是hash & (n - 1)。后者求的是旧下标，无法告诉你新增加的那一位是什么。
这不是一次新的随机分配，而是把原来未参与下标计算的一位拿出来用。对所有具有相同旧下标的节点，新下标只有原下标和原下标+n两个选择。
3. 用四个节点把这件事看清楚
让四个键的原始hashCode依次为5、21、37、53。这几个数的高16位为0，因此本版本扰动后的hash仍是它们自身。
| 键 | 保存的hash | 旧下标：hash & 15 | 新增位：hash & 16 | 新下标：hash & 31 |
|---|---|---|---|---|
| A | 5 | 5 | 0 | 5 |
| B | 21 | 5 | 16 | 21 |
| C | 37 | 5 | 0 | 5 |
| D | 53 | 5 | 16 | 21 |
旧链 A→B→C→D 被分成 A→C 和 B→D。两条新链内部保持各自在旧链中的相对顺序，但不是说整个HashMap承诺遍历顺序。
扩容也没有消除全部碰撞：A和C仍在桶5，B和D仍在桶21。扩容提供了更多桶，却不能保证每个元素独占一个桶。
4. 不只算下标：让 HashMap 真扩容一次
只改一个局部变量n=32然后打印下标，并不等于观察到了Map扩容。验证需要检查实际table的长度。
实验使用new HashMap<>(16, 0.75f)，先插入这四个键，再插入8个不与它们碰撞的填充键。普通桶只有4个节点，不触发树化相关路径。此时12条映射，table长度16，threshold为12。
然后分两步：
- 覆盖A对应的值。size仍是12，table对象不变。
- 插入第13个不同的键。size变为13，table长度变为32。
在这个普通插入场景，判断是++size > threshold，不是等于12就扩容。另一方面，严重桶碰撞也可能通过treeifyBin触发扩容，因此不能把“第13次才扩容”说成所有插入序列的必然规律。
附录程序在扩容前后读取table、threshold、next与key，同时记录键的hashCode调用次数和节点对象身份。它不是用自己实现的链表模拟HashMap。
在本机的实际输出中，关键部分为：
BEFORE size=12 capacity=16 bucket5=[A, B, C, D] AFTER size=13 capacity=32 bucket5=[A, C] bucket21=[B, D] MIGRATION: existing key hashCode calls unchanged; node identities preserved PROPERTY_SAMPLES=20080它还断言：旧数组的桶5被清空，新数组不是旧数组；迁移后的四个节点就是原来的四个对象；所有映射仍可get到。调用次数在get之前比较，因为get本身会再次调用查询键的hashCode。
5. 源码为什么要保留两条尾指针？
本版本resize的普通链表分支维护loHead、loTail、hiHead、hiTail。逐个取旧节点时，先保存next，再按(e.hash & oldCap)选择低位链或高位链，接到对应尾部。
next = e.next 新增位为0 -> 接到loTail后面 新增位非0 -> 接到hiTail后面 e = next处理完以后，将loTail.next和hiTail.next分别设为null，把两条头节点放入newTab[j]和newTab[j + oldCap]。
为什么尾部要断开？以A→B→C→D为例，C在旧链中还指着D，而D现在属于另一条新链。不清理旧连接，低位链就可能串进高位链。保存next则保证改写链路时，仍能继续遍历尚未处理的旧节点。
因此，这段实现做的不是“重新new四个节点”，而是复用普通节点、重接next，并分配一个更长的table。树桶有单独的split分支，本文没有用四节点实验验证树桶行为。
6. 验证程序本身怎么设计？
验证分成两个层次，避免只有一个漂亮输出。
实际容器断言检查扩容触发、两条链的内容和顺序、节点身份、调用次数、所有映射的可查询性。键的hash字段不可变，只有调用计数器变化，且计数器不参与equals/hashCode计算。
位运算性质测试检查10个2的幂容量，从2到1024；每个容量测试8个边界值和2000个固定种子随机int，包括负数。直接用新掩码计算下标，和“旧下标或旧下标+n”公式比较，共20080组样本。代数推导负责一般性证明，有限测试负责发现代码写错，二者不能互相替代。
另外还把公式中的新增位判断故意改成hash & (capacity - 1)，运行应失败。如果这种错误也能通过，说明测试没有覆盖真正要验证的差别。这个变异只修改我们自己的计算函数，不修改JDK。
一个顺手补上的边界：Java的%是余数运算，负数时不能直接声称hash % n等于hash & (n - 1)。例如-1 % 16是-1，而-1 & 15是15。对正的2的幂n，可对照Math.floorMod(hash, n)。
7. 怎样运行，哪些结论不要外推？
保存附录为HashResizeLab.java，在JDK17下运行：
javac -encoding UTF-8 HashResizeLab.java java --add-opens java.base/java.util=ALL-UNNAMED HashResizeLab第二条只为这次实验进程开放java.util内部字段反射访问；程序只读字段，不改写JDK内部状态，也不要把这个参数加到全局Java配置中。不带参数时，JDK17模块封装会拒绝相关反射访问。
内部字段属于实现细节，换版本需重新核对。此次实验不证明HashMap线程安全，不测试树桶，也不是性能基准。生产代码不应该依赖这些私有字段。
HashMap的公开约定不保证遍历顺序；容量和负载因子与扩容有关，但这不能替代对某个版本内部路径的核对。Java17 HashMap官方文档
我认为这次追源码最值得留下的不是“扩容翻倍”四个字，而是：先区分hash和下标，再问容量变化究竟新增了哪一位信息。这样旧下标或旧下标+n就不再是需要背下来的结论，链拆分也能从位运算自然推出来。
附录：完整验证程序
import java.lang.reflect.Field; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Random; public class HashResizeLab { static int checks; static void check(boolean ok, String message) { if (!ok) throw new AssertionError(message); checks++; } static final class Key { final String id; final int rawHash; int calls; Key(String id, int rawHash) { this.id = id; this.rawHash = rawHash; } public int hashCode() { calls++; return rawHash; } public boolean equals(Object other) { return other instanceof Key k && id.equals(k.id) && rawHash == k.rawHash; } public String toString() { return id; } } static Object field(Object target, Class<?> owner, String name) throws Exception { Field f = owner.getDeclaredField(name); f.setAccessible(true); return f.get(target); } static Object[] table(HashMap<?, ?> map) throws Exception { return (Object[]) field(map, HashMap.class, "table"); } static List<Object> nodes(Object head) throws Exception { List<Object> result = new ArrayList<>(); while (head != null) { check(head.getClass().getName().equals("java.util.HashMap$Node"), "ordinary node"); check(!result.contains(head), "no cycle"); result.add(head); head = field(head, head.getClass(), "next"); } return result; } static List<String> names(List<Object> nodes) throws Exception { List<String> result = new ArrayList<>(); for (Object node : nodes) result.add(field(node, node.getClass(), "key").toString()); return result; } static int splitIndex(int hash, int capacity) { int oldIndex = hash & (capacity - 1); return (hash & capacity) == 0 ? oldIndex : oldIndex + capacity; } public static void main(String[] args) throws Exception { System.out.println("JAVA=" + System.getProperty("java.runtime.version")); HashMap<Key, Integer> map = new HashMap<>(16, 0.75f); check(table(map) == null, "lazy allocation"); Key[] keys = {new Key("A", 5), new Key("B", 21), new Key("C", 37), new Key("D", 53)}; for (int i = 0; i < keys.length; i++) map.put(keys[i], i); int[] fillers = {1, 2, 3, 4, 6, 7, 8, 9}; for (int h : fillers) map.put(new Key("F" + h, h), h); Object[] before = table(map); check(map.size() == 12 && before.length == 16, "12 entries: capacity 16"); check((int) field(map, HashMap.class, "threshold") == 12, "threshold 12"); List<Object> oldNodes = nodes(before[5]); check(names(oldNodes).equals(List.of("A", "B", "C", "D")), "old chain"); System.out.println("BEFORE size=" + map.size() + " capacity=" + before.length + " bucket5=" + names(oldNodes)); map.put(keys[0], 100); check(map.size() == 12 && table(map) == before, "overwrite does not resize"); int[] calls = new int[4]; for (int i = 0; i < 4; i++) calls[i] = keys[i].calls; Key trigger = new Key("F10", 10); map.put(trigger, 10); Object[] after = table(map); check(map.size() == 13 && after.length == 32 && after != before, "13th entry resizes"); check((int) field(map, HashMap.class, "threshold") == 24, "threshold 24"); check(before[5] == null, "old bucket cleared"); List<Object> low = nodes(after[5]), high = nodes(after[21]); check(names(low).equals(List.of("A", "C")), "low partition preserves order"); check(names(high).equals(List.of("B", "D")), "high partition preserves order"); check(low.get(0) == oldNodes.get(0) && low.get(1) == oldNodes.get(2), "low node identity"); check(high.get(0) == oldNodes.get(1) && high.get(1) == oldNodes.get(3), "high node identity"); for (int i = 0; i < 4; i++) check(keys[i].calls == calls[i], "no hashCode call while migrating " + keys[i]); check(trigger.calls == 1, "new key hashCode called once"); System.out.println("AFTER size=" + map.size() + " capacity=" + after.length + " bucket5=" + names(low) + " bucket21=" + names(high)); System.out.println("MIGRATION: existing key hashCode calls unchanged; node identities preserved"); for (int i = 0; i < 4; i++) check(map.get(keys[i]) == (i == 0 ? 100 : i), "lookup " + keys[i]); for (int h : fillers) check(map.get(new Key("F" + h, h)) == h, "filler lookup"); check(map.get(trigger) == 10, "trigger lookup"); Random random = new Random(408); int[] edges = {Integer.MIN_VALUE, Integer.MAX_VALUE, -1, 0, 5, 21, 37, 53}; int samples = 0; for (int n = 2; n <= 1024; n <<= 1) { for (int t = 0; t < 2008; t++) { int hash = t < edges.length ? edges[t] : random.nextInt(); check(splitIndex(hash, n) == (hash & ((n << 1) - 1)), "split identity"); check((hash & (n - 1)) == Math.floorMod(hash, n), "mask vs floorMod"); samples++; } } check((-1 % 16) == -1 && (-1 & 15) == 15, "Java remainder is not floorMod"); System.out.println("PROPERTY_SAMPLES=" + samples); System.out.println("CHECKS_PASSED=" + checks); } }
