HashMap 中 `hash` 与数组索引的计算原理

在 Java 8 的 HashMap 中，下面两段代码非常关键：

(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

(n - 1) & hash

第一段负责把 key 转成更适合散列的 hash，第二段负责把 hash 映射成数组下标。它们组合起来，决定了元素会被放进哪个桶。

一、`hash` 的计算方式

先看第一段：

(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

这段代码的意思是：

如果 key == null，直接返回 0
如果 key != null，先取出 key.hashCode()
再把原始哈希值和它右移 16 位后的结果做一次异或运算

拆开后更容易理解：

int h;
if (key == null) {
    return 0;
}
h = key.hashCode();
return h ^ (h >>> 16);

1. 为什么 `null` 的哈希值是 `0`

HashMap 允许 null 作为 key，但 null 无法调用 hashCode()，所以实现里直接约定：

null -> hash = 0

这不是数学规则，而是 HashMap 的实现约定。

2. 为什么不直接用 `key.hashCode()`

很多人会以为拿到 hashCode() 就够了，但 HashMap 后面在计算数组下标时，并不会完整使用整个 32 位整数，而是主要依赖低位。

如果很多对象的 hashCode() 在低位上很接近，但高位不同，那么它们最终可能还是会落到同一个桶里，导致冲突增加。

例如下面两个哈希值：

h1 = 0x12340001
h2 = 0x56780001

它们的低 16 位都是 0x0001。如果后续只依赖低位来定位桶，那么这两个值很可能发生碰撞。

3. `h ^ (h >>> 16)` 到底做了什么

这一步通常被称为“扰动函数”或“位混合”。

h >>> 16

表示把 h 无符号右移 16 位。这样原本的高 16 位就被移动到了低 16 位区域。

然后再执行：

h ^ (h >>> 16)

也就是原始值与右移后的值做异或。结果就是：

原始低位的信息还在
原始高位的信息也被折叠进了低位
最终低位不再只表示“原来的低位”，而是同时受高位影响

这就是常说的“高位异或低位”。

一篇讲清楚移位和异或

4. 为什么这样能减少碰撞

因为后续数组索引计算主要看低位，所以必须尽量让低位也携带高位信息。

如果不做扰动，那么某些 hashCode() 虽然整体不同，但只要低几位相同，就很容易映射到同一个桶。

做了扰动之后：

原本只有高位不同的哈希值
现在连低位也会变得不同
桶分布更均匀

注意，这里更准确的说法是：

它不是“消除碰撞”，而是“减少因为低位分布不佳导致的碰撞”。

5. 一个简单例子

假设有两个原始哈希值：

h1 = 0x12340001
h2 = 0x56780001

做扰动后：

h1 ^ (h1 >>> 16)
h2 ^ (h2 >>> 16)

由于：

h1 的高 16 位是 0x1234
h2 的高 16 位是 0x5678

这些高位信息被混入低位后，最终参与下标计算的低位部分就更可能不同，从而降低落入同一桶的概率。

二、数组索引的计算方式

再看第二段：

(n - 1) & hash

这里的目的，是把一个整数 hash 映射到数组下标范围：

[0, n - 1]

1. 为什么不用 `%`

最直观的写法通常是：

hash % n

但 HashMap 没这么做，而是使用位运算：

(n - 1) & hash

原因有两个：

位运算比取模更快
在数组长度满足特定条件时，两者结果等价

2. 这个等价关系的前提

前提是：

n 必须是 2 的幂

例如：

16
32
64
128

这也是为什么 HashMap 的容量总是尽量保持为 2 的幂。

3. 为什么 `n - 1` 可以替代 `% n`

假设：

n = 16

那么：

n - 1 = 15

转成二进制：

16  = 00010000
15  = 00001111

此时执行：

hash & 15

本质上就是只保留 hash 的低 4 位。

而任意一个数对 16 取模，结果也正好只取决于低 4 位，因此：

hash % 16 == hash & 15

4. 例子说明

例如：

hash = 27

那么：

27 % 16 = 11
27 & 15 = 11

看二进制更直观：

27 = 00011011
15 = 00001111
----------------
&  = 00001011

结果就是 11。

所以在 n 为 2 的幂时：

(n - 1) & hash

既能达到取模的效果，又比 % 更高效。

三、这两段代码是怎么配合的

HashMap 放入元素时，核心路径可以简化成三步：

1. key.hashCode()         // 先拿到原始哈希值
2. h ^ (h >>> 16)         // 扰动，让高位参与低位
3. (n - 1) & hash         // 映射成数组下标

这里最关键的逻辑链路是：

下标计算主要依赖低位
所以低位的分布必须尽量均匀
如果原始 hashCode() 的高位很有区分度、低位却很差，就会产生大量冲突
因此要先把高位信息混入低位
然后再用位运算快速定位桶下标

这就是这两段代码组合设计的本质。

四、常见误区

1. 扰动函数不是强哈希算法

h ^ (h >>> 16) 只是一次轻量级混合，不是密码学意义上的哈希增强。

它的目标不是“制造绝对均匀的散列”，而是：

成本低
足够快
能改善低位分布

如果某个类的 hashCode() 本身实现非常差，比如大量对象返回相同值，那么这一步也无法彻底解决问题。

2. 位运算替代取模不是无条件成立

只有当数组长度 n 是 2 的幂时：

(n - 1) & hash

才能等价于：

hash % n

如果 n 不是 2 的幂，这种写法就不能保证分布正确。

五、总结

HashMap 的这两个公式分别解决了两个问题：

1. `hash` 如何更均匀

(h = key.hashCode()) ^ (h >>> 16)

作用是把高位信息折叠到低位，减少因为低位重复而导致的哈希冲突。

2. 如何快速算出桶下标

(n - 1) & hash

作用是在数组长度为 2 的幂时，用位运算代替取模，快速得到桶索引。

最终你可以把它们概括成一句话：

先通过扰动函数让 hash 的低位更有区分度，再利用 2 的幂容量和位运算高效定位数组下标。

这也是 Java 8 HashMap 在性能和散列分布之间做出的一个非常经典的工程化权衡。