跳到主要内容
约 10 分钟3 张卡

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 外部锁与多键操作​

10.3 Hashtable 与 ConcurrentHashMap​

10.4 单键读取与更新时间​

11. 面试题卡片​

12. 参考资料​

来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明