# 问题
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 扩容影响性能?