那些年你啃过的ConcurrentHashMap

一时失言乱红尘 2023-10-11 18:14 2阅读 0赞

#### 文章目录 ####

*  1.基础回顾
 *  2.红黑树
 *   *  红黑树插入数据
 *  3.多线程竞争下的读写操作
 *  4.扩容原理
 *  5.正在扩容 && 有多个线程正在竞争
 *   *  5.1 扩容期间的读操作
     *  5.2 扩容期间的写操作
 *  6.总结

最近迷上了并发编程。并发这玩意怎么说呢，就是你平时工作用不到，一用就用在面试上。这不，又卷起了并发容器。

那说起并发容器，你一定也知道那几个，CopyOnWriteArrayList、并发队列BlockingQueue，等等。但是作为面试的典中典，聊到并发容器就无法绕开ConcurrentHashMap。

![在这里插入图片描述][c9f248e5158049989d107d7b0de8c862.png_pic_center]

以下的技术点都基于JDK1.8~

因为jdk1.7及以前都是数组+链表的方式进行构建的。

我们先来回顾一下一些常见的基础问题，当然也是一些中小厂爱问的八股问题。

## 1.基础回顾 ##

在**JDK1.7**以前，ConcurrentHashMap是由 **Segment 数组**结构和**HashEntry数组**结构组成。

Segment 是一种可重入锁ReentrantLock，在 ConcurrentHashMap 里扮演锁的角色。

HashEntry 则用于存储键值对数据。

一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment的结构和HashMap 类似，是一种**数组和链表**结构， 一个 Segment 里包含一个**HashEntry 数组**，每个 HashEntry 是一个**链表结构**的元素， 每个 Segment 守护者一个 HashEntry 数组里的元素, 当对 HashEntry 数组的数据进行修改时，必须首先获得它对应的 Segment 锁。

使用ConcurrentHashMap**分段锁**的思想，将HashMap进行切割，把HashMap中的哈希数组切分成小数组，每个小数组有n个HashEntry 组成，其中小数组继承自**ReentrantLock**（可重入锁），这个小数组名叫**Segment**。

![在这里插入图片描述][5cdd26b4d2424d73a5cbfd7bfb591d52.png_pic_center]

JDK1.8中取消了Segment分段锁，采用 **CAS + synchronized** 来保证并发安全，ConcurrentHashMap 中synchronized 只锁定当前链表或红黑二叉树的首节点，只要节点 hash 不冲突，就不会产生并发。  
![在这里插入图片描述][a26ddcf1aff048d39ecf8587a0354124.png_pic_center]

## 2.红黑树 ##

在谈到红黑树的时候，我其实有必要给大家说明一下为什么HashMap要采用红黑树的数据结构来存储数据，当然这个 也是经常被问到的一个考点。

**数据比较少**的时候，链表的性能要好于红黑树，所以HashMap一上来并没有直接采用红黑树。

树化的阈值为**8**，为什么呢，因为正常业务情况下都不会出现链表的长度超过8。只有在恶意被攻击的情况下，如：DOS攻击，等才会出现大量的链表长度超过的情况，所以使用红黑树用来避免**DOS攻击**，防止链表超长时性能下降，同时，一般情况下认为树化是**偶然情况**。

其次，hash值如果足够随机，则在hash表内按泊松分布，在负载因子0.75的情况下，长度超过8的链表出现的概率是0.00000006，选择8的原因就是让树化的几率非常小。

树化的两个条件：链表长度超过树化阈值8，而且数组容量>=64

退化的情况：

*  在扩容拆分树时，树元素个数小于等于6则会退化为链表退化;
 *  remove树节点时，若root、root.left、root.right、root.left.left有一个为空，也会退化为链表

红黑树也是一种**平衡二叉树**，每个节点有一个储存位表示节点的颜色，可以是红色或者黑色。

通过对任意一条从**根到叶子**的路径上各个节点**着色方式**的限制，红黑树确保没有任意一条从根到叶子的路径**超过最短路径的两倍**，因此红黑树是一种**弱平衡二叉树**。

相对于AVL树来说，红黑树的**旋转次数少**，对于搜索、插入、删除多的操作下用红黑树。

下面我们继续讨论JDK1.8这里的红黑树。

红黑树，准确的来说是一个**TreeBin代理类**，它作为红黑树的具体实现起**存储作用**，而TreeNode是封装红黑树的数据结构，所以你可以理解TreeBin就是**封装TreeNode的一个容器**。

红黑树在ConcurrentHashMap里面的体现是一个**双向链表**：  
![在这里插入图片描述][cc2b9811596b460793a2ee157b719b8a.png_pic_center]

### 红黑树插入数据 ###

在这里，红黑树维护一个字段**dir**。

**在插入数据的时候会获取节点的hash值，从而与当前节点p的hash值比较，若插入节点的hash小于当前节点，则dir的值为-1，否则为1：**  
![在这里插入图片描述][57e71e4c430f4a50b4eed391e5b08a7c.png_pic_center]

所以，当dir的值为-1时，就代表插入节点需要插入到当前节点的**左子节点**或者继续往**左子树上**查找

相反如果dir值为1则**向右查找**，这里的规则和二叉查找树的规则是一样的。

## 3.多线程竞争下的读写操作 ##

由于读操作本身就是天然线程安全的。所以多个线程对同一个桶位同时读并不会有什么问题。

但若是相互竞争的写操作，就是通过**Synchronized锁**的方式来保证某个桶位同一时刻只有一个线程能获取到资源。

通过源码可以看到，put()方法的核心是**putVal()**:  
![在这里插入图片描述][8ad327556f32463ca6a2cf7f1fea0caa.png_pic_center]

putVal()很长，它主要是通过Synchronized去锁住每一个节点保证并发的安全性。

在这里最为重要的两点：

*  一是判断你put进去的这个元素，是**处于链表还是处于红黑树**上；
 *  二就是判断当前插入的key是否与链表或者红黑树上的某个元素一致。  
    如果当前插入key与链表当中所有元素的key都不一致时，那么当前的插入操作就追加到链表的末尾。否则就替换掉key对应的value。

![在这里插入图片描述][66c2cedcd9744e35b0c6d0e770927073.png_pic_center]

## 4.扩容原理 ##

在知道扩容原理之前，得知道什么情况会导致扩容。

因此需要知道的两个重要字段：

*  **MIN\_TREEIFY\_CAPACITY** ：数组初始长度，默认为64
 *  **TREEIFY\_THRESHOLD** ：树化阈值，指定桶位链表长度达到8的话，就可能发生树化操作

线程往桶里面新增每一个元素，都会对链表的长度进行判断，只有元素个数大于阈值MIN\_TREEIFY\_CAPACITY并且链表长度大于8，才会调用**treeifyBin()**把链表转化为红黑树，否则就会进行扩容操作。

这里的扩容，指的就是扩大数组的桶个数，从而装下更多的元素。

除此之外，扩容还维护了另一重要的字段**sizeCtl**：  
![在这里插入图片描述][8206bb5c04df4f388ee8ee0d31ecf13e.png_pic_center]

通过翻译，我们可以知道这个字段有三种状态：

*  sizeCtl < 0：若为-1则起标记作用，告知其它线程此时**正在初始化**；若为其它的值表示当前table正在扩容
 *  sizeCtl = 0：表示创建table数组时**还未进行扩容**，没有指定的初始容量
 *  sizeCtl > 0：表示当table初始化后下次扩容的触发条件字段的值可以转化为32位的二进制数值
    
     *  它的高16位表示**扩容标识戳**，用来标识**扩容的范围**，如从长度16扩容到32；
     *  低16位表示当前参与扩容的**线程数量**。

![在这里插入图片描述][d5f0256051cb4c12b7fac7c9d96ed911.png_pic_center]

扩容操作会新建一个长度更大的数组，然后将老数组上的元素全部迁移到新的数组去。

<table> 
 <tbody> 
  <tr> 
   <td><b>扩容的本质目的是为了减少桶位链表的长度，提高查询效率。因为链表的查询复杂度是O(n)，如果链表过长就会影响查询效率。</b></td> 
  </tr> 
 </tbody> 
</table>

假设桶位的长度从16扩容到32，说明桶位变多了，那迁移到新数组后就需要有元素去到新的桶位。

这就需要通过一些算法将老数组和新数组的元素位置做一个映射。因为扩容后元素有的需要迁移到新的位置，有的还是处于和老数组一样的位置，只不过是换了一个数组。

如何计算出这个元素迁移后要呆在哪个桶位呢？这里使用了一个**按位与**的算法。

就是将这个桶位**key的hash值&(扩容前数组长度 - 1)**

*  若生成的值等于0则不需要迁移
 *  否则就要进行迁移。

并且维护两个变量**ln和hn**代表是否需要进行位置迁移。

然后采用**尾插法**将元素插入。这就是**LastRun机制**。  
![在这里插入图片描述][08e2c5c873ae47bc8ce53454bd738865.png_pic_center]

<table> 
 <tbody> 
  <tr> 
   <td>注：尾插法指的就是后面插入的元素都处于前一个元素的后面</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][bd1ca524ae3148c0bf3451b4a20461ab.png_pic_center]

这里简单普通的扩容是没什么问题的，大多数场景都和HashMap的扩容是一样的。

问题就在于当前是处于并发环境的，而扩容也需要时间。

## 5.正在扩容 && 有多个线程正在竞争 ##

所以，比较复杂的场景来了。若是桶位正在扩容，且有多个线程正在竞争读写咋办？

没关系，我们依然分情况来讨论。

### 5.1 扩容期间的读操作 ###

如果扩容期间，有线程进行元素的读取，比如你去get()某个key的value，那读不读的到呢？

答案是可以。但是前提是你这个节点已经**迁移结束**，**如果你是一个正在扩容迁移的节点，那就访问不到**。

具体的操作，就是去调用**find()**。

当一个桶位要进行数据迁移，就会往这个桶位上放置一个**ForwardingNode节点**。除此之外还需要去标识这个节点是正在迁移还是已经迁移结束了的；

在这里我们统称：

*  **迁移前**的桶位节点叫老节点
 *  **迁移后**的桶位节点叫新节点。

当其中某一个节点迁移完成后，就会在老节点上添加一个**fwd引用**，它指向**新节点的地址**。

所以当某个线程访问了这个节点，看到它上面存在**fwd**引用，就说明当前table正在扩容，那么就会根据这个引用上的**newtable字段**去新数组的对应桶位上找到数据然后返回。  
![在这里插入图片描述][a83a821fdf9044608b920f51fde422e4.png_pic_center]

### 5.2 扩容期间的写操作 ###

写操作相较于读操作会更加复杂一点，原因就是读操作只需要获取对应数据返回就行了，而写操作还要修改数据，所以当一个写线程来修改数据刚好碰到容器处于扩容期间，那么它还要**协助容器进行扩容**。

具体的扩容操作依然还要分情况，假如访问的桶位数据还没有被迁移走的话，那就直接竞争锁，然后在老节点上进行操作就行。

但是假如线程修改的节点正好是一个**fwd**节点，说明当前节点正处于扩容操作，那么为了节约线程数并且快速完成任务，当前线程就会进行协助扩容。如果有多个线程进行同时写，那么它们都会调用**helpTransfer()**进行协助扩容。

这里协助扩容的方式就是拿到一个**扩容标识戳**，这个标识戳的作用就是用来标识扩大的容量大小。

因为每个线程都是独立的嘛，互不通信，但是它们要做的事情是相同的，就是将桶位扩大相同的值，所以它们就必须拿到这个**相同**的标识戳，只有**标识戳一致**才会进行扩容。

假设一个容器从16个桶位扩容到32个桶位，有线程A、B两个线程。

若A触发了扩容的机制，那么线程A就会进行扩容，此时线程B也来进行写操作，发现正在扩容就会进入到协助扩容的步骤中去。

所以线程A和线程B共同负责桶位的扩容。

一个线程负责扩容的桶位个数，是根据**CPU核心数**来算的。最少是16个，也就是一个线程最少要负责16个元素的扩容：

我们在上面有提过，**sizeCtl**转化为32位后，它的低16位是表示**当前参与扩容的线程数量**。

所以当A线程触发了扩容之后，它就会将sizeCtl低16位的最后一位值+1，表示扩容线程多了一位，当它退出扩容时又会将最后一位的值-1，表示扩容线程少了一位，就这样各个线程共同维护这个字段。  
![在这里插入图片描述][0d8dccf4967549a09df13a276b8b7060.png_pic_center]

所以你一定会好奇了：那我要是最后一个退出扩容的线程要怎么维护啊？

是的，**最后一个线程**还有一些别的事情要做。当某一个线程完成任务后去判断**sizeCtl**的值得时候，发现它的低16位只剩下最后一位是1，再减下去就是0了，那就代表它是最后一个退出扩容的线程。此时它还需要去检查一遍老的table数组，判断是否还有遗漏的**slot**没有迁移。

具体的操作就是去**轮询检查**是否还留有**fwd**节点，如果没有的话代表迁移完成，如果有的话还需要继续将它迁移到新的桶位。

由于源码非常长，所以我们就不贴全部源码了，通过流程图的方式来帮助大家理解这个扩容期间的操作：  
![在这里插入图片描述][d7147938a9894ca083719080d8459d39.png_pic_center]

## 6.总结 ##

有的童鞋在看Juc这一块的时候会去背诵源码，将方法的调用链都讲的头头是道，我认为没有必要，相反面试官可能会觉得你过于抽象，背的这么清楚。

**并发的核心在于如何用手段去解决可能遇到的安全问题，并且让它更高效点，面试的目的也是为了体现你思维能力。**

[c9f248e5158049989d107d7b0de8c862.png_pic_center]: https://img-blog.csdnimg.cn/c9f248e5158049989d107d7b0de8c862.png#pic_center
[5cdd26b4d2424d73a5cbfd7bfb591d52.png_pic_center]: https://img-blog.csdnimg.cn/5cdd26b4d2424d73a5cbfd7bfb591d52.png#pic_center
[a26ddcf1aff048d39ecf8587a0354124.png_pic_center]: https://img-blog.csdnimg.cn/a26ddcf1aff048d39ecf8587a0354124.png#pic_center
[cc2b9811596b460793a2ee157b719b8a.png_pic_center]: https://img-blog.csdnimg.cn/cc2b9811596b460793a2ee157b719b8a.png#pic_center
[57e71e4c430f4a50b4eed391e5b08a7c.png_pic_center]: https://img-blog.csdnimg.cn/57e71e4c430f4a50b4eed391e5b08a7c.png#pic_center
[8ad327556f32463ca6a2cf7f1fea0caa.png_pic_center]: https://img-blog.csdnimg.cn/8ad327556f32463ca6a2cf7f1fea0caa.png#pic_center
[66c2cedcd9744e35b0c6d0e770927073.png_pic_center]: https://img-blog.csdnimg.cn/66c2cedcd9744e35b0c6d0e770927073.png#pic_center
[8206bb5c04df4f388ee8ee0d31ecf13e.png_pic_center]: https://img-blog.csdnimg.cn/8206bb5c04df4f388ee8ee0d31ecf13e.png#pic_center
[d5f0256051cb4c12b7fac7c9d96ed911.png_pic_center]: https://img-blog.csdnimg.cn/d5f0256051cb4c12b7fac7c9d96ed911.png#pic_center
[08e2c5c873ae47bc8ce53454bd738865.png_pic_center]: https://img-blog.csdnimg.cn/08e2c5c873ae47bc8ce53454bd738865.png#pic_center
[bd1ca524ae3148c0bf3451b4a20461ab.png_pic_center]: https://img-blog.csdnimg.cn/bd1ca524ae3148c0bf3451b4a20461ab.png#pic_center
[a83a821fdf9044608b920f51fde422e4.png_pic_center]: https://img-blog.csdnimg.cn/a83a821fdf9044608b920f51fde422e4.png#pic_center
[0d8dccf4967549a09df13a276b8b7060.png_pic_center]: https://img-blog.csdnimg.cn/0d8dccf4967549a09df13a276b8b7060.png#pic_center
[d7147938a9894ca083719080d8459d39.png_pic_center]: https://img-blog.csdnimg.cn/d7147938a9894ca083719080d8459d39.png#pic_center