(n−1)&hash能替代hash%n，因n为2的幂时n−1二进制全为1，位与操作等价于取hash低log₂n位，速度远快于取模；若n非2的幂则索引分布失衡、冲突剧增。

因为这是用位运算高效替代取模运算的方案，前提是数组长度 n 必须是 2 的幂次方。

为什么不用 hash % n

取模运算本质是除法，CPU 执行开销大；而位与运算（&）直接操作二进制位，速度通常快十几倍甚至更多。在高频 put 操作中，这点差异会显著影响整体性能。

为什么 (n - 1) & hash 等价于 hash % n

当 n 是 2 的幂（如 16、32、64），n−1 的二进制全是 1（例如 16−1 = 15 → 1111）。此时 (n−1) & hash 实际就是保留 hash 的低 k 位，恰好等于 hash 对 n 取余的结果。

Java Maven Common

Java Maven 项目审查工作流的通用输入处理。当 Java Maven 项目以 ZIP压缩包或 GitLab 仓库 URL 形式提供且需要...时使用。

下载

• n = 16 → n−1 = 15 = 00001111₂ → 保留 hash 最低 4 位
• n = 32 → n−1 = 31 = 00011111₂ → 保留最低 5 位

如果不满足 2 的幂，会发生什么

比如 n = 10，n−1 = 9 = 1001₂，那么 (n−1) & hash 只保留 hash 的第 0 位和第 3 位，其余位被强制清零。这会导致：

立即学习“Java免费学习笔记（深入）”；

• 大量哈希值映射到极少数下标（如 0、1、8、9）
• 其他桶长期空置，分布严重倾斜
• 冲突剧增，链表/红黑树变长，查找退化为 O(n)

它还依赖扰动函数协同工作

HashMap 先对原始 hashCode 做扰动：hash = h ^ (h >>> 16)，把高 16 位混入低 16 位。否则仅靠低位参与 & 运算，容易因高位不同、低位相同而频繁碰撞（比如两个 key 的 hashCode 仅高位不同，低 4 位都是 1010，就会都落到下标 10）。