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，扰动后低位也变得不同，减少冲突

三、扰动过程图解

对比 不扰动 扰动后
index 计算 hash & (n - 1)，n = 16 时只有低 4 位参与运算，高位全部被丢弃 先 hash ^ (hash >>> 16)，再 & (n - 1)
冲突示例 key A/B/C 的高 28 位完全不同，但低 4 位都是 0101，全部落入桶 5，产生冲突 低位融合了高位信息；n = 64 时 key A 低 6 位 000101 → 桶 5，key B 低 6 位 110101 → 桶 53
结论 高位信息浪费，冲突严重 冲突减少，散列更均匀

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

  • 异或特性：相同为 0，不同为 1。高 16 位与自己异或保持不变，低 16 位与高 16 位异或产生变化。
  • 只扰动一次：为什么不是多次扰动？一次扰动已经足够，多次扰动反而可能增加计算开销。
  • 低 16 位变化：低 16 位融合了高 16 位的信息，即使两个 hashCode 低位相同，只要高位不同，扰动后低位也会不同。

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

运算方式 公式 特点
与（&） H & L 只有 1 & 1 = 1，其他都是 0，结果更容易趋向 0，不够随机
或（|） H | L 只有 0 | 0 = 0，其他都是 1，结果更容易趋向 1，不够随机
异或（^） H ^ L 0 和 1 概率各 50%，最随机，散列效果最好

异或的真值表：

A B A ^ B
0 0 0
0 1 1
1 0 1
1 1 0

输出 0 和 1 的概率相等，散列效果最好。

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

  • 与运算：偏向 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。

声明：本文转载自小哈的博客 《HashMap 的 hash 方法是如何实现的？》，版权归原文作者所有。转载请保留本声明与原文链接。