cyxCoder

在 Java 的 HashMap 中，使用i = (n - 1) & hash计算数组下标而非传统的取模运算（hash % n），核心原因是位运算的高效性，同时通过对数组长度n的特殊设计（保证为 2 的幂），使得该位运算与取模运算结果等价。

前提：n是 2 的幂次方

HashMap 的数组长度n始终保持为 2 的幂次方（初始化时默认 16，扩容时以 2 倍增长）。这一设计是关键，因为当n为 2 的幂时，n的二进制形式为100...0（如 16 是10000，32 是100000），而n-1的二进制形式则为011...1（如 15 是01111，31 是011111），即低位全为 1。

等价性：(n-1) & hash 等价于 hash % n

当n是 2 的幂时，(n-1) & hash 的结果与 hash % n（取模）完全相同。

原理：二进制中，n-1的低位全为 1，与hash进行&运算时，会保留hash二进制中低于n最高位的所有位，这恰好等价于对n取模的结果。即最大值是：n-1,最小值是：0

举例：

设n=8（2 的 3 次幂，二进制1000），则n-1=7（二进制0111）。

若hash=10（二进制1010）：

• 10（1000） & 7 （0111）= 2（0010）（ 与运算： 0 & 1 = 0，1 & 0 = 0， 0 & 0 = 0， 1 & 1 =1）
• 10 % 8 = 2
• 两者结果完全一致。

高效性：位运算远快于取模运算

计算机底层对位运算（&、|、^ 等） 的处理效率远高于取模运算（%）。

取模运算本质是除法的衍生，需要经过复杂的硬件运算步骤；

位运算直接操作二进制位，几乎是处理器的原生操作，耗时极短。

HashMap 作为高频使用的数据结构，通过位运算替代取模，能显著提升插入、查询等操作的性能。