先给结论

因为要用& (n-1)代替取模。n 是 2 的幂时，n-1的二进制全是 1，位与的结果刚好等价于取模，而且比取模快。

但更值钱的理由在扩容那一步，多数人不知道。

一个很常见的初始化

很多团队写代码时都会这么干：已知要放 1000 个元素，于是new HashMap<>(1000)，心想一次分配到位，省一次扩容。

实际上它还是会扩一次。原因在后面第 4 节，看完就明白为什么阿里巴巴的开发手册建议写成new HashMap<>(expectedSize / 0.75 + 1)。

扩容不是小事。一次 resize 要重新分配一个两倍大的数组，再把所有元素搬过去，数据量大的时候这是一次明显的停顿。缓存类的 Map 如果初始化容量没算对，启动阶段可能连续扩三四次。

先把问的是哪一层搞清楚

"HashMap 底层实现"其实是把四个问题打包在一起问：

数据结构长什么样；hash 值怎么算的；拿到 hash 之后怎么定位到数组下标；容量不够时怎么扩容。

多数人只会答第一层。第三层和第四层才藏着 2 的幂这个答案。

逐层拆开

数据结构：数组加链表，链表太长变红黑树

JDK 1.8 的 HashMap 是数组（table）、链表、红黑树的组合。每个数组位置叫一个桶，哈希冲突的元素挂在同一个桶上，形成链表。

链表长了查询会退化成 O(n)，所以 1.8 加了树化：链表长度超过 8，并且数组长度达到 64，链表转成红黑树，查询变成 O(log n)。

注意是两个条件同时满足。数组还没到 64 的时候，优先做的是扩容而不是树化，因为扩容能直接把冲突分散开，代价通常比建树低。

反过来，树上的元素减少到 6 时会退化成链表。为什么不是 8？中间留了 1 的缓冲，避免某个桶的元素数在 8 附近反复横跳导致来回转换。

hash 值：一次高位异或

// JDK 1.8 java.util.HashMap static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

把 hashCode 的高 16 位和低 16 位做异或，结果还是 32 位。这一步叫扰动。

它的目的不是"让 hash 更随机"。真正的原因是，数组长度比较小的时候，定位下标只用到低位，高 16 位完全不参与。如果两个 key 的低位一样、高位不同，它们会撞到同一个桶。异或之后，高位的信息被混进了低位，冲突概率就降下来了。

HashMap 只在这一处做了扰动，没有用多重哈希那种更重的算法。这是个取舍：多花一次异或的代价，换大部分场景下的冲突改善，够了。

定位下标：用位与取代取模

// JDK 1.8，putVal 里的定位 // n = table.length int index = (n - 1) & hash;

取模的正经写法是hash % n。位运算比取模快，但两者等价有个前提：n必须是 2 的幂。

n 是 16，n-1是 15，二进制1111。任何数跟1111做与运算，结果就是它最低 4 位的值，范围 0 到 15，正好是取模的结果。

n 是 10，n-1是 9，二进制1001。做与运算之后，第 2 位和第 3 位永远是 0，也就是说下标 2、3、4、5、6、7 里有好几个永远空着。一半的桶浪费了，冲突率直接翻倍。

这就是"必须是 2 的幂"最直接的技术理由。

扩容：这才是 2 的幂真正的价值

这部分是被答得最薄的一层。

容量从 16 扩到 32，(n-1) & hash里的掩码从1111变成11111，多参与了一位。于是每个元素的新下标只有两种可能：

原下标不变，或者原下标加上旧容量（16）。

判断条件极简单，看 hash 在那新增的一位上是 0 还是 1：

// JDK 1.8 resize 里的拆分逻辑，简化后 if ((e.hash & oldCap) == 0) { // 新下标 = 原下标，留在 lo 链 } else { // 新下标 = 原下标 + oldCap，进 hi 链 }

一次位与就能决定去向，不用重新算 hash，不用重新取模。

好处还不止省了一次运算。因为同一条链上的元素只可能分到两个桶里，JDK 1.8 直接把原来那条链拆成 lo 和 hi 两条，各自挂到新位置，链上元素的相对顺序还能保持原样。这顺手解决了 1.7 头插法导致的扩容死循环问题。

如果容量不是 2 的幂，这套拆分逻辑完全不成立，每个元素都得老老实实重算一遍模。扩容是 HashMap 最贵的操作，成本翻一倍是很难接受的。

顺带说初始化那件事。构造时传入的初始容量会被tableSizeFor往上取整到最近的 2 的幂：

// JDK 1.8，把任意正整数变成 >= 它的最小 2 的幂 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; }

传入 1000，得到 1024。但扩容阈值是1024 * 0.75 = 768，放到第 769 个元素时就触发扩容了。所以想放 1000 个元素又不扩容，初始值得写成1000 / 0.75 + 1，约等于 1335。

面试官在等的那句

答完"& (n-1)比取模快"，及格了。但这句话任何背过八股的人都会说，没有区分度。

真正让人抬眼的是这一句：

取模快只是顺带的收益，2 的幂真正解决的是扩容成本。正因为容量翻倍时掩码只多一位，每个元素的新下标只有两种可能，判断只需要一次位与，JDK 1.8 才能把一条链拆成两条直接搬走，不用逐个 rehash。

顺带说一句，负载因子取 0.75 也是有依据的。源码注释里给了个数：在理想的随机 hash 下，桶里的元素数服从泊松分布，负载因子 0.75 时链表长度达到 8 的概率大约是千万分之六，小到可以忽略。所以 8 这个树化阈值不是拍脑袋定的。

第二段尤其加分，因为大多数人只会背"默认 0.75"，说不出它是怎么来的。

五个常见误区

误区一：以为 new HashMap<>(1000) 就不会扩容会扩。容量被上调到 1024，但阈值是 1024 乘 0.75，等于 768。要按预期元素数除以 0.75 再加 1 来给初始值。

误区二：以为链表长度超过 8 就树化还要数组长度达到 64。没到 64 时优先扩容，因为那时候冲突多半是容量不够造成的。

误区三：以为元素少于 8 就从红黑树退回来退化阈值是 6。中间留的缓冲是为了避免在临界点反复转换。

**误区四：把扰动函数说成"让哈希更均匀"**它解决的是低位信息不足的问题。数组小的时候只有低几位参与运算，高 16 位被混下来才有意义。

**误区五：以为 1.8 的 HashMap 线程不安全只是"数据覆盖"**死循环确实被尾插法解决了，但并发 put 依然会丢数据，并发扩容也有风险。要线程安全还是得用 ConcurrentHashMap。至于用 Hashtable，我一般不选，全表一把锁，并发下退化得很厉害。这条看你们的具体场景，我给不了死结论。

速查表

关于本文

HashMap 这条线还有几道没写：为什么线程不安全、1.7 头插法死循环的完整过程、ConcurrentHashMap 从分段锁到 CAS 加 synchronized 的演进。J014 会讲 ConcurrentHashMap，那篇和这篇连着看会顺很多。

我会接着更新。感兴趣的话可以留个关注，方便下次找。

另外，完整的十二个模块（Java / C++ / Go / JVM / MySQL / Redis / MQ / 分布式 / 事务 / 网络 / 系统设计 / 项目深挖）我整理成了一份手册，每题都标了考察点和加分答法。【草丛后端架构】，持续分享后端架构与底层原理。