ConcurrentHashMap 深度解析：从分段锁到 CAS 的进化之路

一、引言HashMap 的线程安全困境HashMap 是 Java 中最常用的容器之一但它有一个致命缺陷——线程不安全。在多线程环境下HashMap 在扩容时可能形成环形链表导致get()操作陷入死循环CPU 飙升到 100%。那用Hashtable呢它所有方法都加了synchronized相当于给整张表上了一把大锁同一时刻只允许一个线程操作并发性能极差。于是ConcurrentHashMap应运而生。它既保证了线程安全又追求极高的并发性能是 Java 并发容器中最闪耀的明星。核心定位ConcurrentHashMap是一个线程安全的哈希表设计目标是在最小化更新操作对哈希表占用的同时保持与HashMap相当的空间消耗并支持多线程高效并发访问。从 Java 7 到 Java 8ConcurrentHashMap经历了一次彻底的重写代码量从 1000 多行暴涨到 6000 多行。下面我们从 JDK 8 的视角深入源码一探究竟。二、JDK 7 vs JDK 8架构的全面进化2.1 JDK 7分段锁Segment LockJava 7 中的ConcurrentHashMap采用了分段锁技术将数据分成多个Segment每个Segment独立加锁。Segment继承自ReentrantLock每个 Segment 是一把独立的锁默认 16 个 Segment理论上支持 16 个线程并发写入锁的粒度是整个 Segment一个 Segment 内的所有操作互斥2.2 JDK 8CAS synchronizedJava 8 彻底摒弃了Segment的设计采用了与HashMap相同的数据结构——数组 链表 红黑树并使用CAS synchronized保证线程安全。对比维度JDK 7JDK 8数据结构Segment数组 HashEntry数组 链表Node数组 链表 红黑树锁机制ReentrantLock分段锁CAS synchronized锁头节点锁粒度整个 Segment单个桶链表/树的首节点并发度固定默认16动态数组长度扩容参与单线程扩容多线程协助扩容JDK 8 的核心优势锁粒度从 Segment 缩小到单个桶节点只要 hash 不冲突不同桶的操作可以完全并行。三、核心数据结构与成员变量3.1 Node——基本存储节点Node是ConcurrentHashMap中最基础的存储单元static class NodeK,V implements Map.EntryK,V { final int hash; final K key; volatile V val; // volatile 保证可见性 volatile NodeK,V next; // volatile 保证可见性 Node(int hash, K key, V val, NodeK,V next) { this.hash hash; this.key key; this.val val; this.next next; } }关键设计val和next都使用了volatile修饰确保一个线程对节点的修改对其他线程立即可见。3.2 TreeNode——红黑树节点当链表长度超过阈值时链表会转换为红黑树。TreeNode继承自Node增加了红黑树所需的指针static final class TreeNodeK,V extends NodeK,V { TreeNodeK,V parent; // 父节点 TreeNodeK,V left; // 左子节点 TreeNodeK,V right; // 右子节点 TreeNodeK,V prev; // 前驱节点用于维持双向链表 boolean red; // 红/黑颜色标记 }3.3 TreeBin——红黑树代理注意桶位中存储的不是TreeNode对象而是TreeBin对象。TreeBin是红黑树的代理容器内部维护着红黑树的根节点root和双向链表的头节点first。3.4 ForwardingNode——扩容标记节点当某个桶的数据迁移完成后该桶位会被设置为ForwardingNode简称 FWD 节点其hash值为MOVED-1。后续其他线程看到这个标记就知道该桶正在扩容或已迁移完成。3.5 核心成员变量// 存储数据的数组volatile 保证可见性 transient volatile NodeK,V[] table; // 扩容时使用的新数组仅在扩容期间非空 private transient volatile NodeK,V[] nextTable; // 核心控制字段控制初始化和扩容 private transient volatile int sizeCtl; // 默认初始容量 16 private static final int DEFAULT_CAPACITY 16; // 最大容量 2^30 private static final int MAXIMUM_CAPACITY 1 30; // 负载因子 0.75固定不可修改 private static final float LOAD_FACTOR 0.75f; // 链表转红黑树阈值8 static final int TREEIFY_THRESHOLD 8; // 红黑树转链表阈值6 static final int UNTREEIFY_THRESHOLD 6; // 转红黑树的最小数组容量64小于此值优先扩容 static final int MIN_TREEIFY_CAPACITY 64;3.6 sizeCtl——最核心的控制字段sizeCtl是ConcurrentHashMap中出镜率最高的字段它的值在不同阶段代表不同含义sizeCtl 值含义0默认值尚未初始化-1正在初始化 table -1正在扩容低 16 位表示参与扩容的线程数如 -N 表示有 N-1 个线程参与 0初始化完成后的扩容阈值容量 × 0.75四、构造方法延迟初始化ConcurrentHashMap采用了延迟初始化策略——构造方法只计算容量并不真正创建 table 数组。// 无参构造什么也不做 public ConcurrentHashMap() { } // 指定初始容量的构造方法 public ConcurrentHashMap(int initialCapacity) { if (initialCapacity 0) throw new IllegalArgumentException(); // 计算大于 1.5 * initialCapacity 1 的最小 2 的幂 int cap tableSizeFor(initialCapacity (initialCapacity 1) 1); this.sizeCtl cap; // 只设置 sizeCtl不创建 table }延迟初始化的好处只有在第一次put时才真正创建数组避免了不必要的内存占用。tableSizeFor方法确保容量始终是2 的幂这是为了后续使用位运算(n - 1) hash替代取模运算提升性能。注意loadFactor虽然在构造方法中作为参数传入但计算完size后并未被保存为成员变量后续扩容阈值计算固定使用 0.75。五、put 方法线程安全的核心put方法是ConcurrentHashMap最复杂的部分涉及初始化、CAS 插入、锁扩容、链表/树操作等多个环节。5.1 入口与 hash 计算public V put(K key, V value) { return putVal(key, value, false); } final V putVal(K key, V value, boolean onlyIfAbsent) { // key 和 value 都不能为 null if (key null || value null) throw new NullPointerException(); // spread让高位参与寻址使 hash 更分散 int hash spread(key.hashCode()); int binCount 0; // 记录桶中元素个数用于判断是否树化 // 自旋无限循环直到操作成功 for (NodeK,V[] tab table;;) { NodeK,V f; int n, i, fh; // ... 四种情况处理 } }spread方法将key.hashCode()的高位与低位混合减少 hash 冲突static final int spread(int h) { return (h ^ (h 16)) HASH_BITS; }5.2 四种情况处理putVal的核心是一个自旋循环处理四种不同的情况Case 1table 未初始化if (tab null || (n tab.length) 0) tab initTable(); // 初始化 tableinitTable()通过 CAS 控制sizeCtl确保只有一个线程执行初始化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.compareAndSetInt(this, SIZECTL, sc, -1)) { // CAS 将 sizeCtl 设为 -1当前线程获得初始化权 try { if ((tab table) null || tab.length 0) { int n (sc 0) ? sc : DEFAULT_CAPACITY; NodeK,V[] nt (NodeK,V[])new Node?,?[n]; table tab nt; sc n - (n 2); // 0.75 * n } } finally { sizeCtl sc; // 设置扩容阈值 } break; } } return tab; }Case 2桶位为空无 hash 冲突else if ((f tabAt(tab, i (n - 1) hash)) null) { // 使用 CAS 将新节点放入空桶位 if (casTabAt(tab, i, null, new NodeK,V(hash, key, value, null))) break; // CAS 成功跳出循环 }这里使用CAS 无锁操作不需要加锁是最高效的插入场景。Case 3桶位正在扩容FWD 节点else if ((fh f.hash) MOVED) tab helpTransfer(tab, f); // 当前线程协助扩容如果桶位的头节点是ForwardingNodehash MOVED说明该桶正在扩容迁移当前线程会协助扩容。Case 4正常插入链表或红黑树else { V oldVal null; 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; } } } } // 判断是否需要树化 if (binCount ! 0) { if (binCount TREEIFY_THRESHOLD) // 8 treeifyBin(tab, i); if (oldVal ! null) return oldVal; break; } }关键设计使用synchronized锁住桶的头节点f而不是锁整张表。这意味着只有操作同一个桶的线程才会竞争锁不同桶的操作完全并行。5.3 addCount元素计数与扩容触发插入完成后调用addCount增加元素数量并检查是否需要扩容addCount(1L, binCount);addCount内部会判断当前元素数量是否超过sizeCtl扩容阈值如果超过则触发transfer扩容。六、get 方法无锁读取的秘密get方法是ConcurrentHashMap性能的又一体现——全程不加锁。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) { // 情况1首节点就是目标节点 if ((ek e.key) key || (ek ! null key.equals(ek))) return e.val; } else if (eh 0) { // 情况2hash 0可能是 TreeBin 或 ForwardingNode // - 如果是 ForwardingNode扩容中去 nextTable 中查找 // - 如果是 TreeBin遍历红黑树 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; }为什么 get 不需要加锁volatile保证可见性Node的val和next都是volatile的写入的结果对所有线程立即可见table是volatile的数组引用本身保证可见性Node的hash和key是final的一旦创建不可变扩容时的特殊处理通过ForwardingNode.find()到新表查找这种设计使得get操作几乎不受锁竞争影响性能极高。七、扩容机制多线程协同作战扩容是ConcurrentHashMap最复杂的部分也是它区别于普通HashMap的核心优势——支持多线程协同扩容。7.1 扩容触发条件扩容在addCount方法中被触发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.compareAndSetInt(this, SIZECTL, sc, sc 1)) transfer(tab, nt); // 当前线程协助扩容 } else if (U.compareAndSetInt(this, SIZECTL, sc, (rs RESIZE_STAMP_SHIFT) 2)) transfer(tab, null); // 当前线程是第一个发起扩容的 s sumCount(); } }7.2 transfer数据迁移transfer方法负责将旧 table 的数据迁移到新 table容量翻倍private final void transfer(NodeK,V[] tab, NodeK,V[] nextTab) { int n tab.length, stride; // 计算每个线程负责的桶位数步长 if ((stride (NCPU 1) ? (n 3) / NCPU : n) MIN_TRANSFER_STRIDE) stride MIN_TRANSFER_STRIDE; // 最小 16 if (nextTab null) { // 第一个发起扩容的线程创建新数组 try { NodeK,V[] nt (NodeK,V[])new Node?,?[n 1]; // 容量翻倍 nextTab nt; } catch (Throwable ex) { sizeCtl Integer.MAX_VALUE; return; } nextTable nextTab; transferIndex n; // 从最后一个桶开始分配任务 } int nextn nextTab.length; ForwardingNodeK,V fwd new ForwardingNodeK,V(nextTab); boolean advance true; boolean finishing false; // 自旋迁移数据 for (int i 0, bound 0;;) { // ... 分配任务、迁移数据 ... } }7.3 扩容的核心设计要点任务分片每个线程每次负责stride个桶的迁移默认 16从后往前迁移transferIndex记录全局迁移进度从高位向低位推进FWD 标记迁移完成的桶位设置为ForwardingNodehash 值为MOVED链表拆分原链表被拆分为两个链表分别放入新表的i和i n位置CAS 控制并发通过 CAS 修改sizeCtl和transferIndex协调多线程多线程扩容的优势扩容时间随着参与线程数增加而缩短充分利用多核 CPU 能力。八、链表 ↔ 红黑树转换8.1 链表转红黑树当链表长度 ≥8且数组长度 ≥64时链表转换为红黑树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) // 64 tryPresize(n 1); // 优先扩容 else if ((b tabAt(tab, index)) ! null b.hash 0) { synchronized (b) { if (tabAt(tab, index) b) { // 将链表节点转为 TreeNode然后构建红黑树 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; } // 用 TreeBin 替代原链表头节点 setTabAt(tab, index, new TreeBinK,V(hd)); } } } } }为什么阈值是 8源码注释指出在理想情况下桶中节点数服从泊松分布一个桶中出现 8 个节点的概率仅为0.00000006。因此 8 是一个足够保守的阈值。8.2 红黑树转链表当红黑树节点数减少到 ≤6时树退化为链表。九、总结ConcurrentHashMap是 Java 并发容器中最闪耀的明星它的设计体现了 Java 在并发编程领域的不断进步核心要点回顾数据结构数组 链表 红黑树与 HashMap 1.8 保持一致线程安全机制CAS无竞争场景synchronized锁头节点摒弃了 Segment 分段锁锁粒度从 Segment 级别细化到单个桶节点并发度大幅提升无锁读取get方法全程不加锁依赖volatile保证可见性多线程扩容支持多线程协同完成数据迁移充分利用多核 CPU延迟初始化table 在第一次put时才真正创建put操作流程:首先先判断key和value是否为空如果为空则抛出异常然后计算哈希值进入自旋操作(CAS如果table为空则CAS初始化table如果是正在扩容则协助扩容如果桶为空则直接CAS插入如果桶位有节点则synchronized锁住头节点遍历链表有相同的则替换没有则插入然后判断是否需要树化。get操作流程:首先计算哈希值定位桶检查首节点相同则直接返回如果是fwd扩容中 则去nextable中寻找如果是treebin则去树中遍历否则去链表中遍历。性能对比容器线程安全并发性能适用场景HashMap❌最高单线程环境Hashtable✅全表锁极低遗留代码ConcurrentHashMap (JDK 7)✅分段锁中中等并发ConcurrentHashMap (JDK 8)✅CAS 锁头节点高高并发首选ConcurrentHashMap的成功源于它对并发性能和线程安全的精妙平衡。无论是面试还是日常开发深入理解它的设计思想都能让你写出更高效、更安全的并发代码。