ConcurrentHashMap 设计原理笔记

在 Java 并发编程中ConcurrentHashMap是最常用的并发容器之一。它既要保证线程安全又要追求接近HashMap的高性能。本文将深入剖析ConcurrentHashMap的整体设计思路从数据结构、锁粒度、无锁读、CAS 无锁更新到多线程协助扩容带你领略并发容器设计的精妙之处。一、从 HashTable 到 ConcurrentHashMap在ConcurrentHashMap出现之前Hashtable是 Java 中唯一的线程安全哈希表。它的实现非常粗暴对所有方法如put、get都加上synchronized关键字整个表被一把大锁保护。在高并发场景下这把锁成为严重的性能瓶颈因为任何时刻只有一个线程能够访问哈希表。HashMap虽然性能高但非线程安全。于是Java 并发包推出了ConcurrentHashMap旨在解决以下问题细粒度锁将锁的粒度从整个表缩小到每个桶bucket。无锁读读操作不加锁只依赖volatile保证可见性。无锁更新对于简单的更新操作使用 CASCompare And Swap无锁算法替代加锁。多线程协助扩容将耗时的扩容操作分摊到多个线程降低单次扩容的停顿时间。二、核心设计理念ConcurrentHashMap的整体设计可以概括为降低锁粒度 无锁读 CAS 无锁更新 局部加锁1. 为什么读操作可以不加锁在实际应用中对哈希表的读操作远多于写操作。如果读操作也加锁性能会大幅下降甚至不如Hashtable。ConcurrentHashMap的读操作完全不加锁依靠volatile保证可见性。volatile的作用是可见性一个线程修改了volatile变量会立即刷新到主内存其他线程读取时会直接从主内存读取而不是自己的 CPU 缓存从而总是读到最新值。禁止指令重排序保证对象的构造过程不会提前将引用暴露出去避免读到半初始化对象。在ConcurrentHashMap中数组table是volatile的每个桶的节点Node的val和next也是volatile的。这样当读线程访问某个桶时它能看到最新的节点引用和值无需加锁。2. 如何降低锁粒度Hashtable的锁是整个对象而ConcurrentHashMap只锁住当前操作的桶bucket的头节点。每个桶对应一个Node链表的头节点或红黑树的根节点。当多个线程同时操作不同的桶时它们可以完全并发互不干扰。这种设计称为分段锁Segmented Locking在 Java 8 中进一步演进为锁桶Lock Striping锁的粒度更细并发度更高。3. 什么时候使用 CAS对于简单的、无需遍历链表的操作如初始化空桶更新计数器size修改sizeCtl扩容状态使用 CAS 可以避免加锁实现无锁更新进一步提升性能。4. 为什么采用多线程协助扩容扩容需要将旧数组中的元素重新哈希分配到新数组是一个耗时操作。如果单线程完成可能会造成长时间停顿。ConcurrentHashMap将扩容任务拆分成多个小任务允许其他线程在插入数据时“顺带”帮忙完成一部分迁移工作从而大幅减少整体扩容时间避免性能毛刺。三、数据结构演进Java 8 的优化Java 7 及之前的ConcurrentHashMap采用分段锁设计内部由多个Segment组成每个Segment独立加锁锁粒度较粗。Java 8 彻底重构采用数组 链表 红黑树的结构锁的粒度细化到每个桶的头节点。Java 8 的核心数据结构NodeK,V[] table哈希桶数组volatile修饰。Node节点包含hash、key、valvolatile和nextvolatile。当链表长度超过阈值TREEIFY_THRESHOLD 8且数组长度大于MIN_TREEIFY_CAPACITY 64时链表转为红黑树TreeNode以优化极端情况下的查找性能。ForwardingNode在扩容过程中用于标记已经被迁移的桶指向新数组。四、读操作get的实现get方法的流程如下public V get(Object key) { NodeK,V[] tab; NodeK,V e, p; int n, eh; K ek; int h spread(key.hashCode()); if ((tab table) ! null (n tab.length) 0 (e tabAt(tab, (n - 1) h)) ! null) { // 1. 检查头节点是否为目标节点 if ((eh e.hash) h) { if ((ek e.key) key || (ek ! null key.equals(ek))) return e.val; } // 2. 特殊节点如红黑树、迁移节点使用特殊查找 else if (eh 0) return (p e.find(h, key)) ! null ? p.val : null; // 3. 普通链表遍历 while ((e e.next) ! null) { if (e.hash h ((ek e.key) key || (ek ! null key.equals(ek)))) return e.val; } } return null; }无锁整个读过程没有任何synchronized或Lock。volatile保证table是volatile的Node的val和next也是volatile的所以即使没有锁也能读到最新值。特殊节点如果头节点的hash小于 0说明是红黑树节点TreeBin或扩容节点ForwardingNode会调用其find方法进行查找同样不加锁。由于读操作不加锁ConcurrentHashMap的并发读性能几乎与HashMap持平这是其设计的核心优势。五、写操作put的实现put方法的关键步骤简化final V putVal(K key, V value, boolean onlyIfAbsent) { if (key null || value null) throw new NullPointerException(); int hash spread(key.hashCode()); int binCount 0; for (NodeK,V[] tab table;;) { NodeK,V f; int n, i, fh; if (tab null || (n tab.length) 0) tab initTable(); // 1. 初始化数组CAS else if ((f tabAt(tab, i (n - 1) hash)) null) { // 2. 空桶CAS 直接插入新节点 if (casTabAt(tab, i, null, new NodeK,V(hash, key, value, null))) break; } else if ((fh f.hash) MOVED) // 3. 正在扩容协助扩容 tab helpTransfer(tab, f); else { V oldVal null; synchronized (f) { // 4. 锁住头节点 // 双重检查确保头节点未被修改 if (tabAt(tab, i) f) { if (fh 0) { // 普通链表 // 遍历链表找到插入位置或更新 // ... } else if (f instanceof TreeBin) { // 红黑树插入 // ... } } } // 5. 链表长度超过阈值转为红黑树 if (binCount ! 0) { if (binCount TREEIFY_THRESHOLD) treeifyBin(tab, i); break; } } } addCount(1L, binCount); // 6. 计数更新CAS return null; }初始化数组使用 CAS 保证只有一个线程能成功初始化table。空桶插入通过casTabAt原子地插入新节点无需加锁。非空桶对桶的头节点加锁synchronized (f)这样其他线程访问同一桶会被阻塞但不同桶的线程完全并发。红黑树同样加锁树节点的操作也在锁保护下进行。扩容协助如果检测到正在扩容当前线程会帮助迁移数据降低扩容总时间。这种设计使得写操作只在必要的时候加锁且锁的粒度非常小极大提升了并发写入能力。六、CAS 无锁更新的应用CASCompare And Swap是一种乐观锁技术它通过比较并交换的方式原子地更新变量避免加锁开销。在ConcurrentHashMap中CAS 被广泛应用于初始化数组sizeCtl通过 CAS 控制初始化状态。空桶插入casTabAt确保只有成功插入的线程才能创建节点。计数器更新使用LongAdder思想的CounterCell数组通过 CAS 更新计数值高并发下避免了竞争。修改 sizeCtl在扩容过程中sizeCtl用于控制扩容进度通过 CAS 修改其值。七、多线程协助扩容机制扩容是ConcurrentHashMap中最复杂的部分。Java 8 实现了并发扩容允许多个线程共同参与迁移大幅缩短扩容时间。1. 触发扩容的条件插入元素后链表长度超过阈值TREEIFY_THRESHOLD且数组长度小于MIN_TREEIFY_CAPACITY。元素个数超过sizeCtl即扩容阈值。2. 扩容的核心思想当需要扩容时首先计算新数组容量原数组的 2 倍。设置sizeCtl为一个负数表示正在扩容并记录参与扩容的线程数。创建ForwardingNode作为占位节点指向新数组。将旧数组的桶分配给不同的线程去迁移。每个线程负责一个“步长”stride的桶迁移完成后通过 CAS 修改transferIndex来获取下一个任务范围。线程在迁移某个桶时先对该桶的头节点加锁然后将其中的元素重新哈希分配到新数组的对应桶中。迁移完成后将桶设置为ForwardingNode后续的读写操作会通过该节点转发到新数组。3. 协助扩容当线程执行put时如果发现当前桶的头节点是ForwardingNode它会调用helpTransfer方法加入扩容队伍帮助迁移数据而不是傻傻等待。这种设计使得扩容不再是单线程的“stop-the-world”操作而是变成多线程并行执行整体扩容时间大幅缩短尤其在高并发场景下效果显著。八、计数机制LongAdder 思想ConcurrentHashMap需要知道当前元素个数size()且在高并发下计数必须准确。如果使用AtomicLong高并发 CAS 竞争会很激烈影响性能。Java 8 引入了LongAdder的思想将计数分散到多个CounterCell中每个线程通过 CAS 更新自己的计数器最后求和。这样减少了 CAS 冲突提高了计数性能。关键类baseCount基础的计数器。CounterCell[] counterCells辅助计数数组。cellsBusy自旋锁用于控制counterCells的初始化或扩容。当 CAS 更新baseCount失败时会尝试更新CounterCell若仍失败则扩容counterCells数组。最终size()返回baseCount加上所有CounterCell的值之和。九、总结ConcurrentHashMap通过一系列精妙的设计在保证线程安全的前提下提供了接近HashMap的读写性能。其设计精髓可以总结为无锁读借助volatile保证可见性读操作完全不加锁实现高并发读。细粒度锁锁的粒度从整个表缩小到每个桶的头节点并发写能力大幅提升。CAS 无锁更新对于简单的、无需遍历的操作使用 CAS 原子更新避免锁开销。多线程协助扩容将耗时的扩容任务拆分为多个子任务允许写线程帮忙迁移降低扩容停顿。高效计数采用LongAdder思想分散计数压力提升高并发下的计数性能。