HashMap 扩容时出现的各种问题及解决方案
一、前言
HashMap 是 Java 中最常用的集合类之一，它基于哈希表实现，提供了 O(1) 时间复杂度的键值对存取。然而，HashMap 的扩容机制是其设计的核心难点，也是各种并发问题的根源。本文将深入分析 HashMap 的扩容机制，对比 JDK 7 和 JDK 8 的实现差异，并重点剖析并发场景下扩容导致的问题（死循环、数据丢失等）以及如何避免。
二、HashMap 基础结构
2.1 数据结构
HashMap 底层采用 数组 + 链表（或红黑树） 的混合结构：
- 数组（table）：每个元素称为桶（bucket）或槽（slot）
- 链表：解决哈希冲突，多个 key 落在同一桶时，以链表形式存储
- 红黑树（JDK 8+）：当链表长度超过阈值（默认 8）时，转换为红黑树以提升查找性能
// JDK 8 核心字段
public class HashMap<K,V> extends AbstractMap<K,V> {
// 底层数组，长度始终为 2 的幂
transient Node<K,V>[] table;
// 阈值 = capacity * loadFactor，当 size > threshold 时触发扩容
int threshold;
// 负载因子，默认 0.75
final float loadFactor;
// 链表树化的阈值，默认 8
static final int TREEIFY_THRESHOLD = 8;
// 树退化为链表的阈值，默认 6
static final int UNTREEIFY_THRESHOLD = 6;
// 树化时数组的最小长度，默认 64
static final int MIN_TREEIFY_CAPACITY = 64;
}
2.2 扩容机制概览
当 HashMap 中存储的元素数量（size）超过 threshold（capacity × loadFactor）时，会触发 resize（扩容） 操作。扩容过程如下：
- 新建一个容量为原来 2 倍 的新数组
- 将原数组中的所有元素重新计算哈希索引，迁移到新数组
- 更新
threshold为新容量 ×loadFactor
三、JDK 7 的扩容实现
3.1 transfer() 方法
JDK 7 的扩容核心在 transfer() 方法中，它遍历每个桶中的链表，使用头插法将节点迁移到新数组：
// JDK 7 HashMap.transfer() — 简化伪代码
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) { // 遍历每个桶
while (null != e) { // 遍历链表
Entry<K,V> next = e.next; // ① 保存下一个节点
int i = indexFor(e.hash, newCapacity); // 计算新索引
e.next = newTable[i]; // ② 头插法：e.next 指向桶的当前头节点
newTable[i] = e; // ③ e 成为新的头节点
e = next; // ④ 处理下一个节点
}
}
}
3.2 头插法的特点
头插法意味着在迁移链表时，会将原链表的节点依次插入到新桶的头部，这会导致 链表反转：
原链表：A → B → C
迁移过程（头插）：
step1: newTable[i] = A → null
step2: newTable[i] = B → A → null
step3: newTable[i] = C → B → A → null
最终链表：C → B → A（反转了！）
3.3 扩容阈值计算
// JDK 7 构造函数
public HashMap(int initialCapacity, float loadFactor) {
// 找到大于等于 initialCapacity 的最小的 2 的幂
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY);
}
四、JDK 8 的扩容实现 — 重要改进
4.1 resize() 方法
JDK 8 对扩容进行了重大重构，使用 尾插法（或更准确地说是拆分链表），并且引入了红黑树的处理：
// JDK 8 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;
// 1. 计算新容量和阈值
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量翻倍
newCap = oldCap << 1;
newThr = oldThr << 1; // 阈值也翻倍
} else if (oldThr > 0) {
newCap = oldThr;
} else {
newCap = DEFAULT_INITIAL_CAPACITY; // 16
newThr = (int)(newCap * DEFAULT_LOAD_FACTOR); // 12
}
// 2. 创建新数组
Node<K,V>[] newTab = (Node<K,V>[]) new Node[newCap];
table = newTab;
// 3. 迁移数据
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e = oldTab[j];
if (e != null) {
oldTab[j] = null; // 帮助 GC
if (e.next == null) {
// 情况1：只有一个节点，直接计算新索引
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) {
// 情况2：红黑树节点 → 拆分红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
} else {
// 情况3：普通链表 → 拆分为高低位两个链表（尾插）
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 关键：利用 (e.hash & oldCap) == 0 判断是否移动
if ((e.hash & oldCap) == 0) {
// 低位链表（索引不变）
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
// 高位链表（索引 = 原索引 + oldCap）
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
e = next;
} while (e != null);
// 将两个链表放到新数组对应位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
4.2 低位 / 高位拆分原理
JDK 8 利用容量是 2 的幂 这个特性，通过 (e.hash & oldCap) 判断节点在新数组中的位置：
e.hash & oldCap |
含义 | 新索引 |
|---|---|---|
== 0 |
低位 | 原索引 j |
== 1 |
高位 | 原索引 j + oldCap |
为什么可以这样判断？
因为扩容后数组长度翻倍，哈希值对应的掩码多了一位。oldCap 正好是新增的最高位的权值。例如旧容量 16（二进制 10000），新容量 32（二进制 100000），e.hash & oldCap 就是在检查哈希值的第 5 位是否为 1。
旧索引计算：e.hash & (16 - 1) = e.hash & 1111
新索引计算：e.hash & (32 - 1) = e.hash & 11111
= e.hash & 01111 | e.hash & 10000
= (原索引) | (oldCap 位)
4.3 使用尾插法避免死循环
JDK 8 使用 尾插法（维护 loTail/hiTail 指针），保持了链表原有的顺序，不会产生反转。这从根本上避免了 JDK 7 头插法在并发时产生的循环链表问题。
五、JDK 7 vs JDK 8 扩容对比总结
| 对比项 | JDK 7 | JDK 8 |
|---|---|---|
| 插入方式 | 头插法（链表反转） | 尾插法（保持顺序） |
| 数据迁移 | 遍历链表逐个 rehash | 拆分低位/高位链表 |
| 树化 | ❌ 仅链表 | ✅ 链表长度 ≥ 8 转红黑树 |
| 并发安全 | ❌ 死循环、数据丢失 | ❌ 仍会数据丢失/覆盖 |
| rehash 计算 | hash & (newCap - 1) |
(e.hash & oldCap) == 0 判断 |
| 扩容后顺序 | 反转 | 不变（低位）/ 后移（高位） |
六、树化（Treeification）机制
6.1 为什么需要树化？
当哈希冲突严重时，链表长度会变得很长，查找时间复杂度退化为 O(n)。红黑树可以将查找时间复杂度降低到 O(log n)。
6.2 树化条件
// 两个条件必须同时满足：
// 条件1：链表长度 ≥ TREEIFY_THRESHOLD（默认 8）
// 条件2：数组容量 ≥ MIN_TREEIFY_CAPACITY（默认 64）
if (binCount >= TREEIFY_THRESHOLD - 1) // binCount 从 0 开始
treeifyBin(tab, hash);
为什么选择 8？ 官方注释给出了解释：在随机哈希码下，链表长度服从泊松分布，长度为 8 的概率极小（约 0.00000006）。选择 8 作为阈值是在时间和空间上权衡的结果。
6.3 扩容时红黑树的处理
JDK 8 中，如果某个桶是红黑树结构，扩容时会调用 split() 方法将红黑树拆分为低位和高位两部分。如果拆分后的子树长度小于 UNTREEIFY_THRESHOLD（6），会退化为链表。
// TreeNode.split() — 简化逻辑
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> loHead = null, loTail = null; // 低位树
TreeNode<K,V> hiHead = null, hiTail = null; // 高位树
// 遍历红黑树节点，根据 (e.hash & bit) 拆分为两个双向链表
// ...
// 如果低位头节点不为空
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) // 长度 ≤ 6，退化为链表
tab[index] = loHead.untreeify(map);
else
tab[index] = loHead;
}
// 高位同理
}
七、并发扩容问题详解
7.1 JDK 7 并发死循环 — 经典 Bug
这是 Java 社区最著名的并发 Bug 之一，由 头插法 + 多线程并发 resize 导致。
场景：两个线程 A 和 B 同时触发扩容，操作同一个链表。
发生步骤：
- 线程 B 在
transfer()中执行到Entry<K,V> next = e.next;后被挂起 - 线程 A 完成完整的扩容，链表被反转
- 线程 B 恢复执行，使用已经反转的链表继续头插法迁移
- 形成循环链表：节点 A.next = B, B.next = A
- 后续对 HashMap 的任何 get/put 操作都可能陷入无限循环
初始链表（桶中）：A → B → null
线程A 完成扩容后（头插法反转）：C → B → A → null
线程B 继续执行时的引用状态：
e = A (原头)
next = B (原 A.next)
但此时链表已经被线程A反转了，B 变成了：
next = B
e = A (此时 A.next 指向 B？还是 null？取决于时序)
在这种混乱状态下，可能出现：
A.next = B, B.next = A → 循环链表！
实际案例复现（经典 JDK 7 代码）：
// JDK 7 下运行 — 可能触发死循环
final HashMap<Integer, String> map = new HashMap<>(2);
Thread t1 = new Thread(() -> {
for (int i = 0; i < 10000; i++) {
map.put(i, String.valueOf(i));
}
});
Thread t2 = new Thread(() -> {
for (int i = 10000; i < 20000; i++) {
map.put(i, String.valueOf(i));
}
});
t1.start();
t2.start();
t1.join();
t2.join();
// 此时 HashMap 内部可能已经形成循环链表
// 调用 map.get(key) 很可能导致 CPU 100% 死循环
7.2 JDK 8 的改进与残留问题
JDK 8 虽然通过尾插法解决了死循环问题，但并发场景下仍然存在数据丢失和覆盖的问题：
问题 1：数据覆盖
// JDK 8 HashMap.putVal() — 并发场景
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // ① 两个线程同时走到这里！
else {
// ...
}
}
当两个线程同时判断 tab[i] 为 null，并同时执行 newNode 赋值，后赋值的会覆盖先赋值的，导致数据丢失。
问题 2：扩容时数据丢失
并发 resize 时，多个线程同时创建新数组并进行数据迁移。线程 A 迁移完成后赋值给 table，线程 B 随后也完成迁移，覆盖掉线程 A 的结果。更严重的是，线程 B 使用的可能是旧数组的引用，导致部分数据永久丢失。
// resize() 最后 — 并发覆盖
table = newTab; // 线程A: table = newTab_A
// 线程B: table = newTab_B ← 覆盖了 A 的结果
7.3 JDK 8 中仍然可能存在的死循环
虽然 JDK 8 解决了经典的 resize 死循环，但在 红黑树操作 中仍然可能存在死循环（虽然概率极低）：
// TreeNode 在并发 put 时可能破坏红黑树结构
// 导致 treeify() 或 balanceInsertion() 进入无限循环
// 这是 JDK 8 中已知的 Bug — JDK-8175105 等
实际上，JDK 8 中 HashMap.computeIfAbsent 也曾报告过死循环问题（JDK-8071667），在并发场景下 TreeNode 的树化过程可能出现环形父节点引用。
八、如何避免 HashMap 的并发问题
方案一：使用 ConcurrentHashMap（推荐）
ConcurrentHashMap 是专为并发设计的哈希表实现，内部通过 分段锁（Segment，JDK 7）或 CAS + synchronized（JDK 8+）保证线程安全。
// JDK 8 ConcurrentHashMap 推荐
ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
// 并发安全，性能优秀
map.put("key", "value");
map.get("key");
方案二：使用 Collections.synchronizedMap()
返回一个线程安全的包装类，所有方法都通过 synchronized 块同步：
Map<String, String> map = Collections.synchronizedMap(new HashMap<>());
// 注意：迭代时需要外层同步
synchronized (map) {
for (Map.Entry<String, String> entry : map.entrySet()) {
// ...
}
}
方案三：使用 HashTable（不推荐）
HashTable 是线程安全的，但所有方法都加 synchronized，性能较差，已经不推荐使用。
方案四：预先设置合理容量避免扩容
// 如果已知数据量，预先指定容量避免频繁扩容
int expectedSize = 10000;
// 避免扩容：capacity = expectedSize / loadFactor + 1
int capacity = (int) (expectedSize / 0.75f) + 1;
HashMap<String, String> map = new HashMap<>(capacity);
方案五：使用 Guava 的 Maps.newHashMapWithExpectedSize()
// Guava 工具类 — 自动计算合理初始容量
Map<String, String> map = Maps.newHashMapWithExpectedSize(10000);
方案六：扩容过程中禁止并发操作
在需要保证数据一致性的场景，使用显式锁或读写锁控制：
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
private HashMap<String, String> map = new HashMap<>();
public void put(String key, String value) {
lock.writeLock().lock();
try {
map.put(key, value);
} finally {
lock.writeLock().unlock();
}
}
九、面试高频问题
Q1：为什么 HashMap 的容量必须是 2 的幂？
答：为了保证 (n - 1) & hash 能均匀分布。如果 n 是 2 的幂，n - 1 的二进制全是低位 1，与哈希值做与运算等价于取模，且效率更高。如果不是 2 的幂，某些位永远为 0，会导致哈希冲突增加。
Q2：JDK 8 为什么要引入红黑树？
答：当哈希冲突严重时，链表长度 O(n) 会严重降低性能。红黑树的查找时间复杂度为 O(log n)，在极端哈希冲突情况下显著提升性能。同时，通过 TREEIFY_THRESHOLD=8 和泊松分布的考量，在正常场景下几乎不会触发树化，不影响常规性能。
Q3：JDK 8 的扩容为什么是线程不安全的？
答：resize() 方法没有加任何同步措施。多线程并发时可能出现：
- 多个线程同时创建新数组，互相覆盖
- put 操作时
(p = tab[i]) == null判断为非原子操作，导致数据覆盖丢失 - 扩容和新 put 操作交替执行，数据丢失或索引错乱
Q4：JDK 8 还有死循环问题吗？
答：JDK 8 使用尾插法解决了因链表反转导致的 resize 死循环。但并发场景下仍然不安全，可能出现数据丢失、put 返回 null 等问题。且在极少数情况下，并发操作红黑树仍可能引发死循环或 ConcurrentModificationException。
十、总结
| 版本 | 扩容策略 | 并发安全性 | 主要风险 |
|---|---|---|---|
| JDK 7 | 头插法 + 逐个 rehash | ❌ | 死循环、数据丢失 |
| JDK 8 | 尾插法 + 高低位拆分 | ❌ | 数据覆盖、丢失 |
| ConcurrentHashMap | CAS + 细粒度锁 | ✅ | — |
核心结论：
- 永远不要在并发场景下直接使用 HashMap，无论是 JDK 7 还是 JDK 8
- 并发场景请使用
ConcurrentHashMap，它在 JDK 8 中的性能已经非常优秀 - 了解 HashMap 的扩容机制有助于写出更好的单线程代码（合理设置初始容量、选择合适的负载因子）
- JDK 8 的尾插法 + 高低位拆分 + 红黑树是对 JDK 7 的重大改进，但也引入了新的复杂度
附录：关键源码参考
JDK 8 HashMap.resize() 完整流程：
resize()
├── 计算新容量 newCap 和阈值 newThr
│ ├── oldCap > 0 → 翻倍
│ ├── oldThr > 0 → 使用 oldThr
│ └── 默认 → 16 / 12
├── 创建新数组 New Node[newCap]
├── 遍历旧数组
│ ├── 空桶 → 跳过
│ ├── 单节点 → 直接 rehash 放入
│ ├── 红黑树 → split() 拆分
│ └── 链表 → 拆分为 lo/hi 两个链表
└── table = newTab
参考资源：
- JDK 源码：
java.util.HashMap（JDK 7 / JDK 8 / JDK 11+）- 《Java 并发编程的艺术》 — 方腾飞
- JDK Bug 数据库：JDK-8071667, JDK-8175105