Java8 ConcurrentHashMap 深度解析（底层数据结构详解及方法执行流程）

一、数据结构 (Data Structure)

Java 8 的 ConcurrentHashMap 摒弃了 Java 7 中的 Segment 分段锁 机制，采用了与 HashMap 1.8 类似的 数组 + 链表 + 红黑树 的结构，但在并发控制上做了特殊设计。

1. 核心结构图

ConcurrentHashMap ├── Node[] table (volatile) // 哈希桶数组 │ ├── Node (链表节点) │ ├── TreeBin (红黑树节点包装) │ └── ForwardingNode (扩容迁移标志) ├── Node[] nextTable // 扩容时的新数组 ├── LongAdder baseCount // 基础计数 └── CounterCell[] counterCells // 并发计数单元格 (解决热点竞争)

2. 关键节点类型

• Node: 存储键值对的基本节点，包含 key, val, hash, next。
• TreeBin: 当链表长度超过阈值（默认 8）且数组长度超过 64 时，链表转为红黑树。TreeBin 是红黑树的根节点包装，不直接存储数据，而是维护树的平衡。
• ForwardingNode: 专门用于扩容。当某个桶正在被迁移时，该位置会放置一个 ForwardingNode，其 hash 值为 MOVED (-1)，指向新的数组 nextTable，引导后续请求去新数组操作。

3. 并发控制核心

• CAS (Compare-And-Swap): 用于无锁插入节点（如数组初始化、空桶插入）。
• synchronized: 当发生哈希冲突（链表或树操作）时，只锁定当前桶的 头节点 (Head Node)。粒度更细，性能优于 Java 7 的 Segment 锁。
• volatile: table 数组和 Node 的 val、next 指针都是 volatile 的，保证可见性。

二、put() 方法执行流程

putVal 是 put 的核心实现，流程较为复杂，主要步骤如下：

1. 参数检查与 Hash 计算

• 检查 key 和 value 是否为 null（CHM 不允许 null）。
• 计算 key 的 hash 值（使用扰动函数，高位参与运算，减少冲突）。

2. 数组初始化 (initTable)

• 如果 table 为 null 或长度为 0，调用 initTable()。
• 使用 CAS 竞争初始化权。如果当前线程发现 sizeCtl < 0，说明其他线程正在初始化，当前线程让出 CPU (Thread.yield()) 自旋等待。
• 初始化成功后，设置 sizeCtl 为扩容阈值（通常为容量的 0.75）。

3. 定位桶位置

• 根据 (n - 1) & hash 计算数组下标 i。
• 获取该位置的节点 f。

4. 插入逻辑 (核心分支)

这里分为三种情况：

• 情况 A：桶为空 (f == null)
  • 使用 CAS 尝试将新节点插入到该位置。
  • 如果 CAS 成功，直接结束。
  • 如果 CAS 失败（说明有其他线程竞争），进入自旋重试。
• 情况 B：正在扩容 (f.hash == MOVED)
  • 说明当前桶的节点是 ForwardingNode。
  • 调用 helpTransfer()，当前线程会 协助扩容，将旧数组的数据迁移到新数组 nextTable 中。
• 情况 C：桶不为空且未扩容 (哈希冲突)
  • 使用 synchronized (f) 锁定该桶的头节点。
  • 再次检查 头节点是否变化（双重检查）。
  • 链表插入: 遍历链表。
    • 如果找到相同 key，根据 onlyIfAbsent 决定是否覆盖 value。
    • 如果没找到，尾插法插入新节点。
    • 插入后检查链表长度，如果 >= 8，调用 treeifyBin 尝试转为红黑树（需数组长度 >= 64，否则先扩容）。
  • 红黑树插入: 如果 f 是 TreeBin 类型，调用 putTreeVal 插入树节点。
  • 解锁。

5. 计数与扩容检查

• 调用 addCount(1L, binCount) 更新元素个数。
• 检查是否达到扩容阈值，如果达到，触发 transfer() 进行扩容（容量翻倍）。

public V put(K key, V value) { return putVal(key, value, false); } /** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { // key 和 value 不能为空 if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { // f = 目标位置元素 Node<K,V> f; int n, i, fh;// fh 后面存放目标位置的元素 hash 值 if (tab == null || (n = tab.length) == 0) // 数组桶为空，初始化数组桶（自旋+CAS) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 桶内为空，CAS 放入，不加锁，成功了就直接 break 跳出 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); else { V oldVal = null; // 使用 synchronized 加锁加入节点 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; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }

三、get() 方法执行流程

get 操作是 无锁 的，这是 CHM 高性能的关键之一。

1. 计算 Hash 与定位

• 计算 key 的 hash 值。
• 定位数组下标 i = (n - 1) & hash。
• 获取该位置的第一个节点 tab[i]。

2. 遍历查找

• 匹配头节点: 如果头节点的 hash 和 key 匹配，直接返回 value。
• 链表遍历: 如果不匹配且 next 不为 null，遍历链表查找。
• 红黑树查找: 如果节点类型是 TreeBin，调用 find 方法在红黑树中查找。
• 扩容处理: 如果节点是 ForwardingNode，说明正在扩容，需要在 nextTable (新数组) 中继续查找。

3. 返回结果

• 找到则返回 value，找不到返回 null。
• 注意: 整个过程中没有使用任何锁，依靠 volatile 保证读取到最新的数据。

public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; // key 所在的 hash 位置 int h = spread(key.hashCode()); if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { // 如果指定位置元素存在，头结点hash值相同 if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) // key hash 值相等，key值相同，直接返回元素 value return e.val; } else if (eh < 0) // 头结点hash值小于0，说明正在扩容或者是红黑树，find查找 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; }

四、size() 方法执行流程

Java 8 中 size() 的返回类型是 int，但底层统计逻辑基于 long。它不是 O(1) 的操作，而是一个估算值（在并发修改时）。

1. 计数机制 (LongAdder 思想)

为了减少高并发下对单一计数变量的竞争，CHM 采用了类似 LongAdder 的机制：

• baseCount: 基础计数值。
• CounterCell[]: 一个数组，当并发竞争激烈时，线程会将计数累加到不同的 CounterCell 单元格中，最后求和。

2. 执行流程 (sumCount())

1. 读取 baseCount。
2. 遍历 counterCells 数组，累加所有非空单元格的值。
3. 总和 = baseCount + counterCells 之和。

3. 返回值

• size() 方法内部调用 sumCount()，如果结果超过 Integer.MAX_VALUE 则返回最大值，否则强转为 int。
• 注意: 由于并发修改，size() 返回的值可能不是强一致性的（即调用瞬间的真实大小），但在大多数场景下足够准确。如果需要强一致性大小，需要加锁统计，但性能会大幅下降。

五. put 元素时如何更新计数？

下文来自ConcurrentHashMap 源码分析 | JavaGuide

六、核心优化点总结 (面试加分项)

1. 锁粒度优化: 从 Java 7 的 Segment 分段锁（锁整个段）变为 Java 8 的 桶级别锁 (synchronized)。JVM 对 synchronized 做了大量优化（偏向锁、轻量级锁），在低冲突下性能极高。
2. CAS 无锁插入: 如果桶为空，直接 CAS 插入，无需加锁。
3. 红黑树优化: 当哈希冲突严重时，链表转为红黑树，查找时间复杂度从 O(n) 降为 O(log n)。
4. 协同扩容: 扩容时，多个线程可以一起帮助迁移数据 (helpTransfer)，加快了扩容速度，避免了单线程迁移导致的停顿。
5. 读写分离: get 操作完全无锁，put 操作仅在冲突时加锁，极大提高了读多写少场景的性能。