ConcurrentHashMap
ConcurrentHashMap 是允许多个线程同时读取和更新的线程安全 Map。它的线程安全指的是每一次方法调用是安全的:get、put 不会把内部结构弄坏,同一个键上的 compute、merge 是原子的。可是业务代码常常把几次调用拼在一起,比如先 containsKey 再 put,这种组合它不负责;值对象内部的修改它也不管。讲这个主题,一半是它怎样用 CAS、桶级同步和协作扩容做到并发安全,另一半是它的保证在哪里结束。实现细节以 OpenJDK 21 为准,并说明 JDK 7 到 JDK 8 的变化。
1. 面试核心
先记住这几条,再读正文- OpenJDK 21 的 ConcurrentHashMap 用 CAS 往空桶里放首节点,用桶级同步协调同一个桶内的冲突更新。卡 · JDK 8 之后的结构
get依靠 volatile 等内存同步机制读取已经发布的节点,不需要获取桶的互斥锁。computeIfAbsent原子地完成单个键的缺失检查和计算,而先containsKey再put仍然有竞态。卡 · 回调返回值与可变值- 原子更新只保护键到值的映射关系,可变值对象内部的读写仍需要单独同步。卡 · 回调返回值与可变值
- ConcurrentHashMap 拒绝 null 键和 null 值,所以
get返回 null 就表示当前没有这个映射。卡 · null 键和值
2. 并发 Map 的需求
普通 HashMap 不保证并发读写的正确性。最简单的补救是用一把全局锁保护所有访问,这样是安全了,但两个线程操作毫不相关的键,也得在这把锁上排队。ConcurrentHashMap 的思路是缩小同步的范围,让不相关的操作不必互相等待。
它的实现可以概括为五项机制:
- 读取沿着已经发布的节点查找,不获取桶的互斥锁。
- 往空桶插入时用 CAS(比较并交换):只有这个位置仍然是预期的值(这里是空)时才写入,否则重试。
- 同一个桶里发生冲突更新时,只在这个桶内协调,其他桶照常更新。
- 扩容时,多个线程可以分担桶的迁移工作。
- 迭代可以和更新同时进行,按弱一致的规则观察元素。
这些机制保证的是单次方法调用的安全。热点键和耗时的回调依然会让线程等待;涉及多个键的业务约束,需要更高层的同步;数据库写入和消息发送也要另外协调。
3. JDK 8 之后的结构
JDK 7 用 Segment 把整个映射分成若干段,每段一把锁。JDK 8 改成了和 HashMap 类似的桶数组加链表和红黑树,OpenJDK 21 仍然是这个基本结构。各部分的同步分工如下:
table字段、节点的值和链接通过 volatile 等可见性机制发布,读者能看到正确构造和更新过的节点。- 空桶通过 CAS 放入首节点,多个线程同时竞争时只有一个能成功。
- 非空的链表桶在首节点上加
synchronized,用这个对象的监视器(monitor)让同一个桶的更新排队执行。 - 树桶用
TreeBin包住红黑树,靠内部状态协调查找和结构调整。 - 迁移完成的桶放一个转发节点,引导后来的操作去新数组。
所以锁的粒度从 JDK 7 的「一段」缩小到了「一个桶」。构造参数 concurrencyLevel 在 OpenJDK 21 里只用来估算初始容量。面试里提到「默认 16 个 Segment」时,要说明那是 JDK 7 的历史实现。
4. 无锁读取
读取要能看到已经发布的节点,同时尽量不和写线程互相等待。get 先计算哈希、读出目标桶,再按键沿链表或树查找。节点的值和链接通过 volatile 等机制保证可见,键字段创建后不再改变,可以放心用来确认匹配。树正在调整结构时,查找会改走节点之间的链表路径,所以整个过程不需要获取桶的互斥锁。
V value = cache.get(key);
不加锁不代表没有内存保证。对某个键的一次更新,和之后读到这个更新值的非空读取之间,存在 happens-before 关系:写者在发布这个值之前做的所有写入,对读到它的线程都可见。比如写者先初始化好一个对象的字段,再把它 put 进去,读者 get 到这个对象时,一定能看到初始化后的字段。
跨多个键读取时能看到怎样的状态,见迭代一致性。
5. 复合操作的竞态
每个方法都是线程安全的,不代表由几个方法组成的业务动作也是。下面先检查、再写入,两次调用之间,其他线程可以插进来:
if (!users.containsKey(id)) {
users.put(id, loadUser(id));
}
两个线程如果都看到 id 不存在,就会各自执行一次 loadUser,后写入的值还会覆盖先写入的。对于短小的本地计算,可以用 computeIfAbsent 把「检查缺失」和「创建映射」合成一个原子操作:
User user = users.computeIfAbsent(id, User::new);
只有 id 不存在时才会调用 User::new,已经有值时直接返回现有的值。其他条件更新的需求,可以按下表选择方法:
| 需求 | 方法 |
|---|---|
| 仅不存在时写入 | putIfAbsent |
| 仅值仍匹配时替换 | replace(key, old, next) |
| 仅值仍匹配时删除 | remove(key, value) |
| 按旧值计算新值 | compute、computeIfPresent |
| 不存在时计算 | computeIfAbsent |
| 合并已有与新增值 | merge |
这些方法的原子性只覆盖一个键的映射。数据库写入、对另一个 Map 的修改、发送消息,都要另外协调,才能做到一起成功或妥善处理部分失败。
6. compute 系列方法
compute 系列方法让调用方根据旧值算出新值,整个计算过程由 Map 负责同步。计算回调就是传给这些方法、用来生成新值的函数。下面在键缺失时创建一个计数器,之后的并发递增交给计数器自己处理:
LongAdder counter = counters.computeIfAbsent(
key,
ignored -> new LongAdder()
);
counter.increment();
回调执行期间,同一个桶上的其他更新要等它结束,所以回调要遵守这些回调约束:
- 计算要短,减少其他线程的等待时间。
- 网络请求和数据库访问放到专门的加载流程里,不要在回调里做不可控的 I/O。
- 回调里不要修改同一个 Map,无论是递归修改当前键,还是修改其他键。
- 失败时要自己处理已经产生的外部副作用,Map 的异常处理没法回滚外部系统。
在实现上,OpenJDK 21 对空桶执行 compute 时,会先放一个 ReservationNode 占住位置并对它加锁,再执行回调;非空桶则在相应的节点上同步执行。computeIfAbsent 如果发现首节点就是这个键且已经有值,会直接返回,不加锁。
computeIfAbsent 只负责按键创建映射。做一个完整的缓存,还要定义加载与淘汰策略:
- 加载超时后怎样结束等待。
- 已有的值什么时候刷新。
- 加载失败或者没有结果时,要不要缓存。
- 大量查询不存在的键时,怎样避免反复打到后端,也就是缓存穿透保护。
- 容量达到上限时淘汰哪些条目。
上面例子里的 LongAdder 是支持并发递增的累加器,计数本身的线程安全由它保证。但要注意,如果另一个线程把这个计数器从 Map 里删掉了,调用方手里的旧引用仍然可以递增,这些增量就写到了一个已经不在 Map 里的计数器上。所以计数和删除要按业务约定协调。
6.1 回调返回值与可变值
回调的返回值决定映射存不存在,返回的对象是不是线程安全,则由这个对象自己决定。
computeIfAbsent 的回调返回 null,这次计算就不建立映射,键仍然缺失;回调抛异常也一样。所以之后的调用还会再算一次,期间产生的外部副作用要自己控制。compute、computeIfPresent 或 merge 的回调返回 null,则会删除现有的映射;回调抛异常时,原来的映射保持不变。
另一个边界在值对象上。下面的代码里,Map 原子地创建了一个 List,之后才往 List 里追加元素:
var groups = new ConcurrentHashMap<String, List<String>>();
groups.computeIfAbsent("A", k -> new ArrayList<>()).add("x");
原子创建只保护 Map 里「"A" 对应哪个列表」这件事,后面的 ArrayList.add 是另一次操作。多个线程拿到同一个列表后同时 add,就会在 ArrayList 上发生竞争。可以换成线程安全的值对象,或者在 compute 里根据旧列表构造一个新的不可变列表,再替换映射。
7. null 键和值
ConcurrentHashMap 用 null 表示「当前没有映射」,所以 API 拒绝 null 键和 null 值:
// map.put("key", null); // 抛出 NullPointerException
这样 get(key) == null 就能直接说明当前没有这个键。如果允许 null 值,调用方还要再调用一次 containsKey,区分「没有映射」和「映射到了 null」。但在并发环境下,这两次调用之间映射可能已经变了,得不出可靠的结论。null 还被并行归约用作「没有结果」的标记,归约是把多个部分结果合并成一个结果的操作。
需要缓存「查过了、但没有值」这类结果时,可以存一个枚举或显式的状态对象,这样就能区分尚未加载、已查询但无值、加载失败三种情况。
8. 协作扩容
元素增多需要扩容时,旧数组里的节点要迁到一个更大的数组。OpenJDK 21 把桶按区间划分,参与扩容的线程各自领取一段区间去迁移。迁移完的旧桶里放一个 ForwardingNode,也就是指向新数组的转发节点。
更新操作遇到转发节点时,可以顺便帮忙迁移;读取遇到它,就跟着去新数组里找。所以扩容期间 Map 仍然能处理访问,迁移工作也由多个线程分担。不过扩容依然要消耗 CPU、内存带宽和新数组的空间,已知数据规模时,提前估好初始容量可以减少这些开销。
扩容期间的遍历同样是弱一致的,完整的观察范围见迭代一致性。
9. 热点键竞争
不同的桶可以并发更新,但同一个键的更新必须一个接一个地执行。如果所有请求都在更新同一个键,竞争仍然集中在一处:
counts.merge("all", 1L, Long::sum);
高频计数可以改用 LongAdder,它把并发递增分散到内部的多个计数单元,读取时再求和。竞争范围更大时,可以按业务维度分片,或者让各线程先在本地聚合、再批量合并;也可以改变数据的归属,让一个写者集中处理所有更新。
分片把一个值拆到了多个位置,所以要一并定义读取与维护规则:
- 读取时怎样找到所有分片。
- 各个分片什么时候过期。
- 部分更新失败时怎样容错。
- 最后怎样把所有增量汇总起来。
10. 常见问题
10.1 size 与业务限额
并发更新期间,size 返回的是调用过程中观察到的映射数量,返回之后其他线程仍然可以插入。所以「没到上限才插入」这样的容量控制,要把检查和插入放进同一套同步规则里。具体的快照边界见迭代一致性。
10.2 外部锁与多键操作
外部锁只有在所有访问者都遵守时,才能保护多键操作。ConcurrentHashMap 的方法用的是自己的内部同步,任何地方直接调用它们,都会绕过你约定的那把锁。所以多键更新要封装在统一的入口里;也可以改为整体替换不可变状态,或者交给单个写线程处理。
10.3 Hashtable 与 ConcurrentHashMap
Hashtable 的常用操作都在同一个实例锁上排队,不同的键也要互相等待。ConcurrentHashMap 用桶级协调缩小了等待范围,还提供单键的原子方法,遍历是弱一致的。新代码需要并发 Map 时可以优先考虑它,再确认它的一致性保证是否满足业务。
10.4 单键读取与更新时间
对单个键来说,get 反映的是读取开始时最近一次已经完成的更新。读和写同时发生时,可能读到旧值也可能读到新值,取决于两者实际的先后。连续读多个键时,每次观察的时刻都不同,所以要拿到完整的业务状态,仍然需要一致性协议。
11. 面试题卡片
12. 参考资料
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明