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

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

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

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

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

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

1
2
3

问题：

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

主要优化点：

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
- 这样在桶为空时可以无锁插入，避免不必要的锁竞争。
桶级 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 锁定多个桶的情况，进一步减少锁竞争。
红黑树优化（减少链表遍历）
- 当链表长度超过 8 时，转换为 红黑树 存储，树的插入/查找时间复杂度降为 O(logN)，提高并发查询效率。
扩容采用 CAS + 迁移指针（渐进式扩容）
- HashMap 扩容时，需要 rehash 重新计算所有键值的存储位置，而 ConcurrentHashMap 采用分阶段迁移，每个线程只迁移部分数据：
```
if (casTabAt(nextTable, i, null, f)) { // CAS 迁移
    helpTransfer(tab, nextTable);
}
```
1
2
3
- 这样避免了 HashMap 扩容时的全表锁，提高并发性能。

优先使用 CAS，无锁更新：
- 在 putIfAbsent()、computeIfAbsent() 等方法中，尝试用 CAS 直接修改数组，如果成功则无需加锁。
CAS 失败时使用 synchronized：
- 如果 CAS 失败（例如冲突导致哈希桶已有数据），才会进入 synchronized 代码块，加锁保证安全修改。
扩容采用 CAS + 线程协作：
- 通过 CAS 方式更新 nextTable 指针，允许多个线程并行迁移数据，而不是单线程完成所有 rehash，减少 STW（Stop-The-World）问题。

为什么 JDK 1.8 放弃了 Segment？
- Segment 固定 16 个，导致竞争较高并发性能下降。
- 细粒度 synchronized 锁定单个桶，减少锁冲突，提高吞吐量。
为什么 put() 仍然需要 synchronized，而不是完全使用 CAS？
- CAS 适用于单值原子操作，但 put() 可能涉及链表插入、树化转换，需要互斥访问。
ConcurrentHashMap 扩容为何不会影响读操作？
- 采用 volatile 保护 table 引用，扩容期间旧数组仍可读，不影响正在执行的查询操作。