03.3 — ConcurrentHashMap
定位: 线程安全的 HashMap — 从分段锁到 CAS + synchronized 的并发演进 面试高频度: ⭐⭐⭐⭐⭐ 考查方式: JDK7 vs JDK8 实现差异、为什么线程安全、size() 实现、并发度
一、这是什么？为什么需要它？
为什么 HashMap 线程不安全？
java
// JDK 7 HashMap 死循环问题（扩容时头插法导致链表环）
// JDK 8 虽修复了死循环，但仍有数据丢失问题
Map<String, String> map = new HashMap<>();
// 两个线程同时 put → 可能数据覆盖、size 计数错误所以：需要线程安全的哈希表。
为什么不直接用 Hashtable 或 Collections.synchronizedMap()？
java
// Hashtable：所有方法加 synchronized（锁整个表）
public synchronized V put(K key, V value) { ... }
public synchronized V get(Object key) { ... }
// 问题：并发度 = 1
// 线程 A 正在读取，线程 B 必须等待 → 完全串行化
// 1 个 CPU 干活，其他 CPU 空转ConcurrentHashMap 的目标：高并发下保持线程安全，同时最大化并发度。
二、原理拆解
2.1 JDK 7 实现：分段锁
┌─────────────────────────────────────────────────────────────┐
│ JDK 7 ConcurrentHashMap │
│ │
│ ┌──────────────────────────────────────────────────┐ │
│ │ Segment 数组（默认 16 段） │ │
│ ├──────┬──────┬──────┬──────┬──────┬──────┬────────┤ │
│ │ S0 │ S1 │ S2 │ ... │ │ │ S15 │ │
│ ├───┬──┴──┬───┴──┬───┴──┬───┴──┬───┴──┬───┴──┬─────┤ │
│ │ │ │ │ │ │ │ │ │ │
│ │ HashEntry[] 数组（每个 Segment 里的小 HashMap） │
│ │ 每个 Segment 继承 ReentrantLock │
│ └────────────────────────────────────────────────────┘ │
│ │
│ put(key, value): │
│ 1. 通过 key 定位 Segment │
│ 2. 锁 Segment（tryLock 自旋一定次数） │
│ 3. 在 Segment 内的 HashEntry 数组操作 │
│ 4. 释放锁 │
│ │
│ 并发度 = Segment 数量（默认 16） │
│ 不同 Segment 的 put 可以完全并行！ │
└─────────────────────────────────────────────────────────────┘优点：多读多写时可以并行（不同 Segment）。 缺点：Segment 数量固定，扩容复杂，Segment 继承 ReentrantLock 浪费内存。
2.2 JDK 8 实现：CAS + synchronized
┌─────────────────────────────────────────────────────────────┐
│ JDK 8 ConcurrentHashMap │
│ │
│ ┌──────────────────────────────────────────────────┐ │
│ │ Node<K,V>[] table（同 HashMap 一样的桶数组） │ │
│ ├────┬────┬────┬────┬────┬────┬────┬────┬────┬─────┤ │
│ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ ... │ │
│ └─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─────┘ │
│ │ │ │ │ │ │ │ │ │ │
│ 链表或红黑树 │
│ │
│ 同步策略： │
│ - 数组初始化：CAS（无锁） │
│ - 放入空桶：CAS（无锁） │
│ - 放入非空桶：synchronized(桶的头节点)（细粒度锁） │
│ │
│ 相比 JDK 7 的优势： │
│ - 锁粒度更细：只锁单个桶，不是整个 Segment │
│ - 内存占用更少：没有 Segment 和 ReentrantLock 开销 │
│ - 读操作几乎无锁（volatile 保证可见性） │
└─────────────────────────────────────────────────────────────┘put 流程（JDK 8）：
java
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 1. 计算 hash
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
// 2. 延迟初始化（CAS 无锁）
if (tab == null || tab.length == 0)
tab = initTable();
// 3. 桶为空 → CAS 放入（无锁！）
else if ((f = tabAt(tab, i)) == null) {
if (casTabAt(tab, i, null, new Node(hash, key, value)))
break;
}
// 4. 正在扩容 → 帮忙扩容
else if (f.hash == MOVED)
tab = helpTransfer(tab, f);
// 5. 桶不为空 → synchronized 锁桶
else {
synchronized (f) { // 锁桶的头节点
// ... 遍历链表/红黑树，插入或替换
}
}
}
}2.3 并发读：几乎无锁
java
public V get(Object key) {
int hash = spread(key.hashCode());
Node<K,V>[] tab; Node<K,V> e;
// 直接读，不使用锁
e = tabAt(tab, (n - 1) & hash);
// volatile 读保证可见性
}为什么不加锁？ Node 的 val 和 next 都是 volatile 的，保证可见性和有序性。
java
static class Node<K,V> {
final int hash;
final K key;
volatile V val; // 保证读线程看到最新写入
volatile Node<K,V> next; // 保证看到最新链表结构
}2.4 size() 实现
java
public int size() {
long n = sumCount();
return (n < 0L) ? 0 : (n > Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) n;
}
// sumCount 使用 CounterCell 数组进行分段计数
// 多个线程同时 put 时，各自更新不同的 CounterCell
// 避免 CAS 竞争JDK 7：累加每个 Segment 的 modCount
JDK 8：CounterCell 数组 + CAS 更新
先尝试无锁 CAS 更新 baseCount
竞争激烈时，使用 CounterCell 分散竞争
size() 时累加 baseCount + CounterCell[]三、图解全景
┌─────────────────────────────────────────────────────────────┐
│ JDK 7 vs JDK 8 ConcurrentHashMap 对比 │
│ │
│ ┌─────────── JDK 7 ───────────────────────┐ │
│ │ │ │
│ │ Segment[0] │ │
│ │ ┌───┐ ┌───┐ ┌───┐ │ │
│ │ │ H │→│ H │→│ H │→... (HashEntry[]) │ │
│ │ └───┘ └───┘ └───┘ │ │
│ │ ReentrantLock │ │
│ │ │ │
│ │ 并发度 = Segment 数 (默认 16) │ │
│ │ 内存 = 16 ReentrantLock + 16 HashEntry[]│ │
│ └──────────────────────────────────────────┘ │
│ │
│ ┌─────────── JDK 8 ───────────────────────┐ │
│ │ │ │
│ │ table[0] → Node → Node → ... │ │
│ │ table[1] → null (CAS 放入) │ │
│ │ table[2] → Node (synchronized 锁此节点) │ │
│ │ │ │
│ │ 并发度 = table 长度 (理论 16, 默认 16) │ │
│ │ 内存 ≈ 普通 HashMap + 一点 volatile │ │
│ └──────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────┘四、实战验证
4.1 线程安全对比
java
Map<String, Integer> hashMap = new HashMap<>();
Map<String, Integer> chm = new ConcurrentHashMap<>();
int THREADS = 10;
int COUNT = 1000;
// 10 个线程同时 put
ExecutorService pool = Executors.newFixedThreadPool(THREADS);
// HashMap 测试（可能抛异常或数据丢失）
for (int t = 0; t < THREADS; t++) {
pool.submit(() -> {
for (int i = 0; i < COUNT; i++) {
hashMap.put(Thread.currentThread().getName() + i, i);
}
});
}
// ConcurrentHashMap 测试（安全）
for (int t = 0; t < THREADS; t++) {
pool.submit(() -> {
for (int i = 0; i < COUNT; i++) {
chm.put(Thread.currentThread().getName() + i, i);
}
});
}
pool.shutdown();
// HashMap 最终 size 经常 < 10000（数据丢失）
// ConcurrentHashMap 永远 = 10000五、面试视角
| 追问 | 答案要点 |
|---|---|
| JDK 7 和 JDK 8 的 ConcurrentHashMap 区别 | 锁：Segment(ReentrantLock) vs CAS+synchronized；并发度：固定16 vs 动态table长度 |
| 为什么 JDK 8 用 synchronized 而不是 ReentrantLock？ | JDK 6+ 对 synchronized 深度优化，锁升级机制下性能趋近于 ReentrantLock，且 JVM 可自由优化 |
| ConcurrentHashMap 的 get 需要加锁吗？ | 不需要，Node 的 val 和 next 是 volatile，保证可见性 |
| ConcurrentHashMap 的 size() 怎么保证准确？ | CounterCell 分段计数 + CAS 更新，不保证 100% 实时一致（最终一致性） |
| ConcurrentHashMap 的迭代器是 fail-safe 的吗？ | 是。迭代时不会抛 ConcurrentModificationException，但不保证看到最新写入 |
📚 相关链接
- **HashMap核心原理** — HashMap 的基础原理
- **并发工具类(AQS)** — AQS 与并发工具
- ← 返回 **集合索引**