⭐ 题目日期：

美团 - 2025/4/25

📝 题解：

ConcurrentHashMap（简称 CHM）的 put 流程在 Java 8 及之后版本经历了重大重构，核心目标是在保证线程安全的前提下，最大化并发性能和扩展性。它抛弃了 Java 7 中的分段锁（Segment Locking），采用了更细粒度的 CAS + synchronized 锁策略，并结合了其他优化技术。

以下是 Java 8+ 中 ConcurrentHashMap.put(key, value) 的主要流程及其优化点：

核心流程：

1. 计算哈希 (Key Hash Calculation):

   • 调用 spread(key.hashCode()) 计算键的哈希值。spread() 方法（内部是 (h ^ (h >>> 16)) & HASH_BITS）将原始哈希码的高位扩散到低位，并确保结果是一个正数（最高位为 0）。优化： 更好的散列分布，减少哈希冲突。

2. 定位桶 (Table Indexing):

   • 根据计算出的哈希值 h，使用 (n - 1) & h（其中 n 是当前 table 数组的长度）定位到键值对应该放入的桶（Bucket），即 table 数组中的下标 i。

3. 初始化表 (Lazy Initialization):

   • 如果 table 数组尚未初始化（为 null），则调用 initTable() 方法进行初始化。优化： 延迟初始化，避免不必要的内存占用。

4. 处理空桶 (Empty Bucket - CAS):

   • 如果定位到的桶 table[i] 为 null：
     • 尝试使用 CAS 操作将新的 Node（包含 key, value, hash）直接放入该位置 table[i]。
     • 如果 CAS 成功，put 操作基本完成（后续可能需要检查是否需要扩容）。
     • 如果 CAS 失败（说明其他线程抢先在该位置插入了节点），则流程转入下一步“处理非空桶”。

5. 处理非空桶 (Non-Empty Bucket - Synchronized):

   • 如果定位到的桶 table[i] 不为 null：
     • 对桶中的第一个节点（头节点）加 synchronized 锁。这是锁粒度细化的关键：只锁住发生冲突的那个桶（链表/树的头节点），而不是整个 map 或一个大的 Segment。
     • 在同步块内执行：
       • 检查头节点哈希 (Check Hash): 检查头节点的哈希值 fh。
         • 如果 fh >= 0：表示当前桶存储的是普通链表。
           • 遍历链表：
             • 如果找到与传入 key 相同（equals 为 true）且哈希值匹配的节点，则更新其 value。
             • 如果遍历到链表尾部仍未找到，则创建一个新的 Node，将其添加到链表尾部。
         • 如果 fh == MOVED：表示当前桶正在进行扩容迁移。
           • 当前线程会调用 helpTransfer(tab, f) 方法协助完成扩容和数据迁移工作。迁移完成后，在新的 table 上重试 put 操作。优化： 多线程并发扩容，加速大 Map 扩容过程。
         • 如果 fh < 0 且 fh != MOVED：表示当前桶存储的是红黑树（TreeBin 节点）。
           • 调用树节点的 putTreeVal(h, key, value) 方法进行插入或更新。
           • 树内部也利用 CAS 和 synchronized 保证线程安全（TreeBin 自身维护一个读写锁状态）。

6. 链表转树 (Treeify - Threshold):

   • 在链表操作中（步骤 5b），如果插入新节点后链表的长度达到了阈值 TREEIFY_THRESHOLD（默认为 8）：
     • 会尝试调用 treeifyBin(tab, i) 方法将链表转换为红黑树。
     • 注意： 转换并非绝对发生。如果当前 table 数组的长度小于 MIN_TREEIFY_CAPACITY（默认为 64），则优先选择扩容（tryPresize(n << 1)），而不是立即树化。优化： 避免在小表上过早树化（树节点占用空间更大），优先尝试扩容来分散节点。

7. 计数与扩容检查 (AddCount & Resize Check):

   • 无论新增节点（插入成功）还是更新节点值，最终都会调用 addCount(1L, binCount) 方法。
     • 更新元素计数： 使用分散的 CounterCell 数组（类似 LongAdder 的分段计数思想）来统计元素个数，避免单一 size 变量的竞争。优化： 高并发下精确高效的计数。
     • 检查扩容： addCount 内部会检查当前元素总数是否超过了 sizeCtl 阈值。如果超过，则触发 transfer() 方法进行扩容。扩容本身也是一个复杂且高度并发优化的过程（使用 ForwardingNode，多线程协助迁移）。

关键优化总结：

1. 细粒度锁 (Fine-Grained Locking): 从 Java 7 的分段锁 (Segment) 优化为只锁单个桶的头节点（链表或树的根节点）。大大降低了锁的粒度，显著提高了并发度（只要操作不落在同一个桶上，就可以完全并行）。
2. CAS 无锁化 (CAS for First Node): 对于空桶的插入操作，使用 CAS 进行无锁化操作。这是最理想且最高效的情况，完全避免了锁的开销。
3. 并发扩容 (Concurrent Transfer): 当检测到桶处于扩容迁移状态（MOVED）时，当前线程不会阻塞等待，而是会主动调用 helpTransfer 协助其他线程完成迁移。多个线程可以并行迁移不同的桶段，极大地加速了扩容过程。
4. 计数器优化 (Distributed Counting - CounterCells): 使用类似 LongAdder 的分段计数机制（CounterCell 数组）来维护 Map 的大小 (size())。避免了单一 size 变量在高并发更新时成为性能瓶颈和争用点。
5. 链表转红黑树 (Treeify Bin): 当单个桶中的链表过长（>8）时，将其转换为红黑树。将最坏情况下的查找时间复杂度从 O(n) 降低到 O(log n)，优化了哈希冲突严重时的查询性能。
6. 延迟树化 (Check Table Size Before Treeifying): 在链表长度达到树化阈值时，先检查 table 长度。如果 table 长度较小（<64），优先选择扩容而不是立即树化。因为扩容可以有效分散节点，可能避免树化，且小表上树节点的空间开销相对更大。这是一种空间和时间的权衡优化。
7. 更优的哈希计算 (Spread Hash): 使用 spread() 方法优化哈希值计算，提升哈希分布的均匀性，减少冲突。
8. 延迟初始化 (Lazy Initialization): table 在第一次 put 时才真正创建，节省内存。

流程简化视图：

计算 key 的哈希 (spread)
定位桶下标 i ((n-1) & hash)
|
+--> Table 未初始化? ---(是)--> initTable() 初始化
|       |
|       (否)
|
+--> Table[i] == null? ---(是)--> 尝试 CAS 插入新 Node ---(成功)--> addCount(1) & 结束
|       |                              |
|       |                              (失败)--> 重试（说明桶被其他线程占了，进入非空桶流程）
|       |
|       (否)--> 锁住 Table[i]（头节点）
|               |
|               +--> 头节点 Hash == MOVED? ---(是)--> helpTransfer() 协助扩容 --> 完成后重试 put
|               |
|               +--> 头节点 Hash >= 0 (链表)? ---(是)--> 遍历链表 (查找/更新/尾部插入)
|               |                                   |
|               |                                   +--> 插入后链表长度>=8? ---(是)--> treeifyBin() (可能树化或扩容)
|               |
|               +--> 头节点是 TreeBin (红黑树)? ---(是)--> 调用 putTreeVal() 插入/更新树节点
|
+--> 释放 Table[i] 的锁
|
+--> 调用 addCount(1, binCount)
        |
        +--> 更新 CounterCell (分布式计数)
        |
        +--> 检查 size >= sizeCtl? ---(是)--> 触发 transfer() 扩容

总结：

Java 8 及之后的 ConcurrentHashMap.put 流程通过 CAS（空桶插入） + synchronized（锁桶头节点） 的核心锁策略，辅以并发扩容协助、链表转红黑树、分段计数（CounterCell）、延迟初始化、扩容优先于小表树化、优化的哈希计算等一系列精心设计，在保证线程安全的前提下，极大地提升了高并发环境下的插入、更新、扩容操作的性能和扩展性。其设计思想是尽量减少锁的竞争范围，利用 CAS 处理无冲突场景，利用多线程协作处理耗时的扩容操作。