ConcurrentHashMap在JDK1.8中的实现原理是什么？

<think>我们正在讨论ConcurrentHashMap在JDK1.8中的实现原理。在JDK1.8中，ConcurrentHashMap进行了重大改进，放弃了分段锁（Segment）的设计，转而采用更细粒度的桶（bucket）级别锁，并大量使用CAS操作来提升并发性能。 主要特点： 1. 数据结构：与HashMap类似，使用数组+链表/红黑树。当链表长度超过阈值（默认为8）时，链表会转换为红黑树；当红黑树节点数小于阈值（默认为6）时，会退化为链表。 2. 并发控制：使用CAS（Compare and Swap）和synchronized关键字。CAS用于无锁的更新操作（如初始化数组、更新节点等），而synchronized则用于锁定桶的头节点，这样锁的粒度更小，并发度更高。 具体实现原理： - 初始化：使用sizeCtl变量控制初始化和扩容状态，通过CAS设置sizeCtl来保证只有一个线程进行初始化。 - put操作： a. 如果数组为空，则先初始化数组（initTable）。 b. 计算key的hash值，定位到数组下标。如果该位置为空，则使用CAS尝试添加节点（如果CAS失败则重试）。 c. 如果该位置不为空（可能是链表或红黑树），则使用synchronized锁住头节点，然后进行插入或更新操作。 d. 插入后判断链表长度是否超过阈值，超过则转换为红黑树。 - get操作：无锁，因为节点的value和next都是volatile的，保证了可见性。 - size操作：使用一个CounterCell数组（类似LongAdder的分段计数）来减少竞争，提高并发性能。 下面我们通过代码来展示关键部分：</think>### ConcurrentHashMap 在 JDK 1.8 中的实现原理详解 ConcurrentHashMap 在 JDK 1.8 中进行了重大重构，抛弃了 JDK 1.7 的分段锁设计，采用了更高效、更细粒度的并发控制策略。以下是核心实现原理： #### 1. 底层数据结构 ```java // 核心数据结构 transient volatile Node<K,V>[] table; // 哈希表数组 private transient volatile int sizeCtl; // 控制标识符 private transient volatile CounterCell[] counterCells; // 并发计数 ``` - **数组 + 链表/红黑树**：与 HashMap 类似 - **Node 节点**：存储键值对，链表节点 - **TreeNode 节点**：红黑树节点（当链表长度 ≥ 8 时转换） - **ForwardingNode**：扩容时使用的特殊节点 #### 2. 核心并发控制机制 **CAS + synchronized 桶级锁**： ```java final V putVal(K key, V value, boolean onlyIfAbsent) { // ... for (Node<K,V>[] tab = table;;) { if (tab == null || (n = tab.length) == 0) tab = initTable(); // CAS初始化 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) break; // CAS添加新节点 } else { synchronized (f) { // 锁定桶的头节点 // 处理链表/红黑树插入 } } } // ... } ``` - **CAS 操作**： - 初始化哈希表（`initTable()`） - 添加新节点到空桶 - 更新 sizeCtl 控制变量 - **synchronized 锁**： - 锁定桶的头节点（非空桶操作） - 锁粒度 = 单个桶（哈希槽） #### 3. 扩容机制（多线程协同） ```java private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { // 每个线程处理一段桶区间 while (advance) { // 分配任务区间 [bound, i] } // 处理桶内节点 synchronized (f) { // 将节点迁移到新表 } // 设置ForwardingNode标识 setTabAt(tab, i, fwd); } ``` - **并行扩容**： - 线程协助迁移：当线程访问到 ForwardingNode 时参与扩容 - 任务分割：将哈希表划分为多个区间，不同线程处理不同区间 - **无锁查询**： - 扩容期间读操作无需加锁 - 通过 ForwardingNode 访问新表 #### 4. 计数机制（LongAdder 风格） ```java final long sumCount() { CounterCell[] as = counterCells; long sum = baseCount; if (as != null) { for (CounterCell a : as) { if (a != null) sum += a.value; } } return sum; } ``` - **分段计数**： - `baseCount`：基础计数值 - `CounterCell[]`：分段计数器数组 - **减少竞争**： - 更新时优先尝试 CAS 更新 baseCount - 竞争激烈时使用 CounterCell 分散更新 #### 5. 红黑树优化 ```java static final class TreeBin<K,V> extends Node<K,V> { TreeNode<K,V> root; volatile TreeNode<K,V> first; volatile int lockState; // 读写锁状态 // 读锁计数 static final int WAITER = 2; // 写等待 static final int WRITER = 1; // 写锁定 } ``` - **树桶锁**： - 使用读写锁状态（lockState）控制并发 - 读操作共享锁，写操作独占锁 - **链表化优化**： - 扩容时如果树节点 ≤ 6，退化为链表 ### 性能优势对比 JDK 1.7 | 特性 | JDK 1.7（分段锁） | JDK 1.8（CAS + synchronized） | |--------------|--------------------------|-------------------------------| | 锁粒度 | 段级别（默认16段） | 桶级别（哈希槽） | | 并发度 | 最大=段数 | 最大=桶数 | | 扩容机制 | 单线程扩容 | 多线程协同扩容 | | 计数实现 | 全局锁更新 | LongAdder 风格分段计数 | | 数据结构 | 数组+链表 | 数组+链表/红黑树 | | 内存消耗 | 较高（段对象开销） | 较低 | ### 关键设计思想图解 ```mermaid graph TD A[put操作] --> B{桶是否为空?} B -->|是| C[CAS添加新节点] B -->|否| D[synchronized锁桶头节点] D --> E{桶结构} E -->|链表| F[链表插入] E -->|红黑树| G[树插入] F --> H{长度≥8?} H -->|是| I[转为红黑树] G --> J[维护树结构] K[get操作] --> L[无锁访问] L --> M{桶结构} M -->|链表| N[遍历链表] M -->|红黑树| O[树查找] P[扩容] --> Q[设置ForwardingNode] Q --> R[多线程迁移数据] R --> S[完成扩容] ``` ### 总结 JDK 1.8 的 ConcurrentHashMap 通过以下创新实现高并发： 1. **细粒度锁**：桶级别锁（synchronized）替代分段锁 2. **CAS 优化**：无锁操作处理空桶添加和初始化 3. **协同扩容**：多线程并行迁移数据 4. **分段计数**：LongAdder 风格减少计数竞争 5. **读写分离**：红黑树桶使用读写状态控制 这种设计在保持线程安全的同时，大幅提升了并发性能，特别适合高并发场景。