教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载本篇文章是 YCBlogs 技术博客仓库中《ConcurrentHashMap 源码分析下》的完整展开聚焦 JDK 1.8 中 ConcurrentHashMap 的内部结构、构造函数、延迟初始化、put 并发插入、扩容、链表转红黑树与 get 读取的全链路源码。读完本文你将彻底理解CAS 无锁 节点级 synchronized 细粒度锁这套并发设计是如何保证线程安全与高吞吐并存的并能直接应用到高并发缓存、本地注册表等共享 Map 场景的选型与调优中。01. 背景为什么需要 ConcurrentHashMap1.1 效率低下的 HashTableHashTable 容器使用synchronized来保证线程安全但在线程竞争激烈的情况下效率非常低下。因为当一个线程访问 HashTable 的同步方法时其他线程访问 HashTable 的同步方法时可能会进入阻塞或轮询状态。例如线程 1 使用 put 添加元素线程 2 不但不能使用 put 方法添加元素也不能使用 get 方法来获取元素竞争越激烈效率越低。本质原因在于HashTable 是对整个 table 加一把全局对象锁多线程读写时每次只能有一个线程持有锁其余线程全部等待高并发下容器访问被彻底串行化。1.2 线程不安全的 HashMapHashMap 是非线程安全的在涉及多线程并发 put 时可能引发死循环导致 CPU 利用率接近 100%。仓库《Java 数据结构问题》中给出了经典复现场景final HashMapString, String map new HashMapString, 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原子操作类.mdCAS 详解、java/07.Java并发/11.volatile原理深度分析.md内存可见性、java/07.Java并发/04.Synchronize细说.mdsynchronized 原理一并阅读。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.8CAS SynchronizedJDK 1.8 的实现抛弃了 Segment 分段锁机制利用CAS Synchronized保证并发更新的安全底层依然采用数组 链表 红黑树的存储结构。详细演进说明参见仓库 java/04.数据结构/17.ConcurrentHashMap1.md。03. 核心成员变量与重要概念在进入源码之前先明确 ConcurrentHashMap 的几个关键成员详见 java/04.数据结构/17.ConcurrentHashMap1.md成员含义table默认为 null初始化发生在第一次插入操作默认大小为 16 的 Node 数组扩容时大小总是 2 的幂次方nextTable默认为 null扩容时新生成的数组大小为原数组的两倍sizeCtl默认为 0控制 table 的初始化和扩容操作其中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 NodeK,V implements Map.EntryK,V { final int hash; final K key; volatile V val; volatile NodeK,V next; // ... 省略部分代码 }3.2 ForwardingNode 节点一个特殊的 Node 节点hash 值为 -1即MOVED其中存储 nextTable 的引用。只有 table 发生扩容时 ForwardingNode 才会发挥作用作为占位符放在 table 中表示当前节点为 null 或已经被移动final class ForwardingNodeK,V extends NodeK,V { final NodeK,V[] nextTable; ForwardingNode(NodeK,V[] tab) { super(MOVED, null, null, null); this.nextTable tab; } }04. 构造函数与实例初始化4.1 带参构造与 tableSizeFor实例化 ConcurrentHashMap 时带参数会根据参数调整 table 的大小。例如参数为 100最终会调整成 256确保 table 的大小总是 2 的幂次方ConcurrentHashMapString, 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 NodeK,V[] initTable() { NodeK,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) NodeK,V[] nt (NodeK,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 (NodeK,V[] tab table;;) { NodeK,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 NodeK,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) hashn 是 table 大小2 的幂次方(n - 1) hash等价于hash % n且运算效率更高。3. 获取 table 中对应索引的元素 fDoug 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 值为 -1MOVED说明当前 f 是 ForwardingNode 节点意味着有其它线程正在扩容当前线程会调用helpTransfer一起参与扩容加快数据迁移。6. 非空桶场景节点级 synchronized其余情况把新的 Node 节点按链表或红黑树的方式插入到合适的位置这个过程采用同步内置锁实现并发synchronized (f) { if (tabAt(tab, i) f) { if (fh 0) { binCount 1; for (NodeK,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; } NodeK,V pred e; if ((e e.next) null) { pred.next new NodeK,V(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { NodeK,V p; binCount 2; if ((p ((TreeBinK,V)f).putTreeVal(hash, key, value)) ! null) { oldVal p.val; if (!onlyIfAbsent) p.val value; } } } }在节点 f 上同步锁的是桶的头节点插入之前再次用tabAt(tab, i) f判断防止节点被其它线程修改Double-Check 思想。三种分支fh 0f 是链表结构的头结点遍历链表如果找到 hash 与 key 都匹配的节点则修改 valueonlyIfAbsent为 false 时否则在链表尾部追加新节点f 是 TreeBin 类型节点f 是红黑树根节点调用putTreeVal在树结构上遍历元素更新或增加节点链表转树如果链表中节点数binCount TREEIFY_THRESHOLD默认 8则把链表转化为红黑树结构详见下文红黑树构造。这里可以看到 JDK 1.8 的并发设计哲学能无锁CAS就无锁必须加锁就只锁桶头节点不同桶之间的写入完全并行同一桶内的读写冲突概率也远低于全局锁。synchronized 本身的锁升级机制偏向锁 → 轻量级锁 → 重量级锁保证了低竞争下的低开销详见 java/07.Java并发/04.Synchronize细说.md。07. 扩容机制addCount 与 transfer当 table 的元素数量达到容量阈值 sizeCtl 时需要对 table 进行扩容。整个扩容分为两部分构建一个 nextTable大小为 table 的两倍把 table 的数据复制到 nextTable 中。这两个过程在单线程下实现很简单但 ConcurrentHashMap 支持并发插入扩容操作自然也会并发出现其中第二步支持节点的并发复制性能提升明显但实现复杂度也上升了一个台阶。7.1 触发与并发协作addCountprivate final void addCount(long x, int check) { // ... 省略部分代码 if (check 0) { NodeK,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大体思想是遍历、复制的并发过程首先根据运算得到需要遍历的次数 i然后利用tabAt方法获得 i 位置的元素 f初始化一个 forwardNode 实例 fwd如果 f null则在 table 的 i 位置放入 fwdForwardingNode这个过程用Unsafe.compareAndSwapObject实现巧妙地实现了节点的并发移动——空位被占位其他线程就不会再重复处理该桶如果 f 是链表的头节点构造一个反序链表把它们分别放在 nextTable 的 i 和 in 的位置上扩容后 hash 只多一位元素只会落到这两个位置之一移动完成采用Unsafe.putObjectVolatile给 table 原位置赋值 fwd如果 f 是 TreeBin 节点也做反序处理并判断是否需要untreeify红黑树拆分后节点数不足则还原为链表把处理的结果分别放在 nextTable 的 i 和 in 的位置上移动完成同样采用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(NodeK,V[] tab, int index) { NodeK,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) { TreeNodeK,V hd null, tl null; for (NodeK,V e b; e ! null; e e.next) { TreeNodeK,V p new TreeNodeK,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 TreeBinK,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(TreeNodeK,V b) { super(TREEBIN, null, null, null); this.first b; TreeNodeK,V r null; for (TreeNodeK,V x b, next; x ! null; x next) { next (TreeNodeK,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 (TreeNodeK,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); TreeNodeK,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) { 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) { 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; }判断 table 是否为空如果为空直接返回 null计算 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.mdJDK 1.6/1.8 演进、分段锁、核心概念与重要成员面试视角java/04.数据结构/00.Java数据结构问题.md赞分享教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载相关推荐YCBlogs 并发基石ConcurrentHashMap 从分段锁到 CASSynchronized 的演进与实践YCBlogs 并发基石ConcurrentHashMap 从分段锁到 CASSynchronized 的演进与实践 导读 本文基于 YCBlogs 仓库教程技术博客文档JCSprout 并发容器解析ConcurrentHashMap 实现原理JDK1.7 分段锁与 JDK1.8 CASsynchronizedJCSprout 并发容器解析ConcurrentHashMap 实现原理JDK1.7 分段锁与 JDK1.8 CASsynchronized Conc文档知识库后端教程JCSprout 并发系列ConcurrentHashMap 实现原理深度剖析JDK 1.7 分段锁 → JDK 1.8 CAS synchronizedJCSprout 并发系列ConcurrentHashMap 实现原理深度剖析JDK 1.7 分段锁 → JDK 1.8 CAS synchronize文档知识库后端教程上一篇Home Assistant 瑞士公共交通 swiss_public_transport.fetch_connections 操作查询车次连接与响应数据完整指南下一篇如何一键导出QQ空间全部历史说说GetQzonehistory完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/10 2:19:57 · 阅读 1.2k YCBlogs 并发源码剖析：ConcurrentHashMap 的 CAS+Synchronized 实现、扩容与红黑树机制详解
教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载本篇文章是 YCBlogs 技术博客仓库中《ConcurrentHashMap 源码分析下》的完整展开聚焦 JDK 1.8 中 ConcurrentHashMap 的内部结构、构造函数、延迟初始化、put 并发插入、扩容、链表转红黑树与 get 读取的全链路源码。读完本文你将彻底理解CAS 无锁 节点级 synchronized 细粒度锁这套并发设计是如何保证线程安全与高吞吐并存的并能直接应用到高并发缓存、本地注册表等共享 Map 场景的选型与调优中。01. 背景为什么需要 ConcurrentHashMap1.1 效率低下的 HashTableHashTable 容器使用synchronized来保证线程安全但在线程竞争激烈的情况下效率非常低下。因为当一个线程访问 HashTable 的同步方法时其他线程访问 HashTable 的同步方法时可能会进入阻塞或轮询状态。例如线程 1 使用 put 添加元素线程 2 不但不能使用 put 方法添加元素也不能使用 get 方法来获取元素竞争越激烈效率越低。本质原因在于HashTable 是对整个 table 加一把全局对象锁多线程读写时每次只能有一个线程持有锁其余线程全部等待高并发下容器访问被彻底串行化。1.2 线程不安全的 HashMapHashMap 是非线程安全的在涉及多线程并发 put 时可能引发死循环导致 CPU 利用率接近 100%。仓库《Java 数据结构问题》中给出了经典复现场景final HashMapString, String map new HashMapString, 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原子操作类.mdCAS 详解、java/07.Java并发/11.volatile原理深度分析.md内存可见性、java/07.Java并发/04.Synchronize细说.mdsynchronized 原理一并阅读。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.8CAS SynchronizedJDK 1.8 的实现抛弃了 Segment 分段锁机制利用CAS Synchronized保证并发更新的安全底层依然采用数组 链表 红黑树的存储结构。详细演进说明参见仓库 java/04.数据结构/17.ConcurrentHashMap1.md。03. 核心成员变量与重要概念在进入源码之前先明确 ConcurrentHashMap 的几个关键成员详见 java/04.数据结构/17.ConcurrentHashMap1.md成员含义table默认为 null初始化发生在第一次插入操作默认大小为 16 的 Node 数组扩容时大小总是 2 的幂次方nextTable默认为 null扩容时新生成的数组大小为原数组的两倍sizeCtl默认为 0控制 table 的初始化和扩容操作其中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 NodeK,V implements Map.EntryK,V { final int hash; final K key; volatile V val; volatile NodeK,V next; // ... 省略部分代码 }3.2 ForwardingNode 节点一个特殊的 Node 节点hash 值为 -1即MOVED其中存储 nextTable 的引用。只有 table 发生扩容时 ForwardingNode 才会发挥作用作为占位符放在 table 中表示当前节点为 null 或已经被移动final class ForwardingNodeK,V extends NodeK,V { final NodeK,V[] nextTable; ForwardingNode(NodeK,V[] tab) { super(MOVED, null, null, null); this.nextTable tab; } }04. 构造函数与实例初始化4.1 带参构造与 tableSizeFor实例化 ConcurrentHashMap 时带参数会根据参数调整 table 的大小。例如参数为 100最终会调整成 256确保 table 的大小总是 2 的幂次方ConcurrentHashMapString, 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 NodeK,V[] initTable() { NodeK,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) NodeK,V[] nt (NodeK,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 (NodeK,V[] tab table;;) { NodeK,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 NodeK,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) hashn 是 table 大小2 的幂次方(n - 1) hash等价于hash % n且运算效率更高。3. 获取 table 中对应索引的元素 fDoug 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 值为 -1MOVED说明当前 f 是 ForwardingNode 节点意味着有其它线程正在扩容当前线程会调用helpTransfer一起参与扩容加快数据迁移。6. 非空桶场景节点级 synchronized其余情况把新的 Node 节点按链表或红黑树的方式插入到合适的位置这个过程采用同步内置锁实现并发synchronized (f) { if (tabAt(tab, i) f) { if (fh 0) { binCount 1; for (NodeK,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; } NodeK,V pred e; if ((e e.next) null) { pred.next new NodeK,V(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { NodeK,V p; binCount 2; if ((p ((TreeBinK,V)f).putTreeVal(hash, key, value)) ! null) { oldVal p.val; if (!onlyIfAbsent) p.val value; } } } }在节点 f 上同步锁的是桶的头节点插入之前再次用tabAt(tab, i) f判断防止节点被其它线程修改Double-Check 思想。三种分支fh 0f 是链表结构的头结点遍历链表如果找到 hash 与 key 都匹配的节点则修改 valueonlyIfAbsent为 false 时否则在链表尾部追加新节点f 是 TreeBin 类型节点f 是红黑树根节点调用putTreeVal在树结构上遍历元素更新或增加节点链表转树如果链表中节点数binCount TREEIFY_THRESHOLD默认 8则把链表转化为红黑树结构详见下文红黑树构造。这里可以看到 JDK 1.8 的并发设计哲学能无锁CAS就无锁必须加锁就只锁桶头节点不同桶之间的写入完全并行同一桶内的读写冲突概率也远低于全局锁。synchronized 本身的锁升级机制偏向锁 → 轻量级锁 → 重量级锁保证了低竞争下的低开销详见 java/07.Java并发/04.Synchronize细说.md。07. 扩容机制addCount 与 transfer当 table 的元素数量达到容量阈值 sizeCtl 时需要对 table 进行扩容。整个扩容分为两部分构建一个 nextTable大小为 table 的两倍把 table 的数据复制到 nextTable 中。这两个过程在单线程下实现很简单但 ConcurrentHashMap 支持并发插入扩容操作自然也会并发出现其中第二步支持节点的并发复制性能提升明显但实现复杂度也上升了一个台阶。7.1 触发与并发协作addCountprivate final void addCount(long x, int check) { // ... 省略部分代码 if (check 0) { NodeK,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大体思想是遍历、复制的并发过程首先根据运算得到需要遍历的次数 i然后利用tabAt方法获得 i 位置的元素 f初始化一个 forwardNode 实例 fwd如果 f null则在 table 的 i 位置放入 fwdForwardingNode这个过程用Unsafe.compareAndSwapObject实现巧妙地实现了节点的并发移动——空位被占位其他线程就不会再重复处理该桶如果 f 是链表的头节点构造一个反序链表把它们分别放在 nextTable 的 i 和 in 的位置上扩容后 hash 只多一位元素只会落到这两个位置之一移动完成采用Unsafe.putObjectVolatile给 table 原位置赋值 fwd如果 f 是 TreeBin 节点也做反序处理并判断是否需要untreeify红黑树拆分后节点数不足则还原为链表把处理的结果分别放在 nextTable 的 i 和 in 的位置上移动完成同样采用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(NodeK,V[] tab, int index) { NodeK,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) { TreeNodeK,V hd null, tl null; for (NodeK,V e b; e ! null; e e.next) { TreeNodeK,V p new TreeNodeK,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 TreeBinK,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(TreeNodeK,V b) { super(TREEBIN, null, null, null); this.first b; TreeNodeK,V r null; for (TreeNodeK,V x b, next; x ! null; x next) { next (TreeNodeK,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 (TreeNodeK,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); TreeNodeK,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) { 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) { 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; }判断 table 是否为空如果为空直接返回 null计算 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.mdJDK 1.6/1.8 演进、分段锁、核心概念与重要成员面试视角java/04.数据结构/00.Java数据结构问题.md赞分享教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载相关推荐YCBlogs 并发基石ConcurrentHashMap 从分段锁到 CASSynchronized 的演进与实践YCBlogs 并发基石ConcurrentHashMap 从分段锁到 CASSynchronized 的演进与实践 导读 本文基于 YCBlogs 仓库教程技术博客文档JCSprout 并发容器解析ConcurrentHashMap 实现原理JDK1.7 分段锁与 JDK1.8 CASsynchronizedJCSprout 并发容器解析ConcurrentHashMap 实现原理JDK1.7 分段锁与 JDK1.8 CASsynchronized Conc文档知识库后端教程JCSprout 并发系列ConcurrentHashMap 实现原理深度剖析JDK 1.7 分段锁 → JDK 1.8 CAS synchronizedJCSprout 并发系列ConcurrentHashMap 实现原理深度剖析JDK 1.7 分段锁 → JDK 1.8 CAS synchronize文档知识库后端教程上一篇Home Assistant 瑞士公共交通 swiss_public_transport.fetch_connections 操作查询车次连接与响应数据完整指南下一篇如何一键导出QQ空间全部历史说说GetQzonehistory完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考