怎么理解 HashMap 的扰动函数（hash 方法）是如何降低哈希冲突概率的-Java面试题-PHP中文网

扰动函数核心作用是让原始哈希值高位参与索引计算，从而均匀分布键、降低冲突；因数组长度为2的幂，(n-1)&hash仅用低比特，若hashCode低位相同则易冲突，JDK 8通过h^(h>>>16)将高位混合进低位，提升索引差异性。

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

HashMap 的扰动函数（即 hash() 方法）核心作用是**让原始哈希值的高位也参与索引计算**，从而更均匀地分散键在数组中的分布，显著降低哈希冲突概率。

为什么原始 hashCode 容易导致冲突？

Java 中对象的 hashCode() 返回的是一个 32 位 int 值，但 HashMap 底层数组长度通常是 2 的幂次方（如 16、32、64…），计算索引用的是位运算：
index = hash & (length - 1)。
这个公式只依赖 hash 的**低几位比特**。例如 length=16 → length−1=15（二进制 1111），那么只有 hash 的低 4 位决定索引位置。
如果多个 key 的 hashCode() 仅高位不同、低位相同（比如连续 Integer、String 以相似后缀结尾），它们就会映射到同一个桶，引发大量冲突——即使它们逻辑上完全不同。

扰动函数做了什么？

JDK 中典型的扰动逻辑（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 和 2112（巧合相同，实际中常见于短字符串组合）；
但更典型的是："Chat" 和 "Exit" 可能低位高度重复。
扰动后，哪怕原始 hash 仅差 1 个高位 bit，也会引起低 16 位明显变化，大幅减少“撞桶”可能。