# 问题

18. ConcurrentHashMap 如何优化锁竞争?CAS 和 synchronized 如何配合?

# 标准答案

ConcurrentHashMap 主要通过 CAS(Compare-And-Swap)+ synchronized 细粒度锁 结合优化锁竞争,实现高并发安全。具体策略如下:

  1. JDK 1.7:Segment 分段锁机制,每个 Segment 维护一个独立的哈希桶数组,多个线程可并发访问不同的 Segment,减少锁竞争。
  2. JDK 1.8 之后:取消 Segment,采用 CAS + synchronized 实现更细粒度的并发控制,降低锁粒度:
    • 无竞争时使用 CAS(比如 putIfAbsent),避免加锁。
    • 哈希桶为空时使用 CAS 直接插入,减少锁竞争。
    • 链表/红黑树操作使用 synchronized,但仅锁定单个桶,避免影响其他桶的操作。
    • 扩容采用 CAS + 迁移指针,分阶段进行数据迁移,避免全表重锁,提高吞吐量。

# 答案解析

# JDK 1.7 版本:Segment 分段锁(已废弃)

在 JDK 1.7 及之前,ConcurrentHashMap 采用 Segment(继承 ReentrantLock) 进行分段加锁,每个 Segment 维护一个小型 HashMap,多个线程可以同时访问不同的 Segment,避免全局锁:

class Segment<K,V> extends ReentrantLock {
    transient volatile HashEntry<K,V>[] table;
}
1
2
3

问题:

  1. Segment 数量固定(默认 16),并发粒度受限。
  2. 仍然需要使用 synchronized 进行链表操作。
  3. 扩容时会锁住整个 Segment,影响并发性能。

# JDK 1.8 版本:CAS + synchronized 优化锁竞争

JDK 1.8 之后,ConcurrentHashMap 移除了 Segment,直接使用 Node<K, V>[] table 作为存储结构,优化了锁竞争:

主要优化点:

  1. CAS 插入(无锁操作)

    • putIfAbsent() 在插入新键值对时,先通过 CAS 尝试插入新节点,只有 CAS 失败时才加锁:
    if (tab[index] == null) {
        if (casTabAt(tab, index, null, new Node<K,V>(hash, key, value))) 
            return null;
    }
    
    1
    2
    3
    4
    • 这样在桶为空时可以无锁插入,避免不必要的锁竞争。
  2. 桶级 synchronized 细粒度锁

    • 如果 CAS 失败(例如桶已被占用),则使用 synchronized 仅锁定该桶:
    synchronized (f) { // 只锁住当前桶
        Node<K,V> newNode = new Node<>(hash, key, value, null);
        tab[index] = newNode;
    }
    
    1
    2
    3
    4
    • 这样避免了 JDK 1.7 的 Segment 锁定多个桶的情况,进一步减少锁竞争。
  3. 红黑树优化(减少链表遍历)

    • 当链表长度超过 8 时,转换为 红黑树 存储,树的插入/查找时间复杂度降为 O(logN),提高并发查询效率。
  4. 扩容采用 CAS + 迁移指针(渐进式扩容)

    • HashMap 扩容时,需要 rehash 重新计算所有键值的存储位置,而 ConcurrentHashMap 采用分阶段迁移,每个线程只迁移部分数据:
    if (casTabAt(nextTable, i, null, f)) { // CAS 迁移
        helpTransfer(tab, nextTable);
    }
    
    1
    2
    3
    • 这样避免了 HashMap 扩容时的全表锁,提高并发性能。

# CAS 和 synchronized 如何配合?

  1. 优先使用 CAS,无锁更新

    • putIfAbsent()computeIfAbsent() 等方法中,尝试用 CAS 直接修改数组,如果成功则无需加锁。
  2. CAS 失败时使用 synchronized

    • 如果 CAS 失败(例如冲突导致哈希桶已有数据),才会进入 synchronized 代码块,加锁保证安全修改。
  3. 扩容采用 CAS + 线程协作

    • 通过 CAS 方式更新 nextTable 指针,允许多个线程并行迁移数据,而不是单线程完成所有 rehash,减少 STW(Stop-The-World)问题。

# 深入追问

  1. 为什么 JDK 1.8 放弃了 Segment?

    • Segment 固定 16 个,导致竞争较高并发性能下降。
    • 细粒度 synchronized 锁定单个桶,减少锁冲突,提高吞吐量。
  2. 为什么 put() 仍然需要 synchronized,而不是完全使用 CAS?

    • CAS 适用于单值原子操作,但 put() 可能涉及链表插入树化转换,需要互斥访问。
  3. ConcurrentHashMap 扩容为何不会影响读操作?

    • 采用 volatile 保护 table 引用,扩容期间旧数组仍可读,不影响正在执行的查询操作。

# 相关面试题

  • ConcurrentHashMap 如何优化锁竞争?
  • CAS 机制的优缺点是什么?
  • 为什么 ConcurrentHashMap 不支持 null 作为 key 或 value?
  • ConcurrentHashMap 与 CopyOnWriteMap 有什么区别?