ConcurrentHashMap数据结构-平芜编程栈

一、ConcurrentHashMap 概述

作用：在多线程环境下，提供高效、线程安全的键值对存储。
特点：
- 支持高并发读写
- 不允许 null 键和 null 值
- 元素无序

二、ConcurrentHashMap 的底层结构（JDK8）

1. 分段锁思想

JDK7 及之前：采用分段锁（Segment 数组，每个 Segment 维护一部分数据，锁粒度较粗）。
JDK8 及以后：取消 Segment，直接用 Node 数组（类似 HashMap），采用CAS + synchronized细粒度锁，每个桶（Node）独立加锁。

2. 数据结构

主体结构是Node<K,V>[] table，每个 Node 存储 key、value、hash、next。
桶内冲突用链表或红黑树（与 HashMap 类似）。
扩容时采用转移数组（forwardingNode）标记，保证并发安全。

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; }

三、核心原理

1. put 操作

先通过 CAS 尝试插入，如果失败再用 synchronized 锁定当前桶。
只锁定单个桶（链表/树头节点），不会影响其他桶的并发操作。
插入或更新时，保证可见性与原子性。

2. get 操作

只读操作，无需加锁，直接遍历链表/树即可（Node 的 value/next 都是 volatile）。

3. 扩容机制

多线程可以协同完成扩容（transfer），每个线程负责部分桶的迁移。
扩容期间，桶会被标记为 forwardingNode，防止并发冲突。

四、常用方法

put(K key, V value)：插入/更新键值对
get(Object key)：查询值
remove(Object key)：删除键
size()：计算元素个数（JDK8 是近似值，需遍历所有桶）
containsKey(Object key)：判断是否包含键
forEach()、compute()、merge()等并发安全的批量操作

五、性能分析

高并发读写：分桶锁定，读操作无锁，写操作只锁定单一桶，极大提升并发性能。
扩容高效：多线程协同迁移，减少阻塞。
空间利用率高：与 HashMap 类似，支持链表/红黑树结构。

六、线程安全性与细节

采用 CAS（Compare-And-Swap）和 synchronized 双重保证线程安全。
value/next 等字段用 volatile 修饰，保证可见性。
所有操作都不会抛出 ConcurrentModificationException。

七、与 HashMap/Hashtable 对比

Map 实现类	线程安全	并发性能	锁粒度	是否允许 null
HashMap	否	高	无锁	允许
Hashtable	是	低	整体锁	不允许
ConcurrentHashMap	是	高	分桶/细粒度锁	不允许

八、典型应用场景

多线程环境下的缓存
并发统计、分布式数据收集
Web 服务的会话管理
线程安全的配置映射

九、示例代码

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(); map.put("apple", 1); map.put("banana", 2); System.out.println(map.get("banana")); // 输出 2 map.forEach((k, v) -> System.out.println(k + ":" + v));

十、面试常问问题

ConcurrentHashMap 的底层结构和锁机制？
为什么不允许 null 键和 null 值？
JDK8 之前和之后的实现有何区别？
如何保证高并发安全？
与 HashMap、Hashtable 的区别？

十一、JDK7 与 JDK8 的实现差异

1. JDK7（Segment 分段锁）

结构：ConcurrentHashMap 由一个 Segment 数组组成，每个 Segment 本质上类似一个小型的 HashMap。
锁机制：每个 Segment 有自己的 ReentrantLock，线程操作时只锁定一个 Segment，提高并发度，但 Segment 数量有限（默认16），并发度受限。
扩容：每个 Segment 独立扩容，互不影响。

2. JDK8（桶级锁 + CAS）

结构：取消 Segment，直接用 Node 数组，和 HashMap 类似。
锁机制：插入时先用 CAS 操作，无需锁；CAS失败时只锁定单个桶（链表/树头节点），进一步细化锁粒度。
扩容：多线程协同扩容，每个线程负责部分桶迁移，提升效率。

十二、CAS（Compare-And-Swap）机制

CAS是一种无锁并发技术，底层依赖 CPU 指令，保证原子性。
在 ConcurrentHashMap 中，插入新节点时首先尝试 CAS，如果成功则无需加锁，失败再回退到 synchronized。
CAS 主要用于 table 初始化、节点插入等场景。

CAS 示例（JDK8 put 源码片段）

if (tabAt(tab, i) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // 插入成功，无需加锁 }

十三、扩容细节与协作机制

扩容触发：元素数量超过阈值（容量 × 负载因子）时，触发扩容。
协作迁移：多个线程可以同时迁移不同的桶，迁移过程中，桶会被特殊节点（ForwardingNode）标记，防止并发冲突。
迁移过程：每个线程分配一个迁移区间，迁移完成后，旧桶被标记，后续访问自动跳转到新表。

扩容协作示意图

线程A迁移桶0-3，线程B迁移桶4-7 每个桶迁移完毕后标记为 ForwardingNode 访问老表时遇到 ForwardingNode会跳转新表

十四、批量操作与并行计算

ConcurrentHashMap 提供了许多并发安全的批量操作方法（JDK8）：

forEach(long parallelismThreshold, BiConsumer<? super K,? super V> action)
search(long parallelismThreshold, BiFunction<? super K,? super V,? extends U> searchFunction)
reduce(long parallelismThreshold, BiFunction<? super K,? super V,? extends U> transformer, BiFunction<? super U,? super U,? extends U> reducer)

这些方法可以根据 CPU 核数自动并行分片处理，提高大数据量下的处理效率。

十五、常见面试陷阱与注意事项

ConcurrentHashMap 为什么不允许 null 键和 null 值？
- 因为 null 作为返回值无法区分“键不存在”还是“值就是 null”，容易产生歧义。
size() 方法的准确性？
- JDK8 的 size() 方法是近似值，因为可能有并发修改。需要遍历所有桶，性能较低，不建议在高并发场景频繁调用。
ConcurrentModificationException 会抛吗？
- 不会。ConcurrentHashMap 的迭代器是弱一致性（weakly consistent），可以在遍历过程中安全并发修改。
如何选择并发 Map？
- 低并发场景用 HashMap，高并发用 ConcurrentHashMap，极高并发且需分片锁可自定义分段 Map。

十六、与其他集合的并发安全对比

集合类型	并发安全	锁粒度	迭代器一致性	null 支持
HashMap	否	无锁	不一致	支持
Hashtable	是	整体锁	不一致	不支持
ConcurrentHashMap	是	分桶/细粒度	弱一致性	不支持
Collections.synchronizedMap	是	整体锁	不一致	支持

十七、使用建议

多线程环境首选 ConcurrentHashMap，避免 HashMap 线程安全问题。
避免用 size() 统计大数据量，如需精确计数可用 LongAdder 等方案。
批量操作用并行方法，如 forEach、reduce，提升性能。
不要用 null 作为 key 或 value，避免异常。
合理初始化容量，减少扩容带来的性能开销。

十八、典型应用场景

高并发缓存（如本地缓存、分布式缓存）
并发统计（如计数器、流量统计）
线程安全的会话管理、用户状态管理
配置中心、注册表等高并发读写场景

十九、总结

ConcurrentHashMap 是高性能、线程安全的 Map 实现，广泛用于多线程环境。理解其分段锁、CAS、扩容机制等底层原理，有助于写出高并发高可靠的代码。

ConcurrentHashMap 通过 CAS、细粒度锁、协作扩容等机制，实现了高并发下的高性能和线程安全。理解其底层原理有助于在实际开发和面试中写出高质量的并发代码。

ConcurrentHashMap数据结构