ConcurrentHashMap（Java 8）源码分析

type

status

date

slug

summary

01 | 几个重要概念

ConcurrentHashMap 之所以是并发安全的，是因为它在容器初始化、元素修改等操作时采用了 CAS + synchronized 的机制。但是在介绍这些操作前，让我们先看一看 ConcurrentHashMap 中的几个重要概念，了解了这些概念之后，理解代码时会轻松许多。

三个重要字段

ConcurrentHashMap 中定义了许多字段，其中下面的三个字段比较重要：

table ：桶数组，其中保存了所有的键值对。数组中的每个位置都代表一个哈希桶，桶中保存哈希冲突的键值对。

nextTable ：扩容时使用，临时指向新的扩容后的桶数组。扩容结束后，会让 table 指向新的桶数组，nextTable 变回 null。

sizeCtl ：这个属性用于控制初始化桶数组和扩容操作。不同的值代表了不同的含义：

sizeCtl ＜ -1 时：表示 ConcurrentHashMap 正在扩容，而且通过它可以得知正在一起扩容的线程数。
sizeCtl == -1 时：表示 ConcurrentHashMap 正在初始化桶数组。
sizeCtl == 0 时：表示初始化桶数组时使用默认容量。
sizeCtl > 0 时：如果此时桶数组为 null，那么 sizeCtl 表示初始化时的容量。如果此时桶数组不为 null，那么sizeCtl 表示触发下次扩容时的键值对数量。

四种 Node 类型和特殊的哈希值

Node 及其子类

桶数组 table 中的每个位置是一个 Node 类型的元素，那么这些元素的实际类型都是 Node 吗？在这个位置代表的桶中，用于保存键值对的桶元素又是什么类型呢？实际上，ConcurrentHashMap 定义了多种类型用于具体表示桶数组和桶中的元素，其中 4 种类型较为重要，如下图所示：

1）Node ：链表相关

当桶数组中的一个位置是 Node 类型时，表示在这个位置代表的桶中，键值对是以链表的形式存储的。桶中用于保存键值对的桶元素也是 Node 类型，同时，桶数组中的这个位置元素也是整个链表的头节点，保存了第一个键值对。

Node 类型也是其它类型的父类。

2）TreeBin 和 TreeNode ：红黑树相关

当桶中的键值对数量过多时，桶中保存键值对的结构会从链表转为红黑树。此时，桶数组中对应位置的元素会变为 TreeBin 类型，表示这个位置代表的桶中的键值对是以红黑树的形式存储的。需要注意的是，桶数组中的这个 TreeBin 类型的元素不保存键值对，而是负责保存指向红黑树根结点的指针。实际保存键值对的是桶中的元素，也就是红黑树的节点，这些元素是 TreeNode 类型。

需要注意的是，从 TreeBin 的构造函数可以看到，TreeBin 节点的哈希值是固定值 -2。

3）ForwardingNode ：扩容相关

这个类型只有在扩容时才会出现。当哈希表在扩容时，会遍历旧的桶数组，将所有元素转移到新的桶数组中。转移是以桶为单位进行的，如果一个旧桶中的所有元素已经完成了转移，那么在旧的桶数组中，这个旧桶所在位置的元素会被转换成 ForwardingNode 类型，它保存了指向新的桶数组的指针，并提供了 find() 方法在新的桶数组中查找目标键值对。

这个类型有什么作用呢？当扩容没有结束时，ConcurrentHashMap 仍会先去旧的桶数组中查找目标键值对，如果对应的桶数组节点是 ForwardingNode 类型，那么说明其中的键值对已经被转移至新的桶数组中了，此时可以通过 ForwardingNode 提供的 find() 方法去新的桶数组中继续查找。

需要注意的是，从 ForwardingNode 的构造函数可以看到，ForwardingNode 节点的哈希值是固定值 -1。

特殊的哈希值

ConcurrentHashMap 内部会根据 key 的 hashCode 再做一次哈希运算，调用的函数如下：

这个函数有一个特点，就是计算出来的结果的最高位是 0，也就是保证哈希值为非负数。

这么做有一个好处，可以区分实际保存键值对的节点和其它特殊的节点，在后续的 PUT 等操作中，也可以根据节点的哈希值来快速判断桶的类型。从上面那些类的构造函数可以看到，两个特殊的类型 TreeBin 和 ForwardingNode 的哈希值是 -2 和 -1，它们都不保存键值对，只是标识这是个特殊的桶，而 Node 和 TreeNode 的哈希值就是 key 的哈希值，是非负值，它们都实际保存了键值对。

三个访问数组元素的方法

在并发环境中，共享资源需要考虑线程之间的竞争性、可见性和指令重排序的问题。在 ConcurrentHashMap 中，table 就是一个共享资源，因此，类提供了三个通过以 volatile 和 CAS 的语义访问数组元素的方法，通过 Unsafe 的方法，保证线程可以互斥地修改数据，修改后数据的其它线程可以立即可见，同时避免指令重排序。

1）tabAt ：获取元素

这个方法以 volatile 的语义，获取 tab 数组中索引为 i 的元素。

2）casTabAt ：修改元素

这个方法以 CAS 的方式，修改 tab 数组中索引为 i 的元素，将预期的旧值 c 修改为新值 v。

3）setTabAt ：添加元素

这个方法以 volatile 的语义，将值 v 写入 tab 数组索引为 i 的位置。

02 | 初始化

ConcurrentHashMap 的构造函数并没有创建桶数组，我们可以把初始化过程看成两个独立的步骤：对象的构造和桶数组的创建。

ConcurrentHashMap 对象的构造

ConcurrentHashMap 提供了多个构造函数，最终都会调用下面这个构造函数：

这个构造函数有三个参数：

initialCapacity 指定初始容量。这里的初始容量并不是指桶数组的长度，而是之后可能添加的键值对数量。桶数组的长度会根据这个初始容量计算。

loadFactor 指定负载因子。需要注意的是，构造函数中并没有保存这个负载因子，所有这里的负载因子只在这个构造函数中起作用，后续用于计算扩容阈值的负载因子是固定值 0.75。

concurrencyLevel 是我们预估的并发线程数。

整个过程包括了 5 个步骤：

校验参数合法性。

调整初始容量 initialCapacity，让其至少等于预估的并发线程数 concurrencyLevel。这是为了下一步计算桶数组的长度时，有足够数量的桶来支持并发线程的操作，减少竞争。

计算桶数组的最小长度。这一步考虑到了负载因子，确保能容纳 initialCapacity 个元素而不立即扩容。

计算桶数组的最终长度。tableSizeFor 让长度变为 2 的幂次方。

将计算出的容量 cap 赋值给 sizeCtl。此时桶数组为 null，所以 sizeCtl 的值表示之后桶数组初始化时的长度大小。

桶数组的创建

桶数组的创建是一种懒加载的形式，当第一次添加数据时才会被创建，创建时的数组长度就是构造函数中赋值给 sizeCtl 的值。源码如下所示，其中注释标注了代码的逻辑：

需要注意一下几点：

第 2 步和第 3 步是环环相扣的。sizeCtl 等于 -1 表示有线程正在创建桶数组，因此在第 3 步，线程创建数组前会将 sizeCtl 修改为 -1，同时，因为可能会有多个线程同时走到步骤 3，所以为了保证只有一个线程去创建数组，使用了 CAS。而当有线程正在创建数组时，第 2 步就可以提前过滤掉后续尝试创建数组的线程，让它们让出 CPU 进行等待。

第 4 步是必不可少的。假设线程 A 在第 1 步之后，第 2 步之前暂停了，随后线程 B 走完了全程，创建好了数组，还添加了键值对，此时线程 A 恢复执行，那么在线程 A 中，2、3 两步是畅通无阻的。如果没有步骤 4，那么线程 A 会重新创建一个新的桶数组，之前线程 B 添加的键值对就丢失了，这是非常严重的错误。因此，第 4 步就类似于双重检查，不能删去。

03 | GET

Get 操作比较简单，直接看代码注释吧。值得注意的是，Get 操作是无锁设计的，因为整个过程都没有修改哈希表中的状态。但是依赖了 volatile 的语义来保证内存可见性，如变量 table、Node.val、Node.next ，方法 tabAt 等。

04 | PUT

在向哈希表添加元素时，最终会调用 putVal 方法，方法里结合了 CAS 和 synchronized 来做并发控制。

源码（展开查看）

整个过程可以分为以下几个阶段：

1）参数校验和哈希优化

这里使用了上文提到的 spread 方法优化哈希值，同时保证哈希值为非负数，有助于后续的节点类型判断。

2）添加键值对：核心的循环逻辑

在循环中，利用 CAS 自旋和 synchronized 来处理并发竞争。每次进入循环的时候，都会重新获取桶数组 table，因为可能再次进入循环前，哈希表进行了扩容，导致 table 指向新的桶数组。

下面看看循环中做了些什么。

2.1）如果桶数组为空

如果桶数组是空的话，这里就会创建桶数组，整个过程在上文中有介绍。

2.2）如果插入的位置是个空桶

如果插入的位置是个空桶的话，那么新建一个 Node 节点封装键值对，然后桶数组的这个位置的值改为这个节点即可。

注意这里用了 CAS，如果失败的话，就重新进入循环尝试添加键值对。如果成功的话，就退出循环，因为是链表的第一个元素，所以不需要考虑转换为红黑树。

2.3）如果桶处于扩容迁移状态

之前有提到，ForwardingNode 的哈希值就是 MOVED ，说明这个桶中的元素已经转移到了扩容后的桶中，说明此时有其它线程正在扩容哈希表，为了提升扩容效率，当前线程会立即去帮助扩容。扩容完成后，再重新进入循环添加键值对。

2.4）将键值对添加进桶中

如果之前的条件都不满足，说明需要将键值对加进一个桶中。因为我们需要修改桶中的元素数量，而且不止这一个地方会修改桶（比如扩容等操作），所以这里使用了 synchronized 给这个桶的在桶数组中的头节点加锁，防止并发修改桶。

加锁之后，需要再次检查桶数组中的第 i 个位置还是不是之前获取到的桶，因为期间可能会发生扩容，从而引起桶的改变。

最后，在向链表结构的桶中添加键值对时，会统计链表中的元素数量。添加完成后，会根据数量判断是否需要转变为红黑树。

3）更新哈希表的元素数量

等到添加键值对成功后，会退出循环，最后将哈希表的元素数量加 1。

05 | 扩容

和 HashMap 一样，每次扩容时，新桶数组的长度都会变为原来的 2 倍，然后把旧桶数组中的元素迁移到新桶数组中。不一样的是，ConcurrentHashMap 为了提高扩容效率，会让多个线程一起参与扩容。为了协调这些线程，ConcurrentHashMap 把旧桶数组分成了多个区间，如下图所示。每当一个线程参与扩容时，就认领一个区间，这个区间中的所有桶就分配给这个线程去迁移，这些桶迁移完毕后，如果还有剩余的区间没有被分配，那么线程就从中再认领一个区间，重复上述过程。同样的，扩容时用了 CAS 和 synchronized 来进行并发控制。

扩容过程最终会调用 transfer 方法，源码如下（展开查看）：

整个过程可以分为多个阶段：

1）初始化阶段

初始化阶段主要做了两个工作：

根据 CPU 核数计算步长，这个步长就是每个线程每次负责迁移的桶的数量。注意步长最小是 MIN_TRANSFER_STRIDE 。

如果新的桶数组还是空的，那么创建一个新的。新的桶数组的长度是原来的 2 倍。

2）处理迁移

这里创建了一个 ForwardingNode 节点，当一个桶迁移完成后，旧的桶数组中对应的位置就会被替换为这个节点，表示这个桶已经完成迁移。同时这个节点还保存了新的桶数组，用于查询转发。

随后的循环中就是核心的迁移流程，让我们看一看每一次循环都做了什么。

2.1）任务分配

每个线程在给桶做迁移之前，首先要知道自己负责的是哪些桶。根据桶在数组中的位置，按照索引从大到小的顺序分配给来扩容的线程。首先，ransferIndex 会指向已分配的索引最小的桶，大于它的桶都已经被分配给其他线程了。当前线程会从 ransferIndex 开始，向前取 stride 个桶，这些桶就是这一轮次中，自己负责迁移的桶。然后更新 ransferIndex 的值，注意这里是 CAS 更新，避免和其它线程产生冲突。在后面的流程中，线程会从索引为 ransferIndex - 1 的桶开始迁移（用 i 指示），一直向前知道当前负责的桶都迁移完成。当本轮的所有桶都迁移完成后，就会再次重复上面的过程，去负责迁移新的 stride 个桶。分配前后的变量指向变化如下图所示：

2.2）检查桶数组中的所有桶是否已经迁移完成

首先看外部的条件 if (i < 0 || i >= n || i + n >= nextn) ，这里检查了 i 的值，如果 i 越界了，说明所有的桶都已经分配给线程去完成迁移工作了，所有线程在完成各自的迁移任务后肯定会走到这一步。

然后看内部的第 2 个条件 if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) ，既然所有桶已经分配完了，那么线程完成自己的任务后就会用 CAS 的方式将 sizeCtl 减 1，表示自己退出迁移流程了。然后 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) 会判断当前线程是不是最后一个退出的迁移线程，如果不是，就直接退出，如果是，就要把 finishing 置位 true，表示扩容结束，finishing 也只有在这里会被置位 true。注意，做完这些后，最后一个线程还没有退出，而是把 i 重新设置为 n，接着进行 for 循环，从最后一个桶开始重新检查，确保所有桶都已经迁移成功了。

然后回到内部的第 1 个条件 if (finishing) ，当执行到这里而且 finishing 为 true 时，说明最后一个扩容线程检查完了所有的桶，确保它们都已经迁移成功了，那么就做一些收尾工作，把 nextTable 置为 nul，table 指向新的哈希表，sizeCtl 置为新的扩容阈值。

2.3）迁移桶

最后就是根据桶的类型来迁移每个桶了，这里不再赘述。当一个桶迁移完成后，会将旧的桶数组中的对应位置节点修改为 ForwardingNode 节点。需要注意的是，在给一个桶迁移之前，需要给这个桶加上 synchronized 锁，因为可能会有其它操作对桶中的元素进行增删，扩容时是无法感知的，因此直接加锁以避免这种情况。

06 | 总结

ConcurrentHashMap 是线程安全的。ConcurrentHashMap 中的一些共享状态会用 volatile 修饰，保证所有线程都可以看见最新的数据。Get 方法是无锁设计，以此提高查找效率。而涉及到 ConcurrentHashMap 的状态的修改时，会通过 CAS 或 synchronized 来进行并发控制，总体上看，当涉及到桶中元素的增删、转移等修改时，会给这个桶加上 synchronized 锁，而其它情况更多的是用 CAS 加自旋的形式来保证数据的线程安全性。