一篇文章了解HashMap和ConcurrentHashMap的扩容机制

HashMap

HashMap 是 Java 中常用的哈希表实现，其扩容机制是保证其高效性能的关键部分。JDK 1.8 对 HashMap 的扩容机制做了较大优化，下面详细解析其扩容过程：

1. 扩容的触发条件

当 HashMap 中的元素数量（size）超过阈值（threshold）时，会触发扩容。

• 阈值计算公式：threshold = capacity × loadFactor
• 默认初始容量（capacity）为 16，负载因子（loadFactor）为 0.75
• 每次扩容时，容量会变为原来的 2 倍（保证容量始终是 2 的幂）

2. 扩容的核心步骤

（1）创建新数组

新建一个容量为原数组 2 倍的数组（newTab）

（2）数据迁移

将原数组（oldTab）中的数据迁移到新数组中，这是扩容的核心操作：

JDK 1.8 采用了更高效的迁移方式：

// 原位置计算
int oldIndex = e.hash & (oldCap - 1);
// 新位置计算（两种可能）
int newIndex = (oldCap & e.hash) == 0 ? oldIndex : oldIndex + oldCap;

这种计算方式的优势：

• 无需重新计算哈希值
• 元素要么留在原索引位置，要么迁移到 原索引+旧容量 的位置
• 避免了 JDK 1.7 中重新哈希带来的性能损耗

（3）处理链表和红黑树

• 链表迁移：将链表拆分为两个子链表，分别放入新数组的两个可能位置
• 红黑树迁移：
  • 当树节点数小于 6 时，会退化为链表
  • 否则会将红黑树拆分为两个子树，可能是红黑树或链表

（4）更新参数

• 更新容量为新容量
• 重新计算阈值（新容量 × 负载因子）
• 将新数组设置为 HashMap 的 table 属性

3. 扩容的优缺点

优点：

• 采用 2 倍扩容，保证容量始终是 2 的幂，使得哈希计算更高效（位运算）
• 迁移算法优化，减少了哈希冲突的概率
• 红黑树的引入避免了极端情况下链表过长导致的性能下降

缺点：

• 扩容过程需要复制所有元素，耗时较长
• 并发环境下可能导致死循环（JDK 1.7），JDK 1.8 已修复但仍不建议并发使用

4. 扩容机制的注意事项

• 初始容量选择：如果预知数据量较大，可指定合适的初始容量减少扩容次数
• 负载因子调整：对迭代性能要求高时可降低负载因子，牺牲空间换时间
• 线程安全：HashMap 扩容过程中不保证线程安全，多线程环境下建议使用 ConcurrentHashMap

ConcurrentHashMap

ConcurrentHashMap 是 Java 中线程安全的哈希表实现，其扩容机制在保证线程安全的同时，也兼顾了高效性。相比 HashMap，ConcurrentHashMap 的扩容过程更为复杂，下面详细解析其 JDK 1.8 及以上版本的扩容机制：

1. 扩容的触发条件

当 ConcurrentHashMap 满足以下任一条件时，会触发扩容：

• 元素数量（size）超过阈值（threshold = 容量 × 负载因子）
• 某个链表长度达到 8 且数组长度小于 64 时，先扩容而非树化

2. 扩容的核心机制

ConcurrentHashMap 采用分段扩容（增量扩容）策略，允许多个线程同时参与扩容，避免了单线程扩容的性能瓶颈。

（1）扩容准备

1. 计算新容量（原容量的 2 倍）
2. 创建新数组（nextTable）
3. 设置扩容标记（sizeCtl = -1 表示正在扩容）
4. 确定每个线程负责迁移的桶范围

（2）迁移过程（核心步骤）

1. 分配迁移任务：

   • 每个线程通过 CAS 操作认领一段连续的桶进行迁移
   • 用 i 表示当前迁移的桶索引，bound 表示迁移结束的边界
   • 迁移完成后更新 transferIndex 分配新的任务段

2. 元素迁移：
   对每个桶中的元素（链表或红黑树）进行迁移：

   // 计算元素在新数组中的位置
   int newIndex = (node.hash & (newCap - 1));
   // 红黑树迁移
   if (node instanceof TreeBin) {// 拆分红黑树并迁移
   } else {// 链表迁移，保持原有顺序// 分为低位链表和高位链表
   }
   

3. 迁移完成标记：

   • 当所有桶迁移完成后，将 nextTable 设置为新的 table
   • 更新容量和阈值，重置 sizeCtl 为新的阈值

3. 线程协作机制

• 扩容线程：发现需要扩容时，主动参与迁移工作
• 读写线程：
  • 读操作：如果遇到正在迁移的桶，会读取旧表和新表中的数据
  • 写操作：
    • 对已迁移的桶：直接操作新表
    • 对未迁移的桶：先协助完成迁移，再执行写操作

这种协作机制避免了扩容时的线程阻塞，提高了并发效率。

4. 扩容中的线程安全保障

1. CAS 操作：用于设置扩容标记、分配迁移任务等
2. synchronized 锁：迁移时锁定当前桶，防止并发修改
3. volatile 变量：sizeCtl、nextTable 等关键变量用 volatile 修饰，保证可见性
4. 节点标记：迁移中的节点会被标记为 forwardNode，指引线程访问新表

5. 扩容机制的优缺点

优点：

• 支持多线程并发扩容，提高扩容效率
• 扩容过程中不阻塞读写操作，保证高并发性能
• 采用增量迁移，避免单线程长时间占用 CPU

缺点：

• 实现复杂，增加了代码维护难度
• 迁移过程中可能出现短暂的内存占用增加（同时存在新旧两个数组）

两者对比