YCBlogs 并发源码剖析：ConcurrentHashMap 的 CAS+Synchronized 实现、扩容与红黑树机制详解

• 教程
• 技术博客
• 文档

本篇文章是 YCBlogs 技术博客仓库中《ConcurrentHashMap 源码分析（下）》的完整展开，聚焦 JDK 1.8 中 ConcurrentHashMap 的内部结构、构造函数、延迟初始化、put 并发插入、扩容、链表转红黑树与 get 读取的全链路源码。读完本文，你将彻底理解"CAS 无锁 + 节点级 synchronized 细粒度锁"这套并发设计是如何保证线程安全与高吞吐并存的，并能直接应用到高并发缓存、本地注册表等共享 Map 场景的选型与调优中。

01. 背景：为什么需要 ConcurrentHashMap

1.1 效率低下的 HashTable

HashTable 容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下效率非常低下。因为当一个线程访问 HashTable 的同步方法时，其他线程访问 HashTable 的同步方法时可能会进入阻塞或轮询状态。例如线程 1 使用 put 添加元素，线程 2 不但不能使用 put 方法添加元素，也不能使用 get 方法来获取元素，竞争越激烈效率越低。

本质原因在于：HashTable 是对整个 table 加一把全局对象锁，多线程读写时每次只能有一个线程持有锁，其余线程全部等待，高并发下容器访问被彻底串行化。

1.2 线程不安全的 HashMap

HashMap 是非线程安全的，在涉及多线程并发 put 时可能引发死循环，导致 CPU 利用率接近 100%。仓库《Java 数据结构问题》中给出了经典复现场景：

final HashMap<String, String> map = new HashMap<String, String>(2); for (int i = 0; i < 10000; i++) { new Thread(new Runnable() { @Override public void run() { map.put(UUID.randomUUID().toString(), ""); } }).start(); }

原因在于：多线程环境下多个线程同时触发 rehash（扩容），可能导致链表成环（循环链表），一旦出现，线程将无法终止，持续占用 CPU。解决方案有 HashTable 与Collections.synchronizedMap(hashMap)，但两者本质上都是对整体读写加锁，一个线程在读写元素时其余线程必须等待，性能依然堪忧。

正是为了同时解决"线程安全"与"并发效率"这两个问题，Doug Lea 设计了 ConcurrentHashMap，其并发实现依赖 Java 内存模型、CAS、AQS/ReentrantLock 等底层知识，可对照仓库 java/07.Java并发/15.atomic原子操作类.md（CAS 详解）、java/07.Java并发/11.volatile原理深度分析.md（内存可见性）、java/07.Java并发/04.Synchronize细说.md（synchronized 原理）一并阅读。

02. JDK 1.6 与 JDK 1.8 的演进对比

2.1 JDK 1.6：分段锁机制

JDK 1.6 的 ConcurrentHashMap 采用**分段锁（Segment）**机制实现并发更新，底层为数组 + 链表结构。其核心是两个静态内部类：

• Segment：继承 ReentrantLock，充当锁的角色，每个 Segment 对象守护散列映射表的若干个桶；
• HashEntry：封装映射表的键 / 值对，每个桶由若干个 HashEntry 对象链接成链表。

一个 ConcurrentHashMap 实例包含若干个 Segment 对象组成的数组，put 时根据hash(paramK.hashCode())决定放入哪个 Segment，只锁住目标 Segment，从而把"锁整个 Map"细化为"锁其中一段"，显著提升了并发度。需要注意：size()与containsValue()等跨段操作需要按顺序锁定所有段再按顺序释放，顺序至关重要，否则极易产生死锁（段数组及其成员变量均为 final，保证获得锁的顺序固定）。

2.2 JDK 1.8：CAS + Synchronized

JDK 1.8 的实现抛弃了 Segment 分段锁机制，利用CAS + Synchronized保证并发更新的安全，底层依然采用数组 + 链表 + 红黑树的存储结构。详细演进说明参见仓库 java/04.数据结构/17.ConcurrentHashMap1.md。

03. 核心成员变量与重要概念

在进入源码之前，先明确 ConcurrentHashMap 的几个关键成员（详见 java/04.数据结构/17.ConcurrentHashMap1.md）：

其中sizeCtl是并发控制的核心状态位，不同取值含义如下：

• -1：代表 table 正在初始化；
• -N：表示有 N-1 个线程正在进行扩容操作；
• 其余情况：
  • 如果 table 未初始化，表示 table 需要初始化的大小；
  • 如果 table 初始化完成，表示 table 的容量阈值，默认是 table 大小的 0.75 倍，用n - (n >>> 2)计算。

3.1 Node 节点

保存 key、value 及 key 的 hash 值的数据结构，其中 value 和 next 都用volatile修饰，保证并发的可见性：

class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; // ... 省略部分代码 }

3.2 ForwardingNode 节点

一个特殊的 Node 节点，hash 值为 -1（即MOVED），其中存储 nextTable 的引用。只有 table 发生扩容时 ForwardingNode 才会发挥作用，作为占位符放在 table 中，表示当前节点为 null 或已经被移动：

final class ForwardingNode<K,V> extends Node<K,V> { final Node<K,V>[] nextTable; ForwardingNode(Node<K,V>[] tab) { super(MOVED, null, null, null); this.nextTable = tab; } }

04. 构造函数与实例初始化

4.1 带参构造与 tableSizeFor

实例化 ConcurrentHashMap 时带参数，会根据参数调整 table 的大小。例如参数为 100，最终会调整成 256，确保 table 的大小总是 2 的幂次方：

ConcurrentHashMap<String, String> hashMap = new ConcurrentHashMap<>(100); private static final int tableSizeFor(int c) { int n = c - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

该算法通过 5 次无符号右移 + 或运算，把最高位 1 之后的低位全部填充为 1，最终n + 1得到不小于传入容量的最小 2 的幂。这与 HashMap 的tableSizeFor完全一致，可对照 java/04.数据结构/07.HashMap源码深度分析.md 中的构造函数部分。

注意：ConcurrentHashMap 在构造函数中只会初始化 sizeCtl 值，并不会直接初始化 table，而是延缓到第一次 put 操作。

05. table 初始化 initTable()

前面提到，table 初始化操作会延缓到第一次 put。但 put 是可以并发执行的，Doug Lea 是如何保证 table 只初始化一次的？核心思路是：用 CAS 抢占 sizeCtl 把它置为 -1，抢到的线程负责初始化，其余线程让出 CPU。源码如下：

private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { // 如果一个线程发现 sizeCtl < 0，意味着另外的线程执行 CAS 操作成功， // 当前线程只需要让出 cpu 时间片 if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if ((tab = table) == null || tab.length == 0) { int n = (sc > 0) ? sc : DEFAULT_CAPACITY; @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = tab = nt; sc = n - (n >>> 2); } } finally { sizeCtl = sc; } break; } } return tab; }

关键点解读：

• sizeCtl默认为 0；如果实例化时传了参数，sizeCtl会是一个 2 的幂次方的值（由tableSizeFor计算而来）。
• 执行第一次 put 的线程会调用Unsafe.compareAndSwapInt把 sizeCtl 从当前值修改为 -1，有且只有一个线程能够修改成功，其余线程通过Thread.yield()让出 CPU 时间片等待 table 初始化完成。
• 初始化时若sc > 0使用指定容量，否则用DEFAULT_CAPACITY（默认 16）；初始化完成后把sizeCtl更新为n - (n >>> 2)，即新容量的 0.75 倍，作为扩容阈值。
• finally中统一写回 sizeCtl，保证异常时也不会把状态卡死在 -1。

06. put 插入数据操作：CAS + Synchronized

假设 table 已经初始化完成，put 操作采用CAS + synchronized实现并发插入或更新：

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 (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); // ...省略部分代码 } addCount(1L, binCount); return null; }

整个流程可拆解为六步：

1. hash 算法（扰动函数）

static final int spread(int h) { return (h ^ (h >>> 16)) & HASH_BITS; }

将 hashCode 的高 16 位与低 16 位异或，再与HASH_BITS（去掉符号位）相与，让高位信息参与低位运算，降低哈希碰撞概率，使数据分布更均匀。

2. table 中定位索引位置

int index = (n - 1) & hash

n 是 table 大小（2 的幂次方），(n - 1) & hash等价于hash % n，且运算效率更高。

3. 获取 table 中对应索引的元素 f

Doug Lea 采用Unsafe.getObjectVolatile来获取，而不是直接table[index]。原因在于：Java 内存模型中每个线程都有工作内存，里面存储着 table 的副本；虽然 table 本身是 volatile 修饰的，但并不能保证线程每次都拿到 table 中某个下标元素的最新值。Unsafe.getObjectVolatile可以直接读取指定内存地址的数据，保证每次拿到的都是最新值（这正是 volatile 可见性语义在 Unsafe 层面的实现，参见 java/07.Java并发/11.volatile原理深度分析.md）。

4. 空桶场景：CAS 直接插入

如果 f 为 null，说明 table 中这个位置是第一次插入元素，利用Unsafe.compareAndSwapObject方法插入 Node 节点：

• 如果 CAS 成功，说明 Node 节点已经插入，随后addCount(1L, binCount)会检查当前容量是否需要进行扩容；
• 如果 CAS 失败，说明有其它线程提前插入了节点，则自旋重新尝试在这个位置插入节点。
• 空桶插入不加锁，这是 ConcurrentHashMap 并发度高的关键设计之一。

5. 扩容协助：MOVED 节点

如果 f 的 hash 值为 -1（MOVED），说明当前 f 是 ForwardingNode 节点，意味着有其它线程正在扩容，当前线程会调用helpTransfer一起参与扩容，加快数据迁移。

6. 非空桶场景：节点级 synchronized

其余情况把新的 Node 节点按链表或红黑树的方式插入到合适的位置，这个过程采用同步内置锁实现并发：

synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } }

在节点 f 上同步（锁的是桶的头节点），插入之前再次用tabAt(tab, i) == f判断，防止节点被其它线程修改（Double-Check 思想）。三种分支：

1. fh >= 0：f 是链表结构的头结点，遍历链表；如果找到 hash 与 key 都匹配的节点，则修改 value（onlyIfAbsent为 false 时）；否则在链表尾部追加新节点；
2. f 是 TreeBin 类型节点：f 是红黑树根节点，调用putTreeVal在树结构上遍历元素，更新或增加节点；
3. 链表转树：如果链表中节点数binCount >= TREEIFY_THRESHOLD（默认 8），则把链表转化为红黑树结构（详见下文"红黑树构造"）。

这里可以看到 JDK 1.8 的并发设计哲学：能无锁（CAS）就无锁，必须加锁就只锁桶头节点，不同桶之间的写入完全并行，同一桶内的读写冲突概率也远低于全局锁。synchronized 本身的锁升级机制（偏向锁 → 轻量级锁 → 重量级锁）保证了低竞争下的低开销，详见 java/07.Java并发/04.Synchronize细说.md。

07. 扩容机制：addCount 与 transfer

当 table 的元素数量达到容量阈值 sizeCtl 时，需要对 table 进行扩容。整个扩容分为两部分：

1. 构建一个 nextTable，大小为 table 的两倍；
2. 把 table 的数据复制到 nextTable 中。

这两个过程在单线程下实现很简单，但 ConcurrentHashMap 支持并发插入，扩容操作自然也会并发出现，其中第二步支持节点的并发复制，性能提升明显，但实现复杂度也上升了一个台阶。

7.1 触发与并发协作：addCount

private final void addCount(long x, int check) { // ... 省略部分代码 if (check >= 0) { Node<K,V>[] tab, nt; int n, sc; while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) { int rs = resizeStamp(n); if (sc < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); } } }

关键点：

• resizeStamp(n)根据当前 table 长度生成扩容戳记，写入 sizeCtl 的高 16 位，低 16 位记录参与扩容的线程数；
• 通过Unsafe.compareAndSwapInt修改 sizeCtl，保证只有一个线程能够初始化 nextTable（即transfer(tab, null)分支）；
• 后续线程检测到sc < 0（正在扩容），通过sc + 1的 CAS 把参与扩容线程数 +1，然后调用transfer(tab, nt)加入数据迁移；
• 扩容后的数组长度为原来的两倍，但容量阈值（sizeCtl）是原来的 1.5 倍：因为 nextTable 大小为 2n，迁移完成后 sizeCtl 更新为新数组的 0.75 倍，即2n × 0.75 = 1.5n。

7.2 数据迁移：transfer 核心思想

节点从 table 移动到 nextTable，大体思想是遍历、复制的并发过程：

1. 首先根据运算得到需要遍历的次数 i，然后利用tabAt方法获得 i 位置的元素 f，初始化一个 forwardNode 实例 fwd；
2. 如果 f == null，则在 table 的 i 位置放入 fwd（ForwardingNode），这个过程用Unsafe.compareAndSwapObject实现，巧妙地实现了节点的并发移动——空位被占位，其他线程就不会再重复处理该桶；
3. 如果 f 是链表的头节点，构造一个反序链表，把它们分别放在 nextTable 的 i 和 i+n 的位置上（扩容后 hash 只多一位，元素只会落到这两个位置之一），移动完成，采用Unsafe.putObjectVolatile给 table 原位置赋值 fwd；
4. 如果 f 是 TreeBin 节点，也做反序处理，并判断是否需要untreeify（红黑树拆分后节点数不足则还原为链表），把处理的结果分别放在 nextTable 的 i 和 i+n 的位置上，移动完成同样采用Unsafe.putObjectVolatile给 table 原位置赋值 fwd。

遍历过所有节点后复制工作完成：把 table 指向 nextTable，并更新 sizeCtl 为新数组大小的 0.75 倍，扩容完成。

该机制配合 put 流程中的MOVED分支（helpTransfer）与 get 流程中的ForwardingNode.find转发，实现了"扩容期间读写不被阻塞"的高并发体验。

08. 链表转红黑树：treeifyBin 与 TreeBin 构造

注意：如果链表结构中元素超过TREEIFY_THRESHOLD阈值（默认为 8），则把链表转化为红黑树，以提高遍历查询效率（时间复杂度由 O(n) 降为 O(logN)）。

put 完成后触发转树的判断逻辑：

if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; }

转树的具体实现：

private final void treeifyBin(Node<K,V>[] tab, int index) { Node<K,V> b; int n, sc; if (tab != null) { if ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1); else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { synchronized (b) { if (tabAt(tab, index) == b) { TreeNode<K,V> hd = null, tl = null; for (Node<K,V> e = b; e != null; e = e.next) { TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null); if ((p.prev = tl) == null) hd = p; else tl.next = p; tl = p; } setTabAt(tab, index, new TreeBin<K,V>(hd)); } } } } }

要点解读：

• 先判容量再转树：如果 table 长度小于MIN_TREEIFY_CAPACITY（默认 64），说明整体哈希桶太少、冲突过于集中在少数桶，此时直接扩容（tryPresize(n << 1)）比转树更合理；
• 生成树节点的代码块是同步的（synchronized (b)），进入同步代码块之后，再次验证 table 中 index 位置元素是否被修改过；
• 步骤 1：根据 table 中 index 位置 Node 链表，重新生成一个以 hd 为头结点的 TreeNode 链表；
• 步骤 2：根据 hd 头结点，生成 TreeBin 树结构，并把树结构的 root 节点写到 table 的 index 位置的内存中。

TreeBin 的构造函数，主要根据 Node 节点的 hash 值大小构建二叉树（红黑树插入 + 平衡）：

TreeBin(TreeNode<K,V> b) { super(TREEBIN, null, null, null); this.first = b; TreeNode<K,V> r = null; for (TreeNode<K,V> x = b, next; x != null; x = next) { next = (TreeNode<K,V>)x.next; x.left = x.right = null; if (r == null) { x.parent = null; x.red = false; r = x; } else { K k = x.key; int h = x.hash; Class<?> kc = null; for (TreeNode<K,V> p = r;;) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; r = balanceInsertion(r, x); break; } } } } this.root = r; assert checkInvariants(root); }

• 插入时按 hash 大小决定走左子树还是右子树（dir为 -1 走左、1 走右）；
• 当 hash 相同时，先尝试利用 key 的自然排序（comparableClassFor/compareComparables），仍无法区分时用tieBreakOrder按类名与 System.identityHashCode 决出顺序，保证红黑树节点顺序的确定性；
• 每次插入后调用balanceInsertion做红黑树旋转、变色平衡，最后checkInvariants校验树结构约束。

09. get 读取操作

get 操作和 put 操作相比简单许多：

public V get(Object key) { Node<K,V>[] tab; Node<K,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) { if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }

1. 判断 table 是否为空，如果为空直接返回 null；
2. 计算 key 的 hash 值，获取 table 指定位置的 Node 节点，通过遍历链表或树结构找到对应节点，返回 value 值。

分支细节：

• 桶中第一个节点 hash 与目标 hash 相等且 key 匹配，直接返回（命中头节点，最快路径）；
• eh < 0说明该桶是特殊节点（ForwardingNode / TreeBin / ReservationNode），调用find(h, key)在转发节点（扩容中的 nextTable）或红黑树上查找；
• 否则沿链表遍历查找。

全程不加锁，依赖tabAt的 volatile 读语义拿到最新节点，因此 get 可以完全并发执行。

10. 总结与应用建议

10.1 与 HashTable 的对比

ConcurrentHashMap 是一个并发散列映射表的实现，允许完全并发的读取，并且支持给定数量的并发更新。相比之下，HashTable 和同步包装器包装的 HashMap 使用一个全局的锁来同步不同线程间的并发访问：同一时间点只能有一个线程持有锁、只能有一个线程访问容器，虽然保证了多线程间的安全并发访问，但也导致对容器的访问变成串行化，在高竞争场景下吞吐量急剧下降。

JDK 1.8 的 ConcurrentHashMap 通过三层手段解决并发问题：

• volatile 内存语义 + Unsafe 读写：table、Node 的val/next均以 volatile 或getObjectVolatile/putObjectVolatile方式访问，保证可见性；
• CAS 无锁操作：空桶插入、sizeCtl 状态切换、扩容占位等场景用 CAS 自旋，失败重试，避免线程挂起；
• synchronized 细粒度锁：仅对桶头节点加锁，链表/红黑树的结构性修改互不干扰，配合锁升级机制控制开销。

10.2 应用场景

• 当有一个大数组需要在多个线程间共享时，可以考虑把数据分层/分段，避免大锁，并通过 hash 算法进行模块定位；
• 该思想同样适用于数据表设计：把一张数据量巨大的表看作需要同步的数组，操作的表数据过多时考虑事务/存储分离——字段拆分、水平分表等，本质都是"缩小锁粒度"思想的延伸。

10.3 延伸阅读

本文是 YCBlogs 仓库 Java 集合与并发系列的一部分，建议按以下顺序深挖：

• 前置知识：java/04.数据结构/07.HashMap源码深度分析.md、java/04.数据结构/08.HashMap问题思考.md
• 并发基础：java/07.Java并发/15.atomic原子操作类.md、java/07.Java并发/11.volatile原理深度分析.md、java/07.Java并发/04.Synchronize细说.md
• 同主题姊妹篇：java/04.数据结构/17.ConcurrentHashMap1.md（JDK 1.6/1.8 演进、分段锁、核心概念与重要成员）
• 面试视角：java/04.数据结构/00.Java数据结构问题.md

• 教程
• 技术博客
• 文档