HashMap 的哈希扰动：为什么不是简单取模？
一句话结论（30s）
HashMap 的本质是用「位运算取代取模」的哈希表，因为容量固定为 2 的幂，所以能用 (n-1) & hash 一步定位桶；关键设计是 h ^ (h>>>16) 扰动让高位参与桶定位，扩容时用 hash & oldCap 一次位运算决定节点去留，JDK 8 改用尾插法消除 JDK 7 并发扩容的死循环。权衡：以「容量受限为 2^n」换来位运算比取模快约 5 倍，以树节点约 2 倍内存换来极端碰撞下 O(log n) 的查找保证。
核心原理（2min）
主流程：put 时先对 key 做 h ^ (h>>>16) 扰动（XOR 使输出 bit 为 1 的概率最接近 50%，分布最均匀），再用 (n-1) & hash 定位桶；碰撞时先挂链表，链表长度 ≥ 8 且数组 ≥ 64 时树化为红黑树。扩容时容量翻倍，用 hash & oldCap 判断多出的那一个 bit：为 0 留原下标、为 1 偏移 oldCap，用 lo/hi 双链表尾插迁移，一次位运算 O(1) 决策、O(n) 迁移。树化阈值 8 是泊松分布（λ=0.5）下几乎不可能触发的防御信号，退树化阈值 6 而非 8 是为了避免 resize 引起的「树化↔链化」振荡。读到这先别急着往下背结论，自己回答三个问题：扰动函数为什么偏偏是高 16 位异或低 16 位，而不是别的位？容量为什么非得是 2 的幂？这两点如果做不到，get 会慢多少、甚至会不会出错？带着答案继续读，后面的每一节其实都在回答其中之一。
底层深入（5-10min）
一个看似简单的问题
HashMap 的容量是 2 的幂（如 16、32、64），用 (n-1) & hash 定位桶。问题是：(n-1) 的二进制全是低位的 1（如 n=16 时掩码 0b1111），如果 key 的 hashCode 高位差异大但低位相同，直接取模会让它们全落在同一个桶——本来该是 O(1) 的散列查找，直接退化成了对整条链表的线性遍历。先停下来想想：怎么才能让「低位掩码看不到」的高位也参与定位？
这就是”扰动函数”存在的理由——让高位信息也参与桶定位。
JDK 8 的扰动函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}核心操作：将 hashCode 的高 16 位与低 16 位做 XOR，结果存入低 16 位。
为什么是 XOR 而非 AND 或 OR？
| 运算 | 输出 1 的概率 | 问题 |
|---|---|---|
| AND | 25% | 偏向 0，分布不均 |
| OR | 75% | 偏向 1，分布不均 |
| XOR | 50% | 均衡分布 ✅ |
XOR 让高低位信息均匀混合，输出 bit 为 1 的概率最接近 50%，保证桶分布最均匀。
举个例子
hashCode = 0b0001_0010_0011_0100_0101_0110_0111_1000
高16位 = 0b0001_0010_0011_0100
低16位 = 0b0101_0110_0111_1000
h >>> 16 = 0b0000_0000_0000_0000_0001_0010_0011_0100
h = 0b0001_0010_0011_0100_0101_0110_0111_1000
XOR = 0b0001_0010_0011_0100_0100_0100_0100_1100现在低 16 位包含了两部分的信息，(n-1) & hash 使用的掩码能”看到”高位差异。
putVal：定位、覆盖、树化的完整流程
扰动后的 hash 最终交给 putVal 落地，完整实现如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}这段代码把写入拆成三个分支：桶为空时直接新建节点；桶首节点命中（hash 相同且 equals 相等）则走覆盖分支；否则沿链表向后找，找不到就尾插新节点，插入后若 binCount >= TREEIFY_THRESHOLD - 1（即链表里已有 8 个节点）就调用 treeifyBin 尝试树化。注意每处命中判断都是「先 p.hash == hash 快速筛，再 key.equals(k) 精确比」，这正是 hash 与 equals 分两步协作在写路径上的体现。
容量为什么是 2 的幂：tableSizeFor
(n-1) & hash 能当取模用，前提是容量 n 永远是 2 的幂。那为什么不干脆用任意容量、老老实实 hash % n 取模？想想看：只要 n 不是 2 的幂，n-1 的二进制里就会出现 0，掩码会漏掉一部分桶，散列立刻不均——所以「容量必须是 2 的幂」不是洁癖，而是位运算正确性的硬前提。这个前提靠 tableSizeFor 在构造时对齐：
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}numberOfLeadingZeros 算出 cap - 1 最高位 1 的位置，-1 >>> ... 据此生成一个低 k 位全 1 的掩码，再加 1 就得到恰好 >= cap 的 2 的幂。所以无论你传初始容量 17 还是 30，HashMap 都会把它对齐成 32；这就是「容量永远是 2 的幂」的机制来源（JDK 8 用的是逐步右移填充高位的写法，现行 JDK 用 numberOfLeadingZeros 直接算出，效果相同——向上取整到最近的 2 的幂）。
扩容：hash & oldCap 的魔法
HashMap 扩容时容量翻倍（newCap = oldCap * 2），但不需要重新计算每个 key 的 hash。先想一个问题：为什么必须翻倍，不能 +1 或 ×3？因为翻倍后新掩码 newCap - 1 只比旧掩码多出最高位那个 1，而这个多出的 bit 恰好就是 oldCap——正是这个巧合，才让下面「一次位运算决定去向」的捷径成立。JDK 8 用 hash & oldCap 一次位运算判断节点去向：
// 扩容时拆分链表的核心逻辑
if ((e.hash & oldCap) == 0) {
// 该 bit = 0 → 下标不变 → 加入 lo 链表
} else {
// 该 bit = 1 → 下标偏移 oldCap → 加入 hi 链表
}为什么这样是对的？
扩容前 n = 16 = 0b10000，n-1 = 0b01111。扩容后 n = 32 = 0b100000，n-1 = 0b11111。
原来掩码是 4 bit，现在是 5 bit，多出的第 5 bit 恰好就是 oldCap（16 = 0b10000）。所以 hash & oldCap 就是检查”hash 中这个新增 bit 的值”：
- 该 bit = 0 → 新下标 = 旧下标
- 该 bit = 1 → 新下标 = 旧下标 + oldCap
一次位运算，O(1) 决策，O(n) 迁移。
resize() 的真实实现
hash & oldCap 的决策逻辑就藏在 resize() 的迁移循环里，完整代码如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
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 {
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;
}
}
}
}
}
return newTab;
}这段代码先算新容量 newCap（旧容量翻倍，超过 MAXIMUM_CAPACITY 则不再扩）和新阈值 newThr，再遍历旧表把节点搬到新表。单个节点直接按 newCap - 1 重新定位，树节点走 split 拆分，普通链表则用 hash & oldCap 把每个节点归入 lo/hi 两条链，lo 接到原下标 j、hi 接到 j + oldCap；由于 next 在改指针前先保存、尾插时只动 tail.next，链表相对顺序保持不变——这正是 JDK 8 消除 JDK 7 头插死循环的那段代码。
树化：为什么是 8？
static final int TREEIFY_THRESHOLD = 8;链表转红黑树不是只看长度 ≥ 8，还要 MIN_TREEIFY_CAPACITY = 64（数组长度 ≥ 64）。
为什么是 8？JDK 注释给出了数学解释：在理想哈希分布下（泊松分布，λ = 0.5），链表长度达到 8 的概率约为 0.00000006（6 × 10⁻⁸），几乎不可能。所以链表 ≥ 8 本身就是”哈希分布异常”的信号，树化是一种防御措施。
树化后查找从 O(n) 变为 O(log n)，但树节点占用空间约是普通节点的 2 倍，所以添加了”数组长度 ≥ 64”的前提——小表直接扩容就够了，不必树化。
这个「先扩容、够大才树化」的判断就写在 treeifyBin 里：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}第一行的 if 就是那层防御：表还没建或长度 < MIN_TREEIFY_CAPACITY（64）时不树化，而是直接 resize 扩容。只有当数组够大、且这个桶确实还是长链表时，才把链上的每个 Node 逐个替换成 TreeNode、用 prev/next 串成双向链表，最后调用 hd.treeify(tab) 真正构造成红黑树。
退树化：为什么是 6 而不是 8？
static final int UNTREEIFY_THRESHOLD = 6;用不同值（8 和 6）作为树化和退树化阈值，避免因反复 resize 导致的”树化 ↔ 链化”振荡（一个 put 让长度到 8 触发树化，一个 remove 让长度到 7 又退树化，如此反复）。
JDK 7 vs JDK 8：头插法为什么会死循环
JDK 7 扩容时用头插法（新节点插入链表头部），并发扩容时两个线程同时迁移链表，next 指针交叉修改形成 A→B→A 循环引用，get() 进入死循环，CPU 飙高。
JDK 8 改用尾插法 + lo/hi 双链表：遍历时用尾插将节点追加到 loHead → loTail 或 hiHead → hiTail，链表内相对顺序保持不变，彻底消除循环引用。
// JDK 8 尾插法（简化）
if (loTail == null)
loHead = e;
else
loTail.next = e; // 尾部追加，顺序不变
loTail = e;
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;扩容完成后分别将 loHead 接到 newTab[j]，hiHead 接到 newTab[j + oldCap]。
总结：HashMap 设计中的工程权衡
| 设计 | 机制 | 代价 | 收益 |
|---|---|---|---|
| 扰动函数 | h ^ (h >>> 16) | 一次位运算 | 分布均匀度大幅提升 |
| 2 的幂容量 | (n-1) & hash | 容量受限为 2^n | 位运算替代取模（快 ~5 倍） |
| 尾插法 | lo/hi 双链表 | 额外头尾指针 | 消除 JDK 7 死循环 |
| 树化 | 链表 → 红黑树 | 树节点内存 ×2 | 极端哈希碰撞下 O(log n) 保证 |
章末提问
-
为什么 JDK 8 要把头插法改成尾插法？ 结论：为了消除并发扩容的死循环。因为头插法在并发迁移时两个线程会交叉改写 next 指针，形成 A→B→A 循环引用，get 进去就死循环；尾插法保持链表相对顺序，配合 lo/hi 双链表后链表不会成环。
-
扩容为什么要 2 倍，不能 3 倍或随便加一个数？ 结论：为了把「重算下标」降成一次位运算。因为翻倍后新掩码
newCap - 1只比旧掩码多最高位一个 1，这个 bit 恰好等于 oldCap，用hash & oldCap就能 O(1) 决定节点去留；其他扩容因子都没有这种对称性。 -
扰动函数为什么是高 16 位异或低 16 位，而不是别的位？ 结论：为了让高位参与桶定位、分布更均匀。因为
(n-1) & hash只取低 log n 位，高位不参与时，高位差异大、低位相同的 key 会全部碰撞；XOR 混合后输出 1 的概率最接近 50%，分布最均匀。 -
为什么树化阈值是 8，而不是 2 或 100？ 结论：8 是「哈希分布异常」的防御信号。因为在理想泊松分布（λ=0.5）下链表达到 8 的概率约 6×10⁻⁸，几乎不可能，一旦出现说明 hash 质量出问题；又因树节点内存约 2 倍，所以还要求数组 ≥ 64 才树化。
-
为什么不直接用
hash % n取模，偏要(n-1) & hash？ 结论：位运算比取模快。因为容量固定为 2 的幂时两者结果等价，而位与指令比取模快约 5 倍；代价是容量被限制为 2^n，用 tableSizeFor 对齐兜底。