面灵AI→

字节一面:HashMap 扩容为什么必须按 2 的倍数扩

轮次
一面
时间
2026-10
来源
牛客网

《面试题目》

  1. 为什么 HashMap 扩容要按 2 的倍数扩?

《参考解析》

结论先说:按 2 的倍数扩容,本质是为了让「取桶下标」这一步能用位运算替代取模,并且让扩容时的元素迁移变成一次可以批量判断的位测试。

下标计算。HashMap 用 (n - 1) & hash 定位桶。只有 n 是 2 的幂时,n - 1 才是低位全 1 的掩码(16 → 1111),与运算的结果才等价于 hash % n,取值范围也刚好落在 [0, n-1] 内不越界。如果容量取 10 这样的非 2 幂,掩码会有 0 位,某些桶永远取不到,元素分布直接偏斜。

扩容迁移为什么也依赖这一点。容量翻倍时,旧桶里的元素要么留在原下标 i,要么挪到 i + oldCap,判据只有一位:hash & oldCap 是 0 还是 1。所以 JDK 8 的 resize() 不用重新算哈希,把链表拆成 lo、hi 两条就完成迁移。这一招成立的前提就是容量翻倍、且扩容前后都是 2 的幂。

还有一层是哈希扰动。HashMap 会对 hashCode 做一次高位异或(h ^ (h >>> 16)),让高位也参与低位下标计算。2 的幂容量只取低位,如果不再扰动,高位差异相同、低位相同的 key 会全部撞进同一个桶。

答这题容易漏的点:tableSizeFor() 会把传入的容量向上取整到 2 的幂,所以 new HashMap(10) 的实际容量是 16;负载因子 0.75 与 2 的幂容量是两个独立的设计,前者控冲突与空间,后者控下标计算与迁移效率。

面试之外的一句提醒:原帖作者提到「简历上写到的技术,哪怕不是自己负责的部分也要了解」,这在字节这类面试里很常见——简历是提问清单,不是免责声明。