# 问题
5. 为什么 HashMap 的初始容量必须是 2 的幂次方？
# 标准答案
HashMap 的初始容量必须是 2 的幂次方，以便利用 位运算优化哈希寻址，使 index = (n - 1) & hash 计算索引时高效且均匀分布，从而提高查询和存储效率。如果容量不是 2 的幂次方，HashMap 会自动调整为最接近的 2 的幂，避免哈希冲突增多、空间浪费以及扩容时的复杂计算。
# 答案解析
# 1. HashMap 索引计算的优化
在 HashMap 中，键值对存储在 数组（table） 中，索引位置通过 hash & (n - 1) 计算，其中 n 是数组的长度（必须是 2 的幂次方）。
为什么用 n - 1 进行 & 运算？
- 假设
n = 16（2^4），则n - 1 = 15，二进制表示为0000 1111。 hash & 15相当于 仅保留 hash 的低 4 位，保证索引计算落在[0, 15]的范围内。- 由于 2 的幂次方特性，
&计算 等价于取模运算（hash % n），但&比%更快，因为位运算比除法效率高。
示例代码：
int index = hash & (table.length - 1); // 等效于 hash % table.length
# 2. 如果 n 不是 2 的幂会发生什么？
如果 n 不是 2 的幂，比如 n = 10，则 n-1 = 9 (1001)，二进制 & 运算后，索引计算无法均匀分布，可能导致哈希冲突严重。
示例（n = 10）
假设 hash 计算的低几位：
1010 1100 结果：1100 & 1001 = 1000 → 落在索引 8
0110 0011 结果：0011 & 1001 = 0001 → 落在索引 1
2
3
可以看到 某些索引（如 8、1）会比其他索引更容易被命中，导致哈希分布不均，冲突严重。
HashMap 的优化：
- 当
initialCapacity不是 2 的幂时，HashMap 自动调整 为最接近的 2 的幂。 - 例如
new HashMap<>(10)实际上会调整为16。
源码（tableSizeFor 方法，自动调整容量）：
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;
}
2
3
4
5
6
7
8
9
这个算法的作用是将 cap 向上取整到 最近的 2 的幂。
# 3. 避免扩容时 rehash 计算复杂
HashMap 采用 等量扩容（容量翻倍），每次扩容后新索引计算方式变为 hash & (2n - 1)，这样可以快速决定元素是否需要迁移到新位置，避免重新计算所有哈希值，提高扩容效率。
扩容优化（JDK 1.8）：
- 在 rehash 过程中，如果
hash & n == 0，元素 保留原索引； - 否则，元素 索引 = 旧索引 + n，只需 O(1) 计算，避免 hashCode 重新计算。
示例：
if ((e.hash & oldCap) == 0)
newTable[i] = e; // 位置不变
else
newTable[i + oldCap] = e; // 迁移到新位置
2
3
4
# 4. JDK 1.7 与 JDK 1.8 处理索引的不同
| 版本 | 计算索引方式 | 扩容后索引迁移优化 | 计算复杂度 |
|---|---|---|---|
| JDK 1.7 | hash % length（但用 & 代替） | 需要重新计算 hashCode() | O(n) |
| JDK 1.8 | hash & (length - 1) | 只判断 hash & n，无需重新计算 hashCode() | O(1) |
# 5. HashMap 的常见问题
❌ 常见误区
误认为 HashMap 支持任意容量
- HashMap 仅支持 2 的幂次方容量，若传入 10，最终会调整为 16。
误以为
n % m与n & (m - 1)计算结果相同- 只有
m是 2 的幂次方时，n & (m - 1)才等价于n % m，否则会导致哈希分布不均。
- 只有
忽视扩容导致性能下降
- 频繁
put()但未指定初始容量，可能触发多次扩容，影响性能。 - 解决方案：预估 key 数量，合理设置 initialCapacity。
- 频繁
# 深入追问
🔹 为什么 hash & (n - 1) 比 hash % n 更快？
🔹 为什么 tableSizeFor 使用位运算调整容量？
🔹 为什么扩容时 hash & oldCap == 0 可以确定索引？
🔹 HashMap 什么时候会触发扩容？
# 相关面试题
• 为什么 HashMap 采用 n - 1 计算索引，而不是 n？
• ConcurrentHashMap 是否必须使用 2 的幂？
• 如何避免 HashMap 扩容影响性能？
