文章目录
- 【深入源码】图解 HashMap 扰动函数：为什么要把高位“揉”进低位？
- 1. 核心矛盾：被浪费的“40亿”
- 2. 案例实战：如果不“扰动”会发生什么？
- 未经扰动的下标计算：
- 3. 扰动函数介入：h ^ (h >>> 16)
- 演示 A 的变换过程：
- 演示 B 的变换过程：
- 4. 最终对比：碰撞消失了！
- 思维误区:其实原来哈希冲突的原因就是因为低位雷同,现在h&(h>>16)就是保证高16和低16位都是原值的高位信息,导致你h&(n-1)就是用不一样的高位去取模计算索引位置了?
- 1. 修正一个小偏差：是“混合”而非“覆盖”
- 2. 为什么能减少冲突？（逻辑闭环）
- 3. 一个直观的对比
【深入源码】图解 HashMap 扰动函数：为什么要把高位“揉”进低位？
在阅读 HashMap 源码时，很多小伙伴会被(h = key.hashCode()) ^ (h >>> 16)这一行代码困惑。为什么要右移 16 位？为什么要进行异或？本文通过一个具体的案例，带你像剥洋葱一样看透这个“扰动函数”的奥秘。
1. 核心矛盾：被浪费的“40亿”
hashCode是一个 32 位的整数，范围高达 40 亿。但现实中，我们的初始数组长度往往只有 16。
在计算下标时，公式为：(n - 1) & hash。
如果数组长度为 16，计算过程只取决于最后 4 位。这意味着，即便高位有再大的差异，只要低 4 位相同，就一定会发生哈希碰撞。
2. 案例实战：如果不“扰动”会发生什么？
假设我们有两个哈希值h A h_AhA和h B h_BhB，它们的高位差异极大，但低位完全一模一样：
- h A h_AhA:
1111 0000 0000 0000 | 0000 0000 0000 0101 - h B h_BhB:
0101 0101 0101 0101 | 0000 0000 0000 0101
未经扰动的下标计算：
当n = 16时，(16 - 1)的二进制是1111。
- A 的下标:
...0101 & 1111 = 5 - B 的下标:
...0101 & 1111 = 5 - 结果:发生严重碰撞！（高位的差异被完全忽略了）
3. 扰动函数介入：h ^ (h >>> 16)
扰动函数的目的就是：让高 16 位的特征“掉下来”，混合到低 16 位中。
演示 A 的变换过程：
- 原值h A h_AhA:
1111 0000 0000 0000 | 0000 0000 0000 0101 - 右移 16 位:
0000 0000 0000 0000 | 1111 0000 0000 0000 - 异或运算:
1111 0000 0000 0000 | 0000 0000 0000 0101 (原值) ^ 0000 0000 0000 0000 | 1111 0000 0000 0000 (移位值) ------------------------------------------- 1111 0000 0000 0000 | 1111 0000 0000 0101 (扰动结果)最终 A 的低 4 位仍为0101（十进制 5）。
演示 B 的变换过程：
- 原值h B h_BhB:
0101 0101 0101 0101 | 0000 0000 0000 0101 - 右移 16 位:
0000 0000 0000 0000 | 0101 0101 0101 0101 - 异或运算:
0101 0101 0101 0101 | 0000 0000 0000 0101 (原值) ^ 0000 0000 0000 0000 | 0101 0101 0101 0101 (移位值) ------------------------------------------- 0101 0101 0101 0101 | 0101 0101 0101 0000 (扰动结果)最终 B 的低 4 位变为了0000（十进制 0）。
4. 最终对比：碰撞消失了！
| 处理方式 | A 的下标 | B 的下标 | 结果 |
|---|---|---|---|
| 直接取低位 | 5 | 5 | 碰撞！ |
| 扰动后再取 | 5 | 0 | 分流成功！ |
深度总结：
原本 A 和 B 的低 4 位完全相同。但通过右移 16 位，A 的高位特征1111和 B 的高位特征0101分别“揉”进了自己的低位。即使你的数组很小，这种机制也强制让 32 位信息中的每一位都参与了最终的下标运算。这就是利用“40亿”种可能性来减少碰撞的精髓所在。
思维误区:其实原来哈希冲突的原因就是因为低位雷同,现在h&(h>>16)就是保证高16和低16位都是原值的高位信息,导致你h&(n-1)就是用不一样的高位去取模计算索引位置了?
你已经抓住了核心逻辑，但有一个小细节需要修正：不是“都是高位信息”，而是“融合了高低位的信息”。
你的理解中有一个很棒的洞察：“用不一样的高位去计算索引位置”。没错，就是通过“借位”的思想，让本来不参与运算的高位，变相地参与了运算。
为了确保你面试时描述得绝对精准，我们把这个逻辑最后梳理一下：
1. 修正一个小偏差：是“混合”而非“覆盖”
你提到的h ^ (h >>> 16)：
- 高 16 位：因为右移后高位补 0，
h ^ 0还是原值。所以高 16 位保持不变。 - 低 16 位：变成了
原低16位 ^ 原高16位。
所以，并不是说低位变成了纯高位信息，而是低位现在承载了全 32 位的“综合特征”。
2. 为什么能减少冲突？（逻辑闭环）
- 原本的死穴：
n-1（比如 15）像是一个只看身份证最后 4 位的保安。只要最后 4 位一样，他就觉得是同一个人。 - 现在的解决办法：在过保安岗之前，我们先做一个动作——把身份证的前 16 位和后 16 位做一次异或。
- 结果：即使两个人的身份证后 4 位原本一样，但只要前 16 位有任何不同，异或后的“新后 4 位”大概率就不一样了。
3. 一个直观的对比
假设数组长度为 16（即& 1111）：
没有扰动时：
Key1:0000...0001&1111=1Key2:1111...0001&1111=1（冲突！虽然 Key2 高位全是 1，但被保安无视了）
有了扰动后：
Key1: 低位还是接近0001。Key2: 低位变成了0001 ^ 1111=1110。Key2计算索引：1110&1111=14。- 冲突解除！高位的
1111成功自救，把 Key2 送到了 14 号位置。
