# 问题
17. HashMap 什么时候会触发扩容?扩容的代价是什么?如何减少扩容次数?
# 标准答案
HashMap 触发扩容的条件是元素个数(size)超过 capacity * loadFactor
,默认负载因子为 0.75,即当元素数量超过桶容量的 75% 时,HashMap 会扩容为原来的 2 倍,并重新计算所有元素的哈希位置(rehash)。扩容的代价主要包括创建更大数组、重新计算哈希值、数据迁移,会导致较高的 CPU 和内存开销。减少扩容次数的方法包括:
- 合理预估元素数量,通过
new HashMap<>(initialCapacity, loadFactor)
预设初始容量,避免频繁扩容。 - 使用合适的负载因子,高负载因子(如 0.8~0.9)可以减少扩容,但可能导致更多哈希冲突。
- 使用静态哈希表(如
ImmutableMap
)避免动态扩容,在高并发场景使用ConcurrentHashMap
。
# 答案解析
# HashMap 的存储结构与扩容触发条件
HashMap 的底层数据结构是数组 + 链表 + 红黑树(JDK 1.8 之后),数据存储在Node<K,V>[] table 数组中。当 put()
方法插入新元素时,会计算哈希值并存入数组对应索引。如果数组装填超过阈值(threshold),就会触发扩容,公式如下:
threshold = capacity * loadFactor;
1
默认情况下(loadFactor = 0.75):
- 初始
capacity = 16
,threshold = 16 × 0.75 = 12
,当存入第 13 个元素时触发扩容。 - 扩容后,
capacity = 32
,threshold = 32 × 0.75 = 24
,当存入第 25 个元素时再次扩容。
# HashMap 扩容的完整执行流程
当 HashMap 触发扩容时,resize()
方法会执行以下操作:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 已存在数组
newCap = oldCap << 1; // 容量翻倍
newThr = oldThr << 1; // 计算新阈值
} else { // 第一次创建
newCap = DEFAULT_INITIAL_CAPACITY; // 默认16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
for (Node<K,V> e : oldTab) { // 遍历旧数组,重新映射
do {
Node<K,V> next = e.next;
int i = e.hash & (newCap - 1); // 计算新索引
e.next = newTab[i]; // 头插法
newTab[i] = e;
} while ((e = next) != null);
}
return newTab;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
详细步骤如下:
- 计算新容量和阈值:
capacity *= 2
,threshold *= 2
。 - 创建新的 Node<K, V>[] 数组,容量翻倍。
- 遍历旧数组,重新计算哈希值,迁移数据。
- 元素重新分布:哈希索引变化规则:由于
newIndex = oldIndex & (newCapacity - 1)
1capacity
是 2 的幂次方,扩容后索引要么不变(hash & oldCap == 0),要么偏移oldCap
个位置,减少 rehash 计算。
# HashMap 扩容的代价分析
扩容操作涉及多个昂贵的计算:
数组创建开销
- Java 需要在堆上申请新的数组对象,并在
Eden
区分配内存。 - 如果扩容后
old
数组仍然有强引用,可能导致 GC 迟迟无法释放旧数据。
- Java 需要在堆上申请新的数组对象,并在
数据迁移(rehash)
- 旧数组中的所有元素都需要重新计算哈希值,新哈希值可能导致不同的索引位置变化。
- 在 Java 7 及以前,扩容时采用尾插法,多线程下可能导致环形链表(死循环)。
- 在 Java 8 之后,采用头插法和低位掩码优化,减少 rehash 开销。
CPU 计算开销
- 由于
hashCode()
可能涉及复杂计算,每个元素的哈希值重新计算会占用 CPU 资源,影响性能。
- 由于
影响 GC(垃圾回收)
- 扩容导致旧数组被废弃,触发 GC 清理大量对象,导致**Stop-the-world(STW)**暂停时间变长。
- 迁移期间可能造成大对象晋升到老年代,引发 Full GC。
# 如何减少扩容次数
合理预估初始容量
- 计算公式:
capacity = (expectedSize / loadFactor) + 1
1 - 例如预计存储 1000 个元素,最小
capacity = (1000 / 0.75) ≈ 1333
(向上取 2 的幂,即 2048)。 - 代码示例:
Map<String, Integer> map = new HashMap<>(2048);
1 - 这样可以一次性分配足够大的数组,避免后续扩容。
- 计算公式:
降低扩容阈值,优化负载因子
- 默认
loadFactor = 0.75
,可以适当调高(如0.9
)减少扩容,但可能增加哈希冲突。 - 适用于写少读多的应用,如缓存、只读字典表等。
- 默认
避免并发环境下使用 HashMap
- HashMap 线程不安全,扩容时可能导致死循环或数据丢失。
- 推荐使用
ConcurrentHashMap
,它采用分段扩容,避免全局 rehash。
# 深入追问
为什么 HashMap 扩容时选择 2 倍增长,而不是其他增长方式?
- 2 的幂次倍增可以确保
hash & (newCap - 1)
计算索引时无需取模,提高计算效率。 - 取模
%
操作在 CPU 上比位运算&
慢 10 倍以上。
- 2 的幂次倍增可以确保
扩容对 GC 有何影响?
- 由于数组对象是大对象,扩容时可能直接晋升到老年代,导致 Full GC,影响吞吐量。
- 解决方案:使用
-XX:+UseG1GC
,减少老年代 GC 影响。
ConcurrentHashMap 如何优化扩容?
- 采用分段扩容,避免全局锁,并发扩容时不同桶可以独立扩展。
- 采用
CAS + 迁移指针
进行渐进式扩容,不会一次性迁移所有数据。
# 相关面试题
- HashMap 为什么扩容必须是 2 的幂?
- HashMap 如何优化 rehash?
- ConcurrentHashMap 如何避免 HashMap 扩容引起的性能问题?