HashMap 的 hash 方法是如何实现的？

面试考察点

1. 源码掌握：面试官不仅仅是想知道 "有个 hash 方法" 这个事实，更是想知道你是否读过源码，是否理解 (h = key.hashCode()) ^ (h >>> 16) 这行代码的精妙之处。

2. 位运算理解：考察你是否理解无符号右移 >>> 和异或 ^ 的作用，以及为什么这样设计能减少哈希冲突。

3. 设计思想：是否理解 "扰动函数" 的概念，以及高位参与运算对散列均匀性的影响。

核心答案

HashMap 的 hash() 方法通过 "扰动函数" 将 key 的 hashCode() 高 16 位与低 16 位异或，让高位信息参与散列运算：

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

关键点	说明
null 处理	key 为 null 时返回 0（HashMap 允许 null key）
扰动算法	hashCode ^ (hashCode >>> 16)
目的	让高位参与运算，减少哈希冲突
效果	散列更均匀，冲突概率降低

一句话总结：hash 方法通过 高 16 位异或低 16 位 的扰动算法，让散列值更均匀，减少冲突。

深度解析

一、源码逐行解析

static final int hash(Object key) {
    int h;
    // 1. key 为 null，返回 0（HashMap 支持 null key）
    // 2. key 不为 null，计算 hashCode 并扰动
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

逐行解析：

• key == null ? 0：HashMap 允许一个 null 键，null 的 hash 值固定为 0，所以 null 键总是放在桶 0 的位置。

• h = key.hashCode()：先调用 key 对象的 hashCode() 方法获取原始哈希值。

• h >>> 16：将 hashCode 无符号右移 16 位，取出高 16 位。

• ^ 异或操作：将高 16 位与原 hashCode 异或，得到扰动后的哈希值。

二、为什么要扰动？

上图解释了扰动函数的核心价值。关键理解：

• 问题根源：桶索引只用到 hashCode 的低位，高位信息被浪费
• 扰动作用：将高位信息 "混合" 到低位，让低位也包含高位的特征
• 效果：原本高位不同但低位相同的 key，扰动后低位也变得不同，减少冲突

三、扰动过程图解

上图详细展示了扰动函数的执行过程。关键点：

• 异或特性：相同为 0，不同为 1。高 16 位与自己异或保持不变，低 16 位与高 16 位异或产生变化。

• 只扰动一次：为什么不是多次扰动？一次扰动已经足够，多次扰动反而可能增加计算开销。

• 低 16 位变化：低 16 位融合了高 16 位的信息，即使两个 hashCode 低位相同，只要高位不同，扰动后低位也会不同。

四、为什么用异或而不是与/或？

上图解释了为什么选择异或运算。核心原因：

• 与运算：偏向 0，散列不均匀
• 或运算：偏向 1，散列不均匀
• 异或运算：0 和 1 概率相等，散列最均匀

五、与桶定位的关系

面试高频追问

1. 为什么只右移 16 位？不是 8 位或 24 位？

   • 32 位整数，右移 16 位正好是高低位对半
   • 既能利用高位信息，又不会过度破坏低位原始特征
   • 实践证明效果最佳

2. JDK 1.7 和 1.8 的 hash 方法有区别吗？

   • 有！JDK 1.7 扰动了 4 次（多次移位异或）
   • JDK 1.8 简化为 1 次，性能更好，效果相当

3. 扰动函数能完全避免冲突吗？

   • 不能！只能减少冲突概率
   • 完全避免冲突需要完美哈希函数，实际不存在

4. 为什么用 >>> 无符号右移而不是 >> 有符号右移？

   • >>> 高位补 0，>> 高位补符号位
   • hashCode 可能为负数，用 >> 会引入符号位干扰
   • 用 >>> 保证高位始终补 0，扰动更纯净

常见面试变体

• "HashMap 如何计算 key 的哈希值？"
• "为什么 HashMap 要对 hashCode 进行扰动？"
• "HashMap 的 hash 方法为什么用异或？"

记忆口诀

扰动公式：hash = hashCode ^ (hashCode >>> 16)

作用：高位异或低位，让高位信息参与散列，减少冲突。

null 处理：key 为 null 返回 0，统一放桶 0。

总结

HashMap 的 hash() 方法通过 hashCode ^ (hashCode >>> 16) 扰动算法，将高 16 位与低 16 位异或，让高位信息参与散列运算。这是因为桶索引只用到低位，扰动可以让高位原本不同但低位相同的 key 散列到不同桶，减少冲突。选择异或是因为它产生 0 和 1 的概率相等，散列最均匀。null 键的 hash 固定为 0。