★ FEATURED ARTICLE 很久以前第一次翻开 ConcurrentHashMap 源码的时候我的状态基本是找到 JDK 安装目录解压 src.zip双击某个类然后盯着 UnSafe、CAS、ForwardingNode、红黑树这些词半小时缓不过来。这篇源码学习笔记想帮你解决一个很现实的问题如何把 ConcurrentHashMap 这个并发容器从数据结构到核心方法真正读懂同时搞清楚它的性能和一致性边界在哪里。我按 JDK 8 版本的源码主线来拆涉及底层结构、put 流程、扩容机制、无锁读的实现以及实际项目里容易踩的坑。适合准备深入 Java 并发开发的开发者也适合面试前系统梳理并发容器知识的同学。1. 从 HashMap 的并发软肋说起ConcurrentHashMap 为何必须存在1.1 HashMap 并发写入丢数据问题出在哪正常情况下HashMap 的 put 操作就是先根据 hash 定位数组下标然后把 Node 挂到对应桶里。单线程下完全没问题多线程下问题就大了主要体现在两个地方。第一个是并发写同一个桶。两个线程同时发现 table[i] 位置是空的分别 new 出两个 Node然后各自执行 table[i] newNode。这一步赋值不是原子的后写的线程就会把先写的节点直接覆盖掉数据凭空消失。不过这里更常见的情况是在 put 一个链表比较长的桶时两个线程同时遍历链表一个走到最后一个节点准备追加另一个也走到最后一个节点准备追加最后两个节点只能留下一个。第二个是并发扩容。JDK 7 的 resize 在并发下可能让链表形成环之后某个 key 的查找一旦落到环上线程就死循环卡住。JDK 8 改成尾插法解决了成环问题但并发扩容时的数据覆盖仍然存在。两个线程同时搬同一个桶把一个节点从旧表挪到新表互相覆盖之后节点就丢了。这里最容易被忽视的一点是HashMap 并发不安全不是单点问题而是写操作和扩容两个环节都不安全。所以不能指望通过简单加几行 synchronized 来缝缝补补必须重新设计一个并发专用的 Map。1.2 Hashtable 和同步包装 Map 为何不够用Hashtable 给 put、get、remove 这类方法全部加了 synchronized锁的就是整个对象。Collections.synchronizedMap 内部用 mutex 锁整个 Map原理差不多。这两种方案线程安全没问题但读写操作全部串行化任何两个线程想同时操作 Map都要排着队等同一把锁。读多写少的时候这种设计显得非常浪费。因为 get 本身只是读数组里的元素理论上完全没必要阻塞其他读线程即使是写如果写的是不同桶也不应该互相干扰。整个图书馆只有一张桌子所有人都只能到这张桌子上看书效率天花板一眼就能看到。在并发量稍微上来之后这种全局锁方案会成为系统的性能瓶颈这也是后面分段锁、细粒度锁出现的直接原因。1.3 JDK 7 分段锁到 JDK 8 细粒度锁的演进JDK 7 的 ConcurrentHashMap 引入了 Segment 分段锁。默认 16 个 Segment每个 Segment 继承自 ReentrantLock相当于把一整把大锁拆成 16 把小锁。Key 通过 hash 定位到某个 Segment不同 Segment 之间可以并行写入。这个设计比 Hashtable 提升巨大但锁粒度还是有点粗毕竟一个 Segment 内部仍然可能包含很多桶。JDK 8 则更进一步直接去掉了 Segment改用两种更细的机制桶为空时用 CAS 无锁插入。桶非空时用 synchronized 锁住桶头节点。锁的粒度从“16 段”细到“单个桶”并发度基本跟着数组长度走。这种设计变化是整个 ConcurrentHashMap 源码的核心背景后面看到的所有代码本质上都是在为这条思路服务。2. 看源码前的预备课JDK 8 中的底层结构与关键字段在追代码之前先把几个最基础的结构弄清楚否则后面很容易被各种字段绕晕。2.1 Node 数组与 Node 节点结构底层核心存储是一个 Node 数组transient volatile NodeK,V[] table;Node 内部字段如下static class NodeK,V implements Map.EntryK,V { final int hash; final K key; volatile V val; volatile NodeK,V next; }看到 volatile 要留个心table 声明为 volatile只保证数组引用本身的可见性不保证数组里每个元素的可见性。也就是说直接写table[i] node这种赋值其他线程不一定能立刻看到。所以源码里面读取桶元素时不会直接用table[i]而是通过tabAt方法配合Unsafe.getObjectVolatile来读向空桶写入时用casTabAt配合compareAndSwapObject。这种做法绕开了普通数组元素写入的可见性问题。Node 自身的 val 和 next 都声明为 volatile这保证了单个节点的值在并发读写下的可见性。key 和 hash 是 final节点一旦创建key 就固定不变这也是后续 get 可以不加锁读取的前提之一。2.2 sizeCtl 的五种状态sizeCtl 是 ConcurrentHashMap 里最“烧脑”的字段它身兼多职靠正负号和具体数值区分不同状态sizeCtl 值含义-1table 正在初始化-(1n)正在进行扩容n 表示参与扩容的线程数0table 尚未初始化且未指定初始容量正数table 已经初始化此时表示扩容阈值约等于容量 x 0.75初始化或扩容时多个线程就是通过 CAS 抢着修改 sizeCtl 来决定谁干活。谁把 sizeCtl 从 0 改成 -1谁就负责初始化数组扩容时谁把 sizeCtl 从正整数改成负数谁就发起了扩容。需要提醒的是里面的数值只是状态快照不是一个绝对精确的线程数。因为 CAS 是并发修改的你读到的 -(1n) 可能略微滞后但这不影响正确性。2.3 spread 散列与桶定位看 put 之前先看一个静态方法static final int spread(int h) { return (h ^ (h 16)) HASH_BITS; }HASH_BITS 是 0x7fffffff作用是清掉符号位保证结果为正数。核心操作是把 hash 的高 16 位和低 16 位做异或让高位信息也参与到低位计算中。为什么要这么麻烦因为数组定位用的是i (tab.length - 1) hash;tab.length - 1本质是一个低位掩码。如果直接用原始 hashCode只有低几位参与定位高位信息全被浪费冲突概率会明显增加。spread 把高位的随机性“挤压”到低位在数组容量还比较小的时候也能让元素分布得更均匀一些。2.4 hash n一个位运算拆分高低链扩容时有一个非常关键的位运算对每个节点判断hash nn 是旧数组长度一定是 2 的幂。因为新数组长度是 2n比旧数组多了一个二进制位。节点在新数组中的位置只有两种可能如果hash n 0说明多出来的最高位是 0新位置还是原来的下标 i。如果hash n n说明多出来的最高位是 1新位置变成 i n。这个性质让扩容拆分极其高效。只需要对每个节点做一次位判断就能把一条链表无损地拆成两条不需要重新计算 hashCode也不需要重新散列。理解这一点之后再看 transfer 里的高低链拆分就轻车熟路了。3. putVal 逐行拆解初始化、空桶 CAS、非空桶加锁ConcurrentHashMap 的 put 调用链是put-putVal。putVal 是整个写入逻辑的核心我建议把它完整读一遍这里我按关键阶段拆开讲。3.1 initTable用 CAS 裸循环完成数组初始化putVal 的第一步是看 table 是否初始化如果没有就进入 initTable()private final NodeK,V[] initTable() { NodeK,V[] tab; int sc; while ((tab table) null || tab.length 0) { if ((sc sizeCtl) 0) Thread.yield(); else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { // 创建 Node 数组并计算新阈值 } finally { sizeCtl sc; } break; } } return tab; }这个自旋逻辑拆开看很有意思第一个线程读到 sizeCtl 不是负数尝试用 CAS 把它从当前值改成 -1成功后创建数组。其他线程读到 sizeCtl 是负数说明已经有人抢到初始化权调用Thread.yield()让出 CPU等初始化完成。如果第一个线程的 CAS 失败说明发生竞争外层 while 继续自旋重试。为什么不用单独一把锁因为初始化是低频操作用 CAS 裸循环成本更低而且失败线程会主动让出 CPU不会形成锁竞争。初始化完成后sizeCtl 会被设置为新阈值等于初始容量减去四分之一也就是 0.75 倍的容量。这借鉴了 HashMap 负载因子的设计。3.2 空桶插入CAS 失败就继续自旋拿到 table 之后先根据 hash 定位下标int i (n - 1) hash; NodeK,V f tabAt(tab, i); if (f null) { if (casTabAt(tab, i, null, new NodeK,V(hash, key, value, null))) break; }tabAt是 volatile 读数组元素casTabAt是 CAS 写入。如果目标桶是空的就尝试直接把新 Node 放进去整个过程不需要加锁。CAS 成功说明插入完成直接跳出循环CAS 失败说明这瞬间有其他线程抢先写入外层while (true)会重新执行重新读桶、重新判断。这种无锁尝试是 ConcurrentHashMap 高并发下性能好的重要原因大量插入实际命中空桶用一次 CAS 就完成了根本不走锁。3.3 锁住桶头链表遍历与红黑树写入如果桶不为空代码先看头节点的 hashint fh f.hash; if (fh MOVED) { helpTransfer(tab, f); } else { synchronized (f) { if (tabAt(tab, i) f) { if (fh 0) { // 普通链表 } else if (f instanceof TreeBin) { // 红黑树 } } } }MOVED 是 -1表示这个桶已经被标记为 ForwardingNode正在扩容迁移中。当前线程不能再在这个位置直接写而是要调用 helpTransfer 去帮忙扩容。加锁的对象是桶头节点 f不是整个数组。这意味着多个线程可以同时往不同桶里写互相之间完全不影响。锁住之后还要做一次 double-check重新用 tabAt 判断当前桶头是否还是 f。因为等待锁期间其他线程可能已经在扩容过程中把这个桶替换成 ForwardingNode 了。如果不重新检查就可能基于一个过期的头节点继续遍历数据会写错地方。锁内分两种情况普通链表从头遍历key 相同就根据 onlyIfAbsent 决定是否替换 value遍历到结尾都没找到就 new 一个 Node 挂在链尾。TreeBin说明该桶已经树化调用 putTreeVal 走红黑树插入。TreeBin 内部还有一套读写协调机制能保证读线程不会阻塞写线程这里不展开但值得单独去看。3.4 树化条件与 MIN_TREEIFY_CAPACITY 的先后顺序链表长度达到 8 之后会调用 treeifyBin。但 treeifyBin 不是无脑把链表变成红黑树它第一件事是检查数组容量if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) tryPresize(n 1); else if (binCount TREEIFY_THRESHOLD) // 真正树化MIN_TREEIFY_CAPACITY 是 64。如果数组长度小于 64即使某个链表已经超过 8 个节点也先扩容而不是树化。原因一句话就能说清楚容量太小时链表变长很可能是因为桶太少而不是数据分布太差。扩容让桶数量翻倍之后大量节点自然会散开这比建红黑树更划算。只有容量足够大链表还继续变长才说明散列函数对这批 key 的分布确实不理想此时树化才有意义。树化阈值 8 和退化阈值 6 之间特意留了 2 的缓冲目的是避免链表和红黑树在边界上来回横跳。这个设计在 HashMap 里也是一样的。3.5 addCount 计数与扩容检查putVal 的最后调用了 addCountprivate final void addCount(long x, int check) { CounterCell[] as; long b, s; if ((as counterCells) ! null || !U.compareAndSwapLong(this, BASECOUNT, b baseCount, s b x)) { // 走 counterCells 分散计数 } if (check 0) { // 检查是否需要扩容 } }优先用 CAS 给 baseCount 加 1。竞争激烈时 CAS 总是失败就把计数分散到 counterCells 数组里每个线程或 CPU 核心维护自己的计数值最后统一累加。这实际上是 LongAdder 的计数思路目的是避免多线程同时修改一个计数器造成无限重试。check 参数大于 0说明本次插入涉及链表变更可能让元素数量逼近阈值所以 addCount 内部会检查是否触发扩容。如果 sizeCtl 已经小于 0说明其他人正在扩容当前线程不会干等而是加入帮忙。这种“发现别人在干活就搭把手”的协作机制是扩容流程里最有意思的设计。4. transfer 扩容方法与 ForwardingNode并发搬家的核心扩容是整个 ConcurrentHashMap 源码里最复杂的部分也是面试喜欢深挖的地方。4.1 扩容步长 STRIDE 与 transferIndex 任务分配transfer 方法开头有一个非常朴素的逻辑int stride (NCPU 1) ? (n 3) / NCPU : n; if (stride MIN_TRANSFER_STRIDE) stride MIN_TRANSFER_STRIDE;stride 代表一个线程一次领取的连续桶数量。CPU 核数多每个线程可以少领一些核数少就多领一些最少 16 个桶。这样能让多核机器上的并发迁移更细粒度避免某个线程一次领太多区域导致其他线程闲置。负责分配任务的全局变量是 transferIndex初始值是旧数组长度 n。线程通过 CAS 把 transferIndex 减掉 stride拿到一段连续桶区间从高下标往低下标处理。CAS 失败就重新读 transferIndex 再试直到抢到任务。这个分配过程本质上是一个并发栈顶指针的 CAS 递减没有锁却能让多个线程各自领取互不重叠的区间。4.2 ForwardingNode 的意义迁移时每处理完一个桶就在旧数组这个位置放一个 ForwardingNodestatic final class ForwardingNodeK,V extends NodeK,V { final NodeK,V[] nextTable; ForwardingNode(NodeK,V[] tab) { super(MOVED, null, null, null); this.nextTable tab; } }它把 hash 固定为 MOVED-1内部保存着 new 出来的新数组引用。作用是两层标记这个桶已经迁移完成。之后的写线程看到 MOVED就不会再尝试修改旧桶而是去 helpTransfer 帮忙扩容。提供跳转能力。读取线程如果碰到 ForwardingNode通过它的 find 方法会到新表 nextTable 里继续查保证 get 在扩容期间依然能读到数据。理解了 ForwardingNode就能理解 MOVED 这个状态在 put 和 get 里为什么都要特殊处理。它不是一个普通的业务节点而是扩容过程的状态标记。4.3 单桶数据拆分低位链、高位链与 lastRun锁住桶头后对旧链表做一次遍历把节点分成两条链for (NodeK,V p f; p ! null; p p.next) { int b p.hash n; if (b 0) { // 连到低位链 ln } else { // 连到高位链 hn } }判断依据就是前面说过的hash n。低位链放到新数组的 i 位置高位链放到新数组的 i n 位置。这里有个 JDK 8 引以为傲的 lastRun 优化。源码在遍历时会记录最后一个hash n结果变化的位置如果链表尾部有连续一串节点都属于同一条链就直接复用最后这一段不用为这些节点重新 new 对象。对于长链表这个优化能显著减少扩容时的 Node 分配数量。迁移过程中节点仍然在锁内处理所以不会出现同一个节点被两个线程同时操作的情况。单个桶的迁移是原子的多线程之间通过分配不同区间实现并行。4.4 红黑树节点迁移与退化判断如果桶头是 TreeBin不能简单拆链表因为红黑树的节点之间还有父子关系。源码先把 TreeBin 里的 TreeNode 按 next 指针串成链表再遍历做拆分。拆完之后如果某条链的节点数小于等于退化阈值 6就直接用 untreeify 转回普通链表如果仍然超过阈值就 new 一个 TreeBin 重新构造红黑树。这里可以对照 HashMap 的 split 方法思路几乎一样只是多了“树退化”的判断。注意拆分后两条链的根节点不能直接复用因为新链表顺序已经变了必须按新顺序重新建树。4.5 transfer 如何判断整个扩容结束每个线程处理完自己领的区间后会检查 transferIndex 是否已经被其他线程领完。如果领完了当前线程就可能是最后一个完成者源码用 finishing 标志进入第二次循环重新扫描整个旧数组确认所有桶都已经是 ForwardingNode。确认完成后执行收尾table nextTab; nextTable null; sizeCtl (n 1) - (n 1);新容量是 2nsizeCtl 变成新容量的 0.75 倍也就是 1.5n。到这一步整个扩容才算真正结束。整个扩容过程里不同线程并行处理不同区间每个桶的迁移在锁内完成没有数据竞争。线程通过 CAS 竞争 transferIndex 获取任务谁领到谁干干完自己的再帮别人这种协作方式和任务窃取算法有神似之处。5. 读操作为什么可以不加锁get、size、compute 背后的设计ConcurrentHashMap 最反直觉的一点就是 get 全程无锁却依然能拿到正确数据。5.1 无锁 get 为什么安全volatile 字段可见性get 方法的逻辑可以简化成这样tabAt(tab, (n - 1) h) 拿到第一个节点; if (first.hash h key 相等) return first.val; if (first.hash 0) return first.find(h, key); for (Node e first.next; e ! null; e e.next) { ... }整个过程没有锁安全来自于三层保证Node 的 val 和 next 都是 volatile读线程能看见锁内写入的最新值。数组元素读取走的是 getObjectVolatile能看见 CAS 写入的新节点。如果桶头是 ForwardingNodefind 方法会跳到新表继续查扩容期间要么在旧表读到要么跳去新表读到。所以并发读的核心不是锁而是“volatile 保证可见性CAS 保证原子性ForwardingNode 保证跳转正确”这三者的组合。这也是很多初次读源码的人会困惑的地方为什么明明没有 synchronized却能读到线程安全的数据。5.2 弱一致性遍历能看到什么看不到什么ConcurrentHashMap 的迭代器是弱一致性的。它不会像 ArrayList 那样在并发修改时抛 ConcurrentModificationException遍历过程中其他线程修改了 Map可能看到旧数据也可能漏掉新数据但程序不会中断。这个特点经常被忽略。如果业务要求遍历时拿到某个时间点的完整快照ConcurrentHashMap 的迭代器不适合直接用于这种场景。需要先复制一份再遍历或者用 synchronizedMap 替代。这种设计取舍和 get 一样是用“弱一致性”换并发性能。5.3 sumCount 与 counterCellssize() 只是近似值调用 size() 最终走到 sumCountlong sum baseCount; CounterCell[] as counterCells; if (as ! null) { for (CounterCell c : as) { if (c ! null) sum c.value; } } return sum 0L ? 0L : (sum (long)Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)sum);累加 baseCount 和 counterCells 时没有加锁所以任何一个瞬间读到的总和都只是当时数据的近似值。并发写很频繁时size() 和真实值可能有偏差。JDK 官方注释也建议大家用mappingCount()而不是size()前者返回 long避免超大 Map 在 int 上溢出。实际业务里如果只是展示缓存大小、判断是否为空size() 够用如果要用它做精确限流或对账就不太靠谱。5.4 computeIfAbsent 的双检锁思路computeIfAbsent 在 JDK 8 里的实现很值得我们借鉴。它先走一次无锁 get如果 key 已存在就直接返回如果不存在进入自旋在锁内又检查一遍头节点如果桶还是空的用 CAS 直接写入新节点。如果桶非空锁住头节点再走一遍链表或树查找。这套逻辑和单例模式的双重检查锁非常像先无锁快速路径再加锁确认。好处是绝大多数 key 已经不存在的场景都不会真正加锁。但用 computeIfAbsent 时要特别注意传给它的 mappingFunction 必须是无副作用、幂等的操作。因为并发下多个线程可能同时执行这个函数最终只有一个结果被采纳。如果函数里做数据库查询、发送消息这类重量级操作会被重复执行而且执行结果可能还没被采用。6. 源码学习的实践心得从原理到编码的落地点读源码不只是为了面试最终还是要落到实际编码里。这一部分是我自己使用和踩坑后的总结。6.1 key 和 value 为 null 的限制原因ConcurrentHashMap 从一开始就不允许 null key 和 null value这是和 HashMap 最大的一个区别。如果像 HashMap 那样允许 nullget 返回 null 就有两种解释key 不存在或者 value 本身就是 null。单线程下你可以再用 containsKey 判断但并发环境下containsKey 和 get 之间其他线程可能插入数据你无法确定到底属于哪种情况。另一个原因是支持 null 就需要额外的状态标记这会污染并发设计。所以从 HashMap 迁移到 ConcurrentHashMap 时第一件事是检查 key 和 value 是否可能为 null否则线上会遇到奇怪的 NPE。6.2 size() 不是精确值哪些场景要小心前面说过 size() 只是近似值。用同一个 ConcurrentHashMap 统计在线用户数、设备数、任务数的时候多线程持续上下线size() 返回的数字可能和你预期差几条。大多数看板类场景不在乎但一旦涉及“这个数字达到阈值就触发下游动作”就要非常谨慎。如果业务确实需要精确并发计数更合适的方案是用 LongAdder 或者 AtomicLong 单独维护一个计数器。ConcurrentHashMap 负责存对象计数由专门组件负责职责分离之后逻辑也清晰很多。6.3 从读源码到设计并发代码的迁移读完 ConcurrentHashMap最大的收获不该只是记住几个常量而是学会了一套并发设计套路能用无锁就用无锁。空桶插入用 CAS避免不必要的锁开销。必须加锁时把锁粒度控制到最小。锁头节点而不是锁整个 Map。让多个线程在复杂任务里协作。扩容不是单线程包办而是多线程通过 CAS 分任务、互相帮忙。用状态字段表达生命周期。sizeCtl 表达初始化、扩容、稳定期ForwardingNode 标记桶已迁移。这套思想可以迁移到很多代码设计里比如实现一个并发缓存、任务队列或者分段加载器。6.4 JDK 9 版本的差异与阅读建议JDK 9 之后ConcurrentHashMap 内部从 Unsafe 逐步转向 VarHandle比如 compareAndSet、getVolatile 这些底层方法都换成了 VarHandle 调用。语义没有变化只是底层实现换了。如果在较新 JDK 上找源码看到 VarHandle 字样不要慌和 JDK 8 的 Unsafe 逻辑是一一对应的。阅读顺序建议先读 Node 和 sizeCtl再读 putVal再读 transfer最后回头补 get 和 compute。不建议从头到尾逐行读很容易迷失在 CounterCell 和 TreeBin 的细节里。我自己的做法是写一个简单多线程压测小工具用 CyclicBarrier 让几十个线程同时往 Map 里塞数据然后在 IDE 里给 transfer 和 putVal 打断点观察 sizeCtl 和 transferIndex 的实时变化。纸上得来终觉浅看到实际并发下的状态跳转对源码的理解会立刻深一层。最后说一点个人体会。在读完整套源码之后我写并发代码时多了一个习惯先问自己能不能用 CAS 避免锁再问如果必须加锁能不能只锁最小范围。ConcurrentHashMap 的价值不只是提供了一个好用的并发 Map它本身就是一个可参考的并发设计范本。希望这篇源码学习笔记能让你在看懂每个方法的同时也把这种设计思路带走。
阅读完成 · 觉得有帮助？
