HashMap 哈希算法

面试官问："HashMap 的 hash 方法是怎么实现的？"

候选人小蒋答："调用 key 的 hashCode()。"

面试官追问："那 JDK 8 的 hash 方法做了什么额外处理？"

小蒋说："好像是做了一个移位运算..."

面试官继续追问："为什么要这么做？"

小蒋答不上来。

【面试官心理】这道题考查的是候选人对 HashMap 哈希算法的理解深度。能说出"扰动函数"和"高位低位异或"原理的候选人，说明真正理解过 HashMap 的设计意图。

一、hash 方法源码解析 🔴

// JDK 7
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

// JDK 8（简化版）
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

JDK 8 的 hash 方法做了两件事：

计算 key 的 hashCode（32 位 int）
将 hashCode 的高 16 位与低 16 位异或

二、为什么要扰动？🔴

2.1 问题：低位分布不均匀

// HashMap 通过 (n-1) & hash 确定桶位置
i = (n - 1) & hash;

// 如果 n = 16，n-1 = 15 = 0b0000 0000 0000 1111

// hash & 15 只能取到 hash 的低 4 位
// 如果 hash 的低 4 位分布不均匀（很多 hash 的低 4 位相同）
// → 大量 key 哈希到同一个桶（哈希碰撞）

2.2 解决方案：扰动函数

// hash ^ (hash >>> 16)
// 高 16 位右移 16 位，低位变成 0
// 然后与原 hash 异或

// 效果：让高位和低位都参与到取模运算中

hash = 0b1111 0101 1100 0011 0010 1001 1001 1010
hash >>> 16 = 0b0000 0000 0000 0000 1111 0101 1100 0011
hash ^ (hash >>> 16) = 高位信息混入低位

2.3 扰动效果示例

// 假设两个对象的 hashCode：
hash1 = 0bxxxx xxxx xxxx xxxx 0000 0000 0000 0001  // 低 4 位是 1
hash2 = 0bxxxx xxxx xxxx xxxx 0000 0000 0001 0001  // 低 4 位是 1（相同！）

// 直接用 hashCode & 15，两者结果相同（哈希碰撞）
hash1 & 15 = 1
hash2 & 15 = 1

// 扰动后：
hash1 ^ (hash1 >>> 16) = 不同的高位信息混入
hash2 ^ (hash2 >>> 16) = 不同的高位信息混入

// 扰动后 & 15，结果可能不同
扰动后 hash1 & 15 = 某个值
扰动后 hash2 & 15 = 另一个值

三、为什么容量必须是 2 的幂次 🔴

3.1 取模 vs 位运算

// 普通取模（任何整数）
index = hash % n;

// HashMap 的取模（n 必须是 2 的幂次）
index = (n - 1) & hash;

// n = 16 时：
// n-1 = 0b0000 0000 0000 1111（全是 1 的二进制）
// hash & 0b1111 等价于 hash % 16

3.2 性能对比

// 位运算：CPU 一条指令完成
index = (n - 1) & hash; // ~1 ns

// 取模：编译器优化后可能用乘法逆元
index = hash % n; // ~10-20 ns

位运算比取模快 10-20 倍！

3.3 HashMap 如何保证 n 是 2 的幂次

// 无参构造器：不初始化，懒加载
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
    // table = null（懒加载）
}

// tableSizeFor 保证返回 >= cap 的最小 2 的幂次
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

// tableSizeFor(10) = 16
// tableSizeFor(32) = 32
// tableSizeFor(33) = 64

四、tableSizeFor 算法解析 🔴

// tableSizeFor(10) 的计算过程：
cap = 10, n = 9

n |= n >>> 1:  n = 9 | 4 = 13  (0b1101)
n |= n >>> 2:  n = 13 | 3 = 15  (0b1111)
n |= n >>> 4:  n = 15 | 0 = 15  (不变)
n |= n >>> 8:  n = 15 | 0 = 15  (不变)
n |= n >>> 16: n = 15 | 0 = 15  (不变)

n + 1 = 16  ✓

// 最终效果：将最高位的 1 复制到低位
// 9 (0b01001) → 15 (0b01111)

五、追问升级

面试官："如果 HashMap 的容量不是 2 的幂次，会发生什么？"

// 假设 n = 15（不是 2 的幂次）
// n-1 = 14 = 0b01110

// hash & 14 = ?
// 等价于 hash % 15，不是 hash % 14

// 对于 hash = 15:  15 & 14 = 14,  15 % 15 = 0  （结果不同！）
// 对于 hash = 16:  16 & 14 = 0,   16 % 15 = 1  （结果不同！）

问题：位运算 hash & (n-1) 不再等价于 hash % n，哈希分布会变得不均匀。

面试官："自定义对象做 HashMap 的 key，需要注意什么？"

class Person {
    String name;
    int age;

    @Override
    public int hashCode() {
        // ✅ 好的 hashCode：用所有关键字段
        return name.hashCode() * 31 + age;
    }

    @Override
    public boolean equals(Object obj) {
        // ✅ equals 和 hashCode 必须同时重写
        if (!(obj instanceof Person)) return false;
        Person p = (Person) obj;
        return name.equals(p.name) && age == p.age;
    }
}

【面试官心理】能说出"equals 和 hashCode 必须同时重写"并给出正确实现的候选人，说明有工程实践。这是 HashMap 相关题目的基本要求。

#HashMap 哈希算法

#一、hash 方法源码解析 🔴

#二、为什么要扰动？🔴

#2.1 问题：低位分布不均匀

#2.2 解决方案：扰动函数

#2.3 扰动效果示例

#三、为什么容量必须是 2 的幂次 🔴

#3.1 取模 vs 位运算

#3.2 性能对比

#3.3 HashMap 如何保证 n 是 2 的幂次

#四、tableSizeFor 算法解析 🔴

#五、追问升级