怎么理解 HashMap 的扰动函数（hash 方法）是如何降低哈希冲突概率的

先明确一点：HashMap 的扰动函数——也就是那个我们经常在源码里看到的 hash() 方法——它的根本目的，是让原始哈希值的“高位”也能参与到最终的索引计算中。为什么要这么做？很简单，就是为了让键的分布更均匀，从而有效降低哈希冲突的概率。这个设计思路，说起来并不复杂，但背后其实藏着不少细节。

为什么原始 hashCode 容易“撞车”？

Ja va 里每个对象都有 hashCode() 方法，返回的是一个 32 位的 int 值。但问题在于，HashMap 底层数组的长度，通常被设计为 2 的幂次方，比如 16、32、64 这种。计算索引的时候，用的位运算是这么写的：
index = hash & (length - 1)。

这个公式只依赖 hash 的**低几位比特**。举个例子，如果数组长度是 16，那么 length - 1 就等于 15，二进制是 1111。换句话说，只有 hash 值的低 4 位决定了元素最终落在哪个桶里。

想象一下，假如有多个 key，它们的 hashCode() 只有高位不同、低位完全一样——比如一些连续的 Integer 对象，或者以相同后缀结尾的 String。那么无论它们在高位上差异多大，最终都会被映射到同一个桶里。逻辑上完全不同的 key，却因为低位相同而挤在一起，大量冲突就这么产生了。这在某些场景下，几乎是灾难性的。

扰动函数是怎么做的？

JDK 8 里的具体实现，代码非常简洁：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

逻辑很清楚：把原始 hash 值右移 16 位，然后和自身做异或（XOR）。这个操作的本质，就是把高 16 位的特征“混合”进低 16 位里。

这个设计带来了两个关键效果：

• 放大差异性——原来高位不同、低位相同的两个 hash，经过扰动之后，低 16 位很可能就变得不一样了，最终算出的索引自然也就不同。
• 保留低位主导，同时引入高位信息——异或运算本身不会丢失信息，分布性也相当好。而且它没有破坏位运算的高效性，hash & (length-1) 依然能快速计算。

一个直观的例子

举个很典型的例子：假设有两个字符串 "Aa" 和 "BB"，它们的 hashCode() 值碰巧都是 2112（这种巧合在短字符串组合里其实并不少见）。如果不做扰动，这两个 key 会毫无悬念地落在同一个桶里。但经过 hash() 方法处理后，哪怕原始哈希值在高 16 位上仅仅差一个 bit，也会引起低 16 位发生明显变化，从而大大降低“撞桶”的可能性。

不是万能，但确实有效

当然，扰动函数并不能消除所有冲突——哈希本身就是一种压缩映射，冲突在数学上是必然存在的。但它的价值在于，把原本可能“集中轰炸”在少数几个桶上的冲突，变成了“相对均匀地散布”在整个数组上。再配合负载因子 0.75 的自动扩容机制，以及链表转红黑树的降级策略，HashMap 的平均查找复杂度依然能保持在 O(1) 附近。从这个角度看，扰动函数是空间换时间、简单换鲁棒性的一个经典权衡。