ConcurrentHashMap是如何保证线程安全的？

先记住一句最核心的话JDK8 的 ConcurrentHashMap 通过CAS synchronized volatile等机制在保证线程安全的同时尽量减少锁竞争。重点是它不是整张 Map 加一把大锁。一、先理解为什么 HashMap 线程不安全假设MapString, Integer map new HashMap();两个线程同时线程 A 线程 B │ │ │ map.put(A, 1) │ map.put(B, 2) │ │ └──────────┬──────────────┘ ↓ 同时修改 MapHashMap 本身没有提供并发控制。多个线程同时修改可能产生数据覆盖数据丢失结构破坏扩容时出现问题所以HashMap ↓ 多线程同时修改 ↓ 线程不安全二、那 Hashtable 是怎么解决的你刚刚学过HashtableString, Integer table new Hashtable();它的思路非常简单给很多方法加 synchronized。例如可以理解成public synchronized V get(Object key) { ... } public synchronized V put(K key, V value) { ... } public synchronized V remove(Object key) { ... }也就是说同一个Hashtable对象上多个线程执行这些方法时需要竞争同一把对象锁。于是线程 A ───┐ 线程 B ───┤ 线程 C ───┤ 线程 D ───┘ ↓ 同一把锁 ↓ 一个一个执行这样当然线程安全。但是问题是锁竞争太严重。例如线程 A 操作 keyA 线程 B 操作 keyB如果它们实际上操作的是完全不同的桶A → table[1] B → table[100]理论上两者完全可以并行。但 Hashtable一把锁 / | \ A B C仍然要排队。所以并发性能不好。所以你可以把Hashtable理解成“整张表共用一把锁”。三、ConcurrentHashMap 的核心思想ConcurrentHashMap 的设计思想就是不要给整个 Map 加一把大锁而是尽量缩小锁的范围。Hashtable ↓ 整张表一把锁 ↓ 并发性能较低 ConcurrentHashMap ↓ 更细粒度的并发控制 ↓ 允许多个线程尽可能同时操作 ↓ 并发性能更高你可以把它理解成ConcurrentHashMap ┌─────┬─────┬─────┬─────┬─────┐ │桶0 │桶1 │桶2 │桶3 │桶4 │ └─────┴─────┴─────┴─────┴─────┘ ↑ ↑ │ │ │ └── 可以独立操作 │ └── 只锁需要修改的桶所以线程 A → 桶 1 线程 B → 桶 100可以同时进行。这就是 ConcurrentHashMap 高并发性能的重要来源。四、JDK7 和 JDK8 要分开理解JDK7ConcurrentHashMapSegment Segment Segment ...采用Segment 分段锁JDK8取消了 Segment 这种结构。采用CAS synchronized Node 数组 链表/红黑树所以JDK7 和 JDK8 的实现方式不同。JDK7 主要采用 Segment 分段锁JDK8 去掉了 Segment主要通过 CAS 和 synchronized 对桶级别进行控制。五、先重点讲 JDK8现在实际开发中主要关注 JDK8。ConcurrentHashMap 底层结构可以理解成ConcurrentHashMap │ ↓ NodeK,V[] table │ ┌──────┼─────────┐ ↓ ↓ ↓ 桶0 桶1 桶2 │ ↓ Node │ ↓ 链表/红黑树它和 JDK8 HashMap 的数据结构非常接近数组 链表 红黑树但是线程安全机制不一样。六、CAS 是怎么保证线程安全的先理解一个简单场景。假设table[5] null现在两个线程同时往table[5]放元素。线程 A ──┐ ├── table[5] 线程 B ──┘如果直接赋值table[5] newNode;就可能产生并发问题。ConcurrentHashMap 会使用 CAS。可以简单理解成只有当 table[5] 仍然是 null 时我才把我的 Node 放进去。类似线程 A 发现 table[5] null ↓ CAS 成功 ↓ 放入 Node A 线程 B 发现 table[5] 已经不是 null ↓ CAS 失败 ↓ 重新处理因此多个线程不会无脑覆盖。七、为什么 CAS 特别适合 ConcurrentHashMap因为很多情况下桶本来就是空的例如table[10] null这时候没有必要为了放一个 Node加锁 ↓ 修改 ↓ 释放锁可以直接CAS ↓ 成功这样避免了加锁成本。所以对于空桶的插入ConcurrentHashMap 可以优先使用CAS。八、那 CAS 解决不了所有问题这是重点。假设table[5] ↓ A → B → C现在线程 A修改桶 5 线程 B也修改桶 5这里涉及比较复杂的链表/红黑树结构修改。不能简单靠一次 CAS 完成。怎么办ConcurrentHashMap 会使用synchronized对当前桶的头节点进行同步控制。也就是线程 A ↓ 锁住桶5 ↓ 修改链表 ↓ 释放锁 线程 B ↓ 等待注意锁的是当前桶而不是整个 ConcurrentHashMap。这就是它和 Hashtable 的一个非常重要的区别。九、所以 JDK8 ConcurrentHashMap 的核心机制你可以记成ConcurrentHashMap │ ├── CAS │ └── 处理很多简单的并发更新 │ ├── synchronized │ └── 锁住发生冲突的桶 │ ├── volatile │ └── 保证数据可见性 │ └── Node数组 ├── 链表 └── 红黑树最重要的就是CAS synchronized十、为什么还需要 volatileConcurrentHashMap 中部分变量使用了volatile。例如 Node 中的volatile V val; volatile NodeK,V next;目的之一就是保证一个线程修改之后其他线程能够及时看到最新值。例如线程 A 修改 value ↓ volatile ↓ 线程 B 读取最新 value所以CAS → 原子性 synchronized → 原子性 互斥 可见性 volatile → 可见性 一定的有序性十一、put() 的过程你要重点理解ConcurrentHashMap 的 put 是怎么实现线程安全的简化之后可以理解成put(key, value) │ ↓ 计算 hash │ ↓ 计算数组下标 │ ↓ table[index] │ ↓ ┌──────┴─────────┐ │ │ ↓ ↓ 空桶 非空桶 │ │ ↓ ↓ CAS synchronized │ │ ↓ ↓ 插入 Node 修改链表/红黑树也就是说情况 1桶为空CAS情况 2桶不为空synchronized这就是 ConcurrentHashMapput()的核心思想。十二、举一个非常直观的例子假设table[1] → A → B table[2] → C table[3] → null现在线程 1put(D) → 桶 3 线程 2put(E) → 桶 1线程 1桶 3 是空的 ↓ CAS ↓ 成功线程 2桶 1 已经有数据 ↓ synchronized ↓ 锁桶 1 ↓ 修改链表两个线程线程1 → 桶3 → CAS 线程2 → 桶1 → synchronized可以并行。这就是 ConcurrentHashMap 的并发优势。十三、那为什么不用一把 ReentrantLock你可能会想到为什么不直接给每个桶一个 ReentrantLock因为这样会产生大量锁对象内存开销比较大。JDK8 ConcurrentHashMap 采用CAS synchronized而不是给每个桶单独维护一个显式 Lock。当发生冲突时synchronized (f) { ... }其中f可以理解为当前桶的头节点。这样锁对象直接利用现有 Node不需要额外创建大量 Lock 对象。这个设计非常巧妙。十四、JDK7 的 Segment 是什么虽然现在主要使用 JDK8但面试经常问。JDK7ConcurrentHashMap │ ├── Segment 0 ├── Segment 1 ├── Segment 2 └── Segment 3每个 SegmentSegment ↓ HashEntry[]每个 Segment 自己有一把锁。所以线程 A → Segment 0 线程 B → Segment 1可以并行。这就是分段锁。十五、JDK7 vs JDK8这个表建议直接记JDK7JDK8核心结构Segment HashEntryNode[] 链表/红黑树并发控制Segment 分段锁CAS synchronized锁粒度Segment桶级别是否使用 CAS有大量使用是否有红黑树❌✅并发性能较好更好十六、为什么 ConcurrentHashMap 不允许 null这个也很容易被问。ConcurrentHashMapString, String map new ConcurrentHashMap(); map.put(A, null);不允许。原因和并发语义有关。假设map.get(A)返回null在并发环境下到底意味着A 不存在还是A 存在但是 Value null会产生歧义。所以 ConcurrentHashMap 直接禁止 nullKey null ❌ Value null ❌十七、小结ConcurrentHashMap 为什么比 Hashtable 性能好Hashtable 基本上是对整个 Map 的方法进行 synchronized 同步多个线程之间容易产生锁竞争。JDK8 ConcurrentHashMap 不采用整张 Map 一把锁而是使用 CAS 处理部分无锁更新对于发生冲突的桶再通过 synchronized 进行桶级别的同步因此不同桶之间的操作可以并发执行所以并发性能更好。十八、一个非常重要的误区不要说ConcurrentHashMap 是线程安全的所以所有操作都是原子的。这是错误的。例如if (!map.containsKey(key)) { map.put(key, value); }这两个操作containsKey ↓ put虽然各自是线程安全的但是整个“先判断再插入”的复合操作不是原子的。正确做法可以使用map.putIfAbsent(key, value);这样整个操作才具有对应的原子语义。十九、你现在应该记住这张图ConcurrentHashMap │ ┌──────────┴──────────┐ ↓ ↓ JDK7 JDK8 │ │ Segment 分段锁 CAS synchronized │ │ ↓ ↓ 多个 Segment Node[] table │ │ ↓ ┌──────┴──────┐ 每段一把锁 ↓ ↓ 链表 红黑树 CAS │ 空桶插入等场景 synchronized │ 冲突桶修改