说说ConcurrentHashMap 的实现方式（Segment 锁、CAS 乐观锁）？

# 一、JDK 7：Segment 分段锁 * **结构**：`Segment<K,V>[]` 数组（长度为 2 的幂），每个 Segment 内部是一个 **HashEntry\[]** + **ReentrantLock**。 * **并发粒度**：对同一 Segment 内写操作需要拿该段的锁；不同段可并行。 * **put 过程**（简化）： 1. 根据 key 计算 **段索引** 和 **桶索引**。 2. `scanAndLockForPut()` 获取该 Segment 的锁（自旋 + 挂起）。 3. 在该段的桶链表头插入 / 覆盖。 4. 若段内元素数超阈值则**仅对该段扩容**。 5. 释放锁。 * **get 过程**：无锁，只读 `volatile` 字段，沿链表查找（哈希碰撞时）。 * **size**：遍历各 Segment 的计数，多次重试；失败时加段锁做一次一致性统计。 * **特点**：实现简单、吞吐稳定，但**并行度受 Segment 数限制**（默认 16/并发级别）。 # 二、JDK 8+：无 Segment，CAS + 桶级锁（synchronized） * **结构**：直接用 `Node<K,V>[] table`。**不再有 Segment**。核心手段： * **CAS**：初始化表、桶头插入、计数单元更新等。 * **synchronized（极小粒度）**：只在**某个桶（bin）**非空时，对**该桶的头节点**加锁，完成链/树内的插入/替换/树化。 * **红黑树**：链表过长会**树化**为 `TreeBin`，降低最坏复杂度。 * **get 过程（无锁）**： 1. 读 `table`，定位桶 `bin`。 2. 桶为空返回 null；非空： * 头节点 key 相等直接返回； * 若是 `TreeBin`，走树查找； * 否则走链表 next。 > 全程只读 `volatile` 字段和 final 字段，**不加锁**。 * **put 过程（CAS + 桶级锁）**： 1. **表未初始化**：`initTable()` 用 **CAS** 初始化。 2. 定位桶： * 桶为空 → 用 **CAS 将新节点设为桶头**（无锁插入成功则结束）。 * 桶为**转移标记（ForwardingNode）** → 正在扩容，先**帮助扩容**（协作迁移），再重试。 * 否则对**桶头节点 `synchronized` 加锁**，在该桶（链/树）里插入或覆盖： * 链表：找到 key 相等则覆盖，否则尾插；**长度≥8 且表容量≥64 → 树化**。 * 树：按红黑树规则插/改。 3. 插入后 `addCount(1L)`：基于 **分片计数单元（类似 LongAdder）** + CAS 累加；必要时触发扩容。 * **扩容（并行 Rehash）**： * 阈值：`sizeCtl` 控制，达到阈值触发。 * 采用**协作迁移**：多个线程共同搬运桶到新表；被迁移过的桶设置 `ForwardingNode`，读写线程看到会**帮助迁移**或重试。 * **位迁移规则**：和 HashMap8 类似，按 `(hash & oldCap)` 将链拆为 **低位链/高位链**，顺序保持，避免重新计算 hash。 * **计数（size/sizeLong）**： * 平时走**分片计数**（Base + Cells），**无全局锁**。 * `mappingCount()`/`size()` 在并发下是**近似值**；`size()`会尝试两次不加锁采样，不稳则退化一次全表遍历。 * **红黑树（TreeBin）**： * 桶内链表长度 ≥ **8** 且表容量 ≥ **64** → 转为 `TreeBin`（红黑树包装）。 * 之后在该桶内查找/插入/删除为 **O(log n)**（n 为该桶元素数）。 * 节点减少到 ≤ **6** → 退化回链表，避免树常数开销。 * **为什么要用 synchronized 而不是 ReentrantLock？** * 作用域仅限**单个桶**，持锁时间极短；`synchronized` 省内存、JIT 优化成熟（偏向/轻量级锁在低竞争下开销更小）。 * **不支持 null key/value**：避免并发下不可区分“缺失 vs 映射到 null”的语义歧义。 # 三、两代实现的对比总结 | 版本 | 并发粒度 | 写时加锁 | 结构 | 扩容 | 复杂度保障 | | ---------- | --------- | -------------------------- | --------------------------- | ---------- | ------------- | | **JDK 7** | Segment 级 | `ReentrantLock`（段锁） | `Segment[]` + `HashEntry[]` | **分段扩容** | 链表，最坏桶内 O(n) | | **JDK 8+** | 桶级（bin） | CAS + bin 头 `synchronized` | `Node[]`（链/树） | **协作并行扩容** | 桶内树化 O(log n) | # 四、关键词快速回答（面试秒答版） * **实现方式**：JDK7 用 **Segment 分段锁**；JDK8 起改为 **CAS + 桶级 synchronized**，并引入**红黑树**优化冲突桶。 * **为何高并发**：读**无锁**，写只锁**单个桶**，大量使用 **CAS** 与 **分片计数**；扩容**多线程协作**。 * **树化阈值**：链长 **≥8** 且容量 **≥64** 才树化；≤6 退化回链表。 * **复杂度**：平均 **O(1)**，冲突严重时桶内 **O(log n)**（树化后），极端情况下仍可避免 O(n) 的灾难。