关键在于扰动函数(h ^ h>>>16)、容量为2的幂、(n-1)&hash位运算三者协同：扰动使高位影响低位，2的幂保障位运算可行且索引均匀，缺一不可。

Java HashMap 的 hash 算法要实现均匀分布，关键不在“随便写个取模”，而在于三步协同：高质量的扰动函数 + 容量强制为 2 的幂 + 位运算寻址。这三者缺一不可，否则哪怕哈希值本身分布好，落到桶里也会严重倾斜。

扰动函数：让高位也参与运算

Java 中 key 的原始 hashCode() 可能低比特位变化少（比如对象内存地址、连续整数），直接用会导致大量 key 落在相同桶中。HashMap 采用：

• (h = key.hashCode()) ^ (h >>> 16) —— 将高16位异或到低16位
• 这样即使低16位相似，高16位不同也能影响最终结果，大幅提升低位的离散性
• 右移16位成本极低，且不依赖乘除，比传统除法散列（如 h % prime）更高效

容量必须是 2 的幂：为位运算铺路

HashMap 底层数组长度始终是 2ⁿ（如 16、32、64…），不是素数。原因很实际：

OpenJDK 24

下载

• 用 (n - 1) & hash 替代 hash % n，位运算快一个数量级
• 当 n = 2ⁿ 时，n-1 的二进制全是 1（如 15 → 1111），& 运算等价于取 hash 的低 n 位，天然保证索引在 [0, n-1] 范围内
• 更重要的是：只有这时，hash 值的每一位都对最终桶位置有贡献；若用素数取模，低比特位容易被“吃掉”，造成聚集

扩容时的再哈希：只看高位，移动更少

扩容从 2ⁿ → 2ⁿ⁺¹ 时，新容量多一位。此时：

• 旧索引位置 i 和新索引位置 j 的关系是：j = i 或 j = i + 2ⁿ
• 判断依据就是 hash 的第 n 位（即新增的最高有效位）是否为 1
• 这意味着每个节点只需检查一位，就能决定留在原地还是挪到高位桶——避免全量重哈希，提升扩容效率

补充：为什么不用素数容量？

虽然除法散列中素数能缓解部分冲突，但在 HashMap 场景下它反而有害：

• 取模运算慢，破坏 O(1) 查找的性能基线
• 无法利用位运算加速，且不能支持上述高效的扩容迁移逻辑
• 实际测试表明，在 key 分布正常时，2ⁿ 配合扰动函数的冲突率不高于素数方案，甚至更低

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南