深度分析ConcurrentHashMap原理分析

ConcurrentHashMap的初步使用及场景

CHM的使用

ConcurrentHashMap是J.U.C包里面提供的一个线程安全并且高效的HashMap，所以ConcurrentHashMap在并发编程的场景中使用的频率比较高，那么这一节课我们就从ConcurrentHashMap的使用上以及源码层面来分析ConcurrentHashMap到底是如何实现安全性的

api使用

ConcurrentHashMap是Map的派生类，所以api基本和Hashmap是类似，主要就是put、get这些方法，接下来基于ConcurrentHashMap的put和get这两个方法作为切入点来分析ConcurrentHashMap的源码实现

ConcurrentHashMap的源码分析

先要做一个说明，这节课分析的ConcurrentHashMap是基于Jdk1.8的版本。 JDK1.7和Jdk1.8版本的变化 ConcurrentHashMap和HashMap的实现原理是差不多的，但是因为ConcurrentHashMap需要支持并发操作，所以在实现上要比hashmap稍微复杂一些。 在JDK1.7的实现上，ConrruentHashMap由一个个Segment组成，简单来说，ConcurrentHashMap是一个Segment数组，它通过继承ReentrantLock来进行加锁，通过每次锁住一个segment来保证每个segment内的操作的线程安全性从而实现全局线程安全。整个结构图如下

当每个操作分布在不同的segment上的时候，默认情况下，理论上可以同时支持16个线程的并发写入。 相比于1.7版本，它做了两个改进

1. 取消了segment分段设计，直接使用Node数组来保存数据，并且采用Node数组元素作为锁来实现每一行数据进行加锁来进一步减少并发冲突的概率

2. 将原本数组+单向链表的数据结构变更为了数组+单向链表+红黑树的结构。为什么要引入红黑树呢？在正常情况下，key hash之后如果能够很均匀的分散在数组中，那么table数组中的每个队列的长度主要为0或者1.但是实际情况下，还是会存在一些队列长度过长的情况。如果还采用单向列表方式，那么查询某个节点的时间复杂度就变为O(n); 因此对于队列长度超过8的列表，JDK1.8采用了红黑树的结构，那么查询的时间复杂度就会降低到O(logN),可以提升查找的性能； 

   

这个结构和JDK1.8版本中的Hashmap的实现结构基本一致，但是为了保证线程安全性，ConcurrentHashMap的实现会稍微复杂一下。接下来我们从源码层面来了解一下它的原理. 我们基于put和get方法来分析它的实现即可

put方法第一阶段

假如在上面这段代码中存在两个线程，在不加锁的情况下：线程A成功执行casTabAt操作后，随后的线程B可以通过tabAt方法立刻看到table[i]的改变。原因如下：线程A的casTabAt操作，具有volatile读写相同的内存语义，根据volatile的happens-before规则：线程A的casTabAt操作，一定对线程B的tabAt操作可见

initTable

数组初始化方法，这个方法比较简单，就是初始化一个合适大小的数组 sizeCtl这个要单独说一下，如果没搞懂这个属性的意义，可能会被搞晕 这个标志是在Node数组初始化或者扩容的时候的一个控制位标识，负数代表正在进行初始化或者扩容操作 -1 代表正在初始化 -N 代表有N-1有二个线程正在进行扩容操作，这里不是简单的理解成n个线程，sizeCtl就是-N,这块后续在讲扩容的时候会说明 0标识Node数组还没有被初始化，正数代表初始化或者下一次扩容的大小

tabAt

该方法获取对象中offset偏移地址对应的对象field的值。实际上这段代码的含义等价于tab[i], 但是为什么不直接使用tab[i]来计算呢？ getObjectVolatile，一旦看到volatile关键字，就表示可见性。因为对volatile写操作happen-before于volatile读操作，因此其他线程对table的修改均对get读取可见； 虽然table数组本身是增加了volatile属性，但是“volatile的数组只针对数组的引用具有volatile的语义，而不是它的元素”。 所以如果有其他线程对这个数组的元素进行写操作，那么当前线程来读的时候不一定能读到最新的值。 出于性能考虑，Doug Lea直接通过Unsafe类来对table进行操作。

图解分析

put方法第二阶段

在putVal方法执行完成以后，会通过addCount来增加ConcurrentHashMap中的元素个数，并且还会可能触发扩容操作。这里会有两个非常经典的设计

1. 高并发下的扩容

2. 如何保证addCount的数据安全性以及性能

addCount

在putVal最后调用addCount的时候，传递了两个参数，分别是1和binCount(链表长度)，看看addCount方法里面做了什么操作 x表示这次需要在表中增加的元素个数，check参数表示是否需要进行扩容检查，大于等于0都需要进行检查

CounterCells解释

ConcurrentHashMap是采用CounterCell数组来记录元素个数的，像一般的集合记录集合大小，直接定义一个size的成员变量即可，当出现改变的时候只要更新这个变量就行。为什么ConcurrentHashMap要用这种形式来处理呢？ 问题还是处在并发上，ConcurrentHashMap是并发集合，如果用一个成员变量来统计元素个数的话，为了保证并发情况下共享变量的的难全兴，势必会需要通过加锁或者自旋来实现，如果竞争比较激烈的情况下，size的设置上会出现比较大的冲突反而影响了性能，所以在ConcurrentHashMap采用了分片的方法来记录大小，具体什么意思，我们来分析下

fullAddCount源码分析

fullAddCount主要是用来初始化CounterCell，来记录元素个数，里面包含扩容，初始化等操作

初始化CounterCells数组

CounterCells初始化图解

初始化长度为2的数组，然后随机得到指定的一个数组下标，将需要新增的值加入到对应下标位置处

transfer扩容阶段

判断是否需要扩容，也就是当更新后的键值对总数baseCount >= 阈值sizeCtl时，进行rehash，这里面会有两个逻辑。

1. 如果当前正在处于扩容阶段，则当前线程会加入并且协助扩容

2. 如果当前没有在扩容，则直接触发扩容操作

resizeStamp

这块逻辑要理解起来，也有一点复杂。 resizeStamp用来生成一个和扩容有关的扩容戳，具体有什么作用呢？我们基于它的实现来做一个分析

transfer

扩容是ConcurrentHashMap的精华之一，扩容操作的核心在于数据的转移，在单线程环境下数据的转移很简单，无非就是把旧数组中的数据迁移到新的数组。但是这在多线程环境下，在扩容的时候其他线程也可能正在添加元素，这时又触发了扩容怎么办？可能大家想到的第一个解决方案是加互斥锁，把转移过程锁住，虽然是可行的解决方案，但是会带来较大的性能开销。因为互斥锁会导致所有访问临界区的线程陷入到阻塞状态，持有锁的线程耗时越长，其他竞争线程就会一直被阻塞，导致吞吐量较低。而且还可能导致死锁。 而ConcurrentHashMap并没有直接加锁，而是采用CAS实现无锁的并发同步策略，最精华的部分是它可以利用多线程来进行协同扩容 简单来说，它把Node数组当作多个线程之间共享的任务队列，然后通过维护一个指针来划分每个线程锁负责的区间，每个线程通过区间逆向遍历来实现扩容，一个已经迁移完的bucket会被替换为一个ForwardingNode节点，标记当前bucket已经被其他线程迁移完了。接下来分析一下它的源码实现 1、fwd:这个类是个标识类，用于指向新表用的，其他线程遇到这个类会主动跳过这个类，因为这个类要么就是扩容迁移正在进行，要么就是已经完成扩容迁移，也就是这个类要保证线程安全，再进行操作。 2、advance:这个变量是用于提示代码是否进行推进处理，也就是当前桶处理完，处理下一个桶的标识 3、finishing:这个变量用于提示扩容是否结束用的

扩容过程图解

ConcurrentHashMap支持并发扩容，实现方式是，把Node数组进行拆分，让每个线程处理自己的区域，假设table数组总长度是64，默认情况下，那么每个线程可以分到16个bucket。 然后每个线程处理的范围，按照倒序来做迁移 通过for自循环处理每个槽位中的链表元素，默认advace为真，通过CAS设置transferIndex属性值，并初始化i和bound值，i指当前处理的槽位序号，bound指需要处理的槽位边界，先处理槽位31的节点； （bound,i） =(16,31) 从31的位置往前推动。

假设这个时候ThreadA在进行transfer，那么逻辑图表示如下

在当前假设条件下，槽位15中没有节点，则通过CAS插入在第二步中初始化的ForwardingNode节点，用于告诉其它线程该槽位已经处理过了；

sizeCtl扩容退出机制

在扩容操作transfer的第2414行，代码如下

高低位原理分析

ConcurrentHashMap在做链表迁移时，会用高低位来实现，这里有两个问题要分析一下

如何实现高低位链表的区分 假如我们有这样一个队列

第14个槽位插入新节点之后，链表元素个数已经达到了8，且数组长度为16，优先通过扩容来缓解链表过长的问题，扩容这块的图解稍后再分析，先分析高低位扩容的原理 假如当前线程正在处理槽位为14的节点，它是一个链表结构，在代码中，首先定义两个变量节点ln和hn，实际就是lowNode和HighNode，分别保存hash值的第x位为0和不等于0的节点 通过fn&n可以把这个链表中的元素分为两类，A类是hash值的第X位为0，B类是hash值的第x位为不等于0（至于为什么要这么区分，稍后分析），并且通过lastRun记录最后要处理的节点。最终要达到的目的是，A类的链表保持位置不动，B类的链表为14+16(扩容增加的长度)=30 我们把14槽位的链表单独伶出来，我们用蓝色表示 fn&n=0的节点，假如链表的分类是这样

接着，通过CAS操作，把hn链放在i+n也就是14+16的位置，ln链保持原来的位置不动。并且设置当前节点为fwd，表示已经被当前线程迁移完了

迁移完成以后的数据分布如下

为什么要做高低位的划分

要想了解这么设计的目的，我们需要从ConcurrentHashMap的根据下标获取对象的算法来看，在putVal方法中1018行

扩容结束以后的退出机制

如果线程扩容结束，那么需要退出，就会执行transfer方法的如下代码

put方法第三阶段

如果对应的节点存在，判断这个节点的hash是不是等于MOVED(-1)，说明当前节点是ForwardingNode节点， 意味着有其他线程正在进行扩容，那么当前现在直接帮助它进行扩容，因此调用helpTransfer方法

put方法第四阶段

这个方法的主要作用是，如果被添加的节点的位置已经存在节点的时候，需要以链表的方式加入到节点中 如果当前节点已经是一颗红黑树，那么就会按照红黑树的规则将当前节点加入到红黑树中

put方法第四个阶段

判断链表的长度是否已经达到临界值8. 如果达到了临界值，这个时候会根据当前数组的长度来决定是扩容还是将链表转化为红黑树。也就是说如果当前数组的长度小于64，就会先扩容。否则，会把当前链表转化为红黑树

treeifyBin

在putVal的最后部分，有一个判断，如果链表长度大于8，那么就会触发扩容或者红黑树的转化操作。

tryPresize

tryPresize里面部分代码和addCount的部分代码类似，看起来会稍微简单一些