ConcurrentHashMap 实现原理与使用

阳光穿透心脏的1/2处 2022-12-05 15:20 195阅读 0赞

#### 一、ConcurrentHashMap ####

> ConcurrentHashMap 采用**锁分段技术**有效提高了并发访问率，首先将数据分成一段一段地存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问；

##### 1. ConcurrentHashMap 的结构 #####

> ConcurrentHashMap 由 Segment 数组结构 和 HashEntry 数组结构组成，一个ConcurrentHashMap 里面包含一个 Segment 数组（数组链表结构），一个 Segment 里面包含一个 HashEntry 数组 （链表结构），每个 Segment 守护一个HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得它对应的 Segment 锁  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0NjQ2Mw_size_16_color_FFFFFF_t_70_pic_center]

##### 2. ConcurrentHashMap 的初始化 #####

> 通过 initialCapacity 、loadFactor 、concurrentLevel 等几个参数来初始化segment 数组，段偏移量 segmentShift 、段掩码 segmentMask 和每个 segment 里的 HashEntry 数组；

<table> 
 <thead> 
  <tr> 
   <th>初始化参数</th> 
   <th>作用</th> 
   <th>默认值</th> 
   <th>最大值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>initialCapacity</td> 
   <td>是ConcurrentHsahMap 的初始化参数</td> 
   <td>16</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>loadFactor</td> 
   <td>是每个 segment 的负载因子</td> 
   <td>0.75</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>concurrencyLevel</td> 
   <td>–</td> 
   <td>16</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>segmentShift</td> 
   <td>用于定位参与散列运算</td> 
   <td>–</td> 
   <td>16</td> 
  </tr> 
  <tr> 
   <td>segmentMask</td> 
   <td>散列运算的掩码</td> 
   <td>–</td> 
   <td>65535</td> 
  </tr> 
 </tbody> 
</table>

##### 3. 定位Segment #####

> 在使用分段锁时，插入和获取元素都必须先通过散列算法来定位到 Segment ，首先使用 Wang/Jenkins hash 的变种算法对元素的 hashcode 进行一次再散列，其目的时减少散列冲突，使元素能够均匀的分布在不同的 Segment 上，从而提高容器的存取率；

##### 4. ConcurrentHashMap 的操作 #####

###### （1）get 操作 ######

> 先经过一次再散列，然后使用这个散列值通过散列运算定位到 Segment ，再通过散列算法定位到元素，整个 get 过程不需要加锁，除非读到的值为空猜会加锁重读，所以该操作很高效；

###### （2）put 操作 ######

> 该操作首先定位到 Segment 然后再 Segment 里进行插入操作，插入时先判断 Segment 里的 HashEntry 数组是否需要扩容，如果超所阈值，再扩充为原来的两倍，然后定位添加的元素的位置，然后放入 HashEntry 数组里；

###### （3）size 操作 ######

> 想要统计ConcuurentHashMap 里元素大小，先尝试 2 次通过不锁住 Segment 的方法来统计各个 Segment 大小，如果统计过程中，容器的 count 发生了变化，则在采用加锁的方式来统计所有 Segment 的大小；

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0NjQ2Mw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/fa8c8d0056a342e0a0870b56ebf5b16b.png