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

结论先行：只有一行——(h = key.hashCode()) ^ (h >>> 16)，key 为 null 时返回 0。它把 32 位 hashCode 的高 16 位异或到低 16 位，让高位也参与桶下标计算。因为下标用的是 (n - 1) & hash，n 较小时只有低位有效；不做扰动，“高位不同、低位相同”的 key 就会全部挤进同一个桶。

1. 一行代码的意图

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

原始 hashCode : 0x1234_ABCD
h >>> 16      : 0x0000_1234
XOR           : 0x1234_B9F9   ← 高 16 位的信息被折叠进低 16 位

异或的特点是“不同为 1、相同为 0”，既保留低位原貌，又混入高位信息，且不需要循环、没有分支，单条指令级开销。

2. 为什么必须扰动

官方注释举的例子是“连续整数 Float key 在小表里总是碰撞”：Float.hashCode 由 floatToIntBits 得到，1.0 是 0x3F800000、2.0 是 0x40000000，低位全是 0，掩码一与就全落到 0 号桶。异或把指数部分折下来，分布立刻改善。

3. 下标计算与容量

桶下标 i = (n - 1) & hash，n 必须是 2 的幂，这样 n - 1 是一段连续的 1，位与的结果恰好落在 [0, n-1]。

这也解释了为什么容量越大，碰撞越少——掩码变长，更多 hash 位参与定位。

4. 代码：观察扰动效果

public class SpreadDemo {
    static int spread(int h) {
        return h ^ (h >>> 16);
    }

    public static void main(String[] args) {
        int[] hashes = {0x0000ABCD, 0x1234ABCD, 0x12340000,
                        0x00010000, 0x00000001};
        for (int h : hashes) {
            System.out.printf("h=0x%08X  raw=%2d  spread=%2d%n",
                    h, h & 15, spread(h) & 15);
        }
    }
}
// 输出：
// h=0x0000ABCD  raw=13  spread=13
// h=0x1234ABCD  raw=13  spread= 9
// h=0x12340000  raw= 0  spread= 4
// h=0x00010000  raw= 0  spread= 1
// h=0x00000001  raw= 1  spread= 1

前两行最说明问题：0x0000ABCD 与 0x1234ABCD 的低 4 位完全相同，不扰动时都落在 13 号桶；扰动后一个 13、一个 9，冲突被拆开了。

5. 与 JDK 7 的差异

// JDK 7 的 hash：多轮移位异或，还掺入 hashSeed 防止碰撞攻击
final int hash(Object k) {
    int h = hashSeed;
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK 8 简化为一次 h ^ (h >>> 16)：一是红黑树已经能兜住长链，二是多轮扰动的收益在实测中很小，三是减少计算开销。ConcurrentHashMap 1.8 的 spread 在此基础上再与 HASH_BITS（0x7fffffff）相与，把最高位清零，留给 MOVED、TREEBIN 这些负 hash 标记使用。

6. 自定义 key 的写法建议

• 用 IDE 生成或 Objects.hash(...)，保证 equals 与 hashCode 使用同一组字段。
• 不要把 hashCode 写成 id % 16 这类只用低位的实现，那等于人为把桶数限制成 16。
• 不要把可变对象当 key，字段一改 hash 就变，表里再也找不到。
• 字符串 key 直接用 String 即可，它的 hashCode 是 31 * h + c，分布够用。
• 若 key 实现了 Comparable，树化时的比较会更稳定，减少 tieBreakOrder 兜底。

常见追问

• 为什么用异或，不用与/或？ 与运算会丢位（结果偏向 0），或运算会让结果偏向 1，异或能完整保留两边的差异信息。
• 为什么右移 16 位？ int 是 32 位，高低各 16 位，移一半正好把高位折到低位。
• 扰动后 hash 会是负数吗？ 会，但 (n - 1) & hash 只取低位，结果必然非负，不需要额外取绝对值。
• hash 方法为什么对 null 返回 0？ 避免 NPE，同时让 null key 稳定落在 0 号桶。
• 可以直接用 key.hashCode() 当数组下标吗？ 不能，hashCode 可能是负数且范围是整个 int，必须先掩码。
• 为什么 Hashtable 用 % 而不是 &？ 它的容量是 2n+1 这类非 2 的幂，只能取模；HashMap 把容量限定为 2 的幂，才换来了位运算。

小结

hash 方法只有一行，却解决了一个具体问题：低位掩码会浪费 hash 的高位信息。h ^ (h >>> 16) 用最小代价把高位折下来，让桶下标更均匀；配合“容量取 2 的幂 + 掩码定位”，HashMap 才能做到平均 O(1)。回答时按“代码 → 目的 → 不扰动会怎样 → 与 1.7 的差异”四步讲，最后补一句“自定义 key 必须同时正确实现 equals 和 hashCode”，就是完整答案。