为什么 HashMap 的容量总是 2 的幂？取模为什么能用位运算？

简化版

因为当容量是 2 的幂时，hash % capacity 可以用位运算 hash & (capacity − 1) 代替，而位运算比取模快得多，且效果完全等价。同时 capacity − 1 是一串全 1 的低位掩码（如 16−1=1111），能让 hash 的低位都参与运算，下标分布更均匀。所以 Java HashMap 强制把容量规整成 2 的幂。

详细版

关键恒等式：当 capacity 是 2 的幂时，hash % capacity == hash & (capacity − 1)。

例：容量 16，hash % 16 等价于 hash & 15（15 = 0b1111）。
位与只取 hash 的低 4 位，结果范围恰好 [0, 15]，正好是下标范围。

好处：

位运算比取模快：& 是单周期 CPU 指令，% 涉及除法慢得多。哈希表每次存取都要算下标，这点加速很值。
分布均匀：capacity−1 是低位全 1 的掩码，hash 的每个低位都能影响下标；若容量不是 2 的幂，掩码有 0 位，某些下标永远取不到，分布不均。
扩容优化：容量翻倍时元素要么留原位、要么移到「原位 + 旧容量」，只需看多出来的一个 bit，无需重新取模。

所以哪怕你 new HashMap<>(10)，它也会把容量向上取整成 16。

完整版教学

一、为什么 2 的幂能把取模变成位与

一个数对 2^n 取模，等于只保留它二进制的低 n 位——这正好是「和低 n 位全 1 的掩码做位与」。

hash    = 0110 1101   (109)
cap     = 16 = 2^4
cap - 1 = 0000 1111   (15，低 4 位全 1)
hash & (cap-1) = 0000 1101 = 13
109 % 16       = 13      ✓ 完全一致

因为 2^n 及以上的高位对「除以 2^n 的余数」没有贡献，砍掉高位（位与掩码）就等于取模。这个等价只在除数是 2 的幂时成立。

二、为什么只对 2 的幂成立

如果容量是 15（不是 2 的幂），15 − 1 = 14 = 0b1110，最低位是 0。用它做位与，结果的最低位永远是 0，意味着所有奇数下标永远不会被用到，一半的桶白白浪费，冲突翻倍。只有容量是 2 的幂，cap−1 才是「连续的低位全 1」，每个下标都可达、分布才均匀。

三、扰动函数：让高位也参与

位与只用到 hash 的低位，如果两个 key 的低位相同、只有高位不同，就会冲突。为此 HashMap 在取下标前做一次扰动：

static int hash(Object key) {
    int h = key.hashCode();
    return h ^ (h >>> 16);   // 把高 16 位异或到低 16 位
}

把高位信息「搅」进低位，这样即使容量小、只取低位，高位差异也能体现出来，进一步减少冲突。这和「容量取 2 的幂」是配套的：一个负责快速取下标，一个负责补偿「只用低位」的缺陷。

四、扩容时的位运算红利

容量从 16（10000）翻倍到 32（100000），cap−1 从 01111 变成 11111，只多了一个高位。旧桶里的元素重新定位时，只要看 hash 在新增的那一位（第 5 位）是 0 还是 1：

是 0 → 下标不变，留在原桶。
是 1 → 下标 = 原下标 + 旧容量（16）。

于是一条链只需拆成「低位链 / 高位链」两条，无需对每个元素重新取模。2 的幂容量让扩容也变得高效。

五、面试怎么串起来答

「容量取 2 的幂」不是孤立设计，而是一整套配合：2 的幂 → 取模变位与（快）→ 低位掩码要求分布均匀 → 扰动函数补偿高位 → 扩容时按单 bit 拆链。能把这条链讲通，说明你真懂 HashMap 的下标机制，而不是死记「容量是 2 的幂」。

六、常见误区与追问

容量 n	取模表达式	位运算替代	是否等价
16	`hash % 16`	`hash & 15`	等价
32	`hash % 32`	`hash & 31`	等价
10	`hash % 10`	`hash & 9`	不等价

易错点：hash & (n-1) 只有在 n 是 2 的幂时才等价于取模。不是所有容量都能这么替换。

数字例子：hash=27，容量 16 时，27 % 16 = 11，而 27 & 15 也等于 11，因为 15 的二进制低 4 位全是 1。若容量是 10，27 % 10 = 7，但 27 & 9 = 9，结果完全不同。

误区：容量设成 2 的幂只是为了省一点取模时间。 它还让扩容时元素要么留在原桶，要么移动到 oldIndex + oldCap，迁移更有规律。
误区：hashCode 高位质量不重要。 容量较小时只看低位，扰动函数会把高位信息混入低位，减少低位碰撞。
误区：任何整数容量都能用 & 替代 %。 只有 2 的幂容量才成立。
追问：为什么扩容通常翻倍？ 翻倍能保持容量仍是 2 的幂，并让旧索引和新索引关系简单。
追问：如果 hash 低位分布很差会怎样？ 即使 key 不同，也会集中到少数桶，链表或树变长，查询性能下降。
追问：面试回答要不要背源码细节？ 重点讲清 2 的幂、位与取模、扰动函数和扩容迁移规律即可。

七、加强记忆

容量取 2 的幂，是为了让 hash % cap 变成更快的 hash & (cap−1)，且 cap−1 是低位全 1 掩码、每个下标都可达、分布均匀。配套的扰动函数 h ^ (h>>>16) 把高位混进低位补偿「只用低位」的缺陷；扩容翻倍时只需看新增一个 bit 把链拆两条，无需重新取模。非 2 的幂会让部分下标永不命中、冲突加倍。

简化版

详细版