为什么按位与运算要比取模运算高效？

面试考察点

1. 底层认知：面试官要的不只是 “位运算快” 这个结论。你能不能把 “快” 讲到 CPU 指令层面，说得出时钟周期差多少，才算真懂。

2. 数学基础：(n - 1) & hash 能替代 hash % n 是有前提的——n 必须是 2 的幂。讲不清这个等价关系，说明只是背了源码。

3. 设计权衡的意识：HashMap 为了用上这个优化，宁愿强制容量必须是 2 的幂。能讲明白这层 “为了快付出什么代价”，是加分项。

核心答案

一句话：两者在 CPU 层面的开销完全不在一个量级。

• 按位与 &：对应一条 AND 指令，1 个时钟周期就能完成
• 取模 %：本质是除法运算，要靠 CPU 的除法器执行（x86 上是 DIV/IDIV 指令），32 位整数除法在现代 CPU 上要 20 个时钟周期上下，64 位或老一些的架构能到 40 甚至更高

再加上 HashMap 的定位——put、get、扩容，每次都要算下标，这是个不折不扣的热点路径，一点点的指令差距乘以海量调用次数，差距就被放大了。

等价公式（面试要脱口而出）：

当 n 为 2 的幂时：hash % n == hash & (n - 1)

深度解析

一、CPU 指令层面：一条指令和几十条指令的差距

CPU 里每种运算的 “成本” 天差地别。加减法、位运算最便宜；乘法稍贵；除法最贵，因为除法在硬件上要靠迭代逼近来实现，电路复杂、延迟高。

hash & (n - 1) 编译后就是一条 AND 指令，取两个操作数按位与，一个周期出结果，而且不占用除法器，流水线里可以和其他指令并行。

hash % n 在 Java 里对应字节码指令 irem，JVM 实现它要借助除法：x86 的 DIV 指令执行 32 位整数除法，在现代 CPU 上延迟普遍 20 个周期起步，老一些的微架构上甚至能到 40 以上。

也就是说，换成按位与，单次下标计算能省 20 倍以上的指令周期。一次 put 省这么多，一千万次 put 呢？

图的意思很直白：两条路殊途同归，结果一模一样，但左边要走除法器这条 “贵” 的路，右边一条 AND 指令就到站。HashMap 毫不犹豫选了右边。

二、数学层面：为什么 n 是 2 的幂时两者等价

这是这道题的核心，很多背题的人恰恰栽在这里。

先看一个二进制规律：2 的幂减 1，二进制全是 1。

• 16 - 1 = 15 → 1111
• 32 - 1 = 31 → 11111
• 1024 - 1 = 1023 → 1111111111

而一个数对 2 的幂取模，本质上就是 只保留低位的二进制位，把高位全扔掉。

为什么？因为 n = 2^k 时，二进制从第 k 位往上的每一位，权重都是 2^k 的倍数——这些位凑出来的值天然是 n 的整数倍，对取模没贡献；只有低 k 位是 “零头”，正好就是余数。

拿实际数字算一遍，hash = 157，n = 16：

hash      = 157 = 1001 1101
n - 1     = 15  = 0000 1111
──────────────────────────
hash & 15     = 0000 1101 = 13

验证: 157 % 16 = 13 ✓

157 = 9 × 16 + 13，那个 9 就是高位 1001，13 就是低位 1101。按位与 0000 1111 相当于一个 “低位截取器”，把 13 完整保留、把 9 整个清零——效果和取模分毫不差。

反过来说，如果 n 不是 2 的幂，比如 n = 10（二进制 1010），n - 1 = 9（1001），掩码里夹着 0 位，该砍的高位砍不干净，该留的低位也保不齐，和 hash % 10 的结果就对不上了。

所以等价关系是有前提的：n 必须是 2 的幂。这就是 HashMap 死磕 2 的幂容量的根本原因。

三、HashMap 的落地：为了用 &，先把容量钉死成 2 的幂

JDK 8 里 HashMap 计算下标的源码就一行（putVal 和 get 里都有）：

// JDK 8 HashMap#putVal 节选
if ((p = tab[i = (n - 1) & hash]) == null)
    // 直接落桶，n 是 table 长度，hash 是扰动后的哈希值
    tab[i] = newNode(hash, key, value, null);

但代价是什么？HashMap 必须保证任何时刻 n 都是 2 的幂，否则 (n - 1) & hash 立刻算错。它的做法有两手：

1. 构造时向上取整到 2 的幂 —— tableSizeFor()

// 你传 10，它给你 16；传 17，给你 32
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;
}

这段五次位移加按位或，把最高位 1 之后的所有位全部填成 1，再加 1，就得到不小于 cap 的最小 2 的幂。本身也是个位运算的经典操作。

2. 扩容时翻倍 —— newCap = oldCap << 1

容量从 16 → 32 → 64，每次左移一位，2 的幂属性永远不丢。顺便说一句，正因为容量是 2 的幂，扩容后元素要么留在原桶、要么正好移动 oldCap 那么远，JDK 8 的 resize() 才能靠 e.hash & oldCap 是否为 0 一刀切地把链表拆成两条，不用重新计算每个元素的桶下标——这是 2 的幂带来的第二重红利。

实际开发里这个套路也不止 HashMap 在用：ArrayDeque 内部数组的容量也强制 2 的幂，用 (head - 1) & (elements.length - 1) 算下标——head 为 0 时 head - 1 是 -1，-1 & 15 = 15，一次位运算顺手完成了越界回绕，连 if 判断都省了；高性能队列 Disruptor 的环形缓冲区（RingBuffer）官方文档直接写明 size must be power of 2，就是为了用 sequence & (size - 1) 替代取模。环形队列场景下下标计算被调用的频率比 HashMap 还狠，这点优化更不能省。

四、一个容易忽略的点：JIT 也不是完全救不了 %

有个细节可以讲，能明显拉开档次：JIT（C2 编译器）其实会优化取模——当除数是编译期常量时，它会把 % 改写成乘法加位移的组合（所谓 magic number 魔数优化），比如 x % 8 直接变 x & 7。

但 HashMap 的 n 是运行时变量（table 长度随扩容变化），JIT 无能为力，只能老老实实走除法指令。所以源码层面手动写 & (n - 1)，等于替 JIT 把活干了。

自己写业务代码时同理：x % 2 判断奇偶这种，编译器会帮你优化；但 x % 变量 这种，如果变量恰好能保证是 2 的幂，手动换成 & 才有意义。

面试高频追问

1. 追问一：HashMap 初始容量传 10，真正的容量是多少？

   16。tableSizeFor(10) 向上取整到最近的 2 的幂。注意 JDK 8 是懒加载：构造时只把 16 记在 threshold 里，第一次 put 才真正建表。

2. 追问二：为什么 HashMap 还要做扰动（h ^ (h >>> 16)）？

   因为下标只用了哈希值的低几位（n = 16 时只用低 4 位），高位几乎不参与。扰动把高 16 位异或到低位，让高位信息也参与下标计算，降低碰撞概率。它和 & (n - 1) 是配套设计：一个管 “散列得均匀”，一个管 “算得快”。

3. 追问三：是不是所有场景都该用 & 替代 %？

   不是。前提是除数为 2 的幂，另外留意负数的坑：Java 里负数取模的结果可以是负数，位与的结果却永远非负，两者语义并不等价。除数不是 2 的幂，或者你就是需要数学意义上的取模（比如 (a % b + b) % b 防负数），那还是老老实实用 %。

常见面试变体

• “HashMap 的容量为什么必须是 2 的幂？”（同一件事反过来问）
• “hash & (n - 1) 什么时候会算出和 hash % n 不同的结果？”
• “除了 HashMap，还知道哪些地方用了 ‘2 的幂 + 位运算’ 的套路？”（ArrayDeque、Disruptor、各类环形缓冲区）

记忆口诀

“2 的幂才等价，n - 1 全是 1；AND 一拍出结果，除法慢它几十倍。”

总结

按位与快，是因为它只要一条 AND 指令（约 1 个时钟周期），而取模要走除法器（20 个周期起步）；HashMap 敢用 (n - 1) & hash 替代 hash % n，靠的是把容量死死钉在 2 的幂上——n 是 2 的幂时两者数学等价。一句话把 “快在哪、为什么能换、代价是什么” 三层讲清楚，这题就答满分了。