Java 8 ConcurrentHashMap 多线程并发扩容实现详解

### Java 8 `ConcurrentHashMap` 多线程并发扩容实现详解 --- #### **一、扩容触发条件** 1. **元素数量阈值** 当哈希表元素数量超过 `容量 × 负载因子`（默认负载因子为 0.75）时触发扩容。 2. **链表长度限制** 若链表长度超过 8 且数组容量 ≥64，链表会转换为红黑树；若扩容后哈希冲突减少，可能触发树退化为链表。 --- #### **二、扩容核心流程** 1. **初始化新数组** • 创建新数组，容量为旧数组的 2 倍。 • 通过 `sizeCtl` 标记扩容状态（负数表示正在扩容）。 2. **任务分配与多线程协作** • **步长划分**：将旧数组划分为多个连续区间（每个线程默认处理 16 个桶）。 • **线程协助机制**： ◦ 其他线程在执行插入、删除操作时，若发现当前桶已迁移（标记为 `ForwardingNode`），则主动加入迁移任务。 ◦ 通过 `transferIndex` 全局变量动态分配任务区间，确保线程间无冲突。 3. **数据迁移逻辑** • **链表拆分**：根据哈希值高位将旧桶拆分为高低位链表，分别迁移到新数组的 `i` 和 `i + oldCap` 位置。 • **树化处理**：若迁移后的链表长度超过阈值，转换为红黑树；反之退化为链表。 • **标记迁移完成**：已迁移的桶用 `ForwardingNode` 标记，后续操作直接跳转至新数组。 4. **状态更新与清理** • 所有线程完成迁移后，用新数组替换旧数组，并更新 `sizeCtl` 为新容量的阈值。 --- #### **三、关键设计要点** 1. **并发安全机制** • **CAS 操作**：用于设置 `sizeCtl`、`transferIndex` 等全局变量，保证原子性。 • **细粒度锁**：迁移时仅对当前桶的头节点加 `synchronized` 锁，其他桶仍可并发访问。 2. **高效协作策略** • **渐进式扩容**：扩容与读写操作并行，避免阻塞用户线程。 • **多线程负载均衡**：通过步长分配任务，减少线程竞争，充分利用多核性能。 3. **状态标记与容错** • `ForwardingNode`：标识已迁移的桶，引导操作转向新数组。 • **中断恢复**：若线程迁移过程中异常退出，其他线程会接管剩余任务。 --- #### **四、背诵方法与重点** 1. **流程记忆口诀** ``` 触发扩容 → 新数组初始化 → 分配任务步长 → 迁移高低链表 → 标记完成 → 替换数组。 ``` 2. **核心要点提炼** • **触发条件**：元素数超阈值，树化需扩容。 • **线程协作**：步长分配 + ForwardingNode 引导协助。 • **数据迁移**：高低位拆分，树化退化灵活处理。 • **状态控制**：sizeCtl 标记扩容，CAS 保证原子性。 3. **源码关键方法** • `transfer()`：核心迁移逻辑。 • `helpTransfer()`：线程协助迁移入口。 • `addCount()`：触发扩容检查。 4. **对比 Java 7 与 8** • Java 7：分段锁扩容，全局锁竞争高。 • Java 8：桶粒度锁 + 多线程协同，性能更优。 --- #### **五、流程图辅助记忆** ```plaintext 触发扩容 → 新数组创建 → 分配任务区间（transferIndex） ↓ 线程迁移旧桶（拆分为高低链表） → 标记为 ForwardingNode ↓ 其他线程协助迁移（遇到 ForwardingNode 则加入） ↓ 全部迁移完成 → 替换新数组 → 更新 sizeCtl ```