文档章节

ConcurrentHashMap源码解读

edwardGe
 edwardGe
发布于 08/18 15:05
字数 1583
阅读 6
收藏 0
JDK

部分内容转自:http://jiabinyuan.xyz/#/app/archive/detail/25

内部结构

内部采用了segment结构,每一个segment相当于一个hashtable。看下面的结构图:

从图的结构我们可以了解到,ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作,第一次Hash定位到Segment,第二次Hash定位到元素所在的链表的头部,因此,这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长,但是带来的好处是写操作的时候可以只对元素所在的Segment进行加锁即可,不会影响到其他的Segment,这样,在最理想的情况下,ConcurrentHashMap可以最高同时支持Segment数量大小的写操作(刚好这些写操作都非常平均地分布在所有的Segment上),所以,通过这一种结构,ConcurrentHashMap的并发能力可以大大的提高。

segment的数据结构

static final class Segment<K,V> extends ReentrantLock implements Serializable {  
    transient volatile int count; //Segment中元素的数量
    transient int modCount;  //对table的大小造成影响的操作的数量(比如put或者remove操作,这个值只增不减)
    transient int threshold;  //阈值,Segment里面元素的数量超过这个值依旧就会对Segment进行扩容
    transient volatile HashEntry<K,V>[] table;  //链表数组,数组中的每一个元素代表了一个链表的头部
    final float loadFactor;  //负载因子,用于确定threshold
} 

HashEntry的数据结构(segment中的元素以HashEntry的形式存放在链表数组中)

static final class HashEntry<K,V> {  
    final K key;  
    final int hash;  
    volatile V value;  
    final HashEntry<K,V> next;  
} 

除value以外,其他变量都是final的,这是为了防止链表结构被破坏,出现ConcurrentModification的情况。

初始化

CurrentHashMap的初始化一共有三个参数:

  • initialCapacity:表示初始的容量
  • loadFactor:表示负载参数
  • concurrentLevel:ConcurrentHashMap内部的Segment的数量

ConcurrentLevel一经指定,不可改变,后续如果ConcurrentHashMap的元素数量增加导致ConrruentHashMap需要扩容,ConcurrentHashMap不会增加Segment的数量,而只会增加Segment中链表数组的容量大小,这样的好处是扩容过程不需要对整个ConcurrentHashMap做rehash,而只需要对Segment里面的元素做一次rehash就可以了。

整个ConcurrentHashMap的初始化方法还是非常简单的,先是根据concurrentLevel来new出Segment,这里Segment的数量是不大于concurrentLevel的最大的2的指数,就是说Segment的数量永远是2的指数个,这样的好处是方便采用移位操作来进行hash,加快hash的过程。接下来就是根据intialCapacity确定每个Segment的容量的大小,每一个Segment的容量大小也是2的指数,同样使为了加快hash的过程。

这边需要特别注意一下两个变量,分别是segmentShift和segmentMask,这两个变量在后面将会起到很大的作用,假设构造函数确定了Segment的数量是2的n次方,那么segmentShift就等于32减去n,而segmentMask就等于2的n次方减一。

get操作

get操作是不用加锁的,主要过程是:

  1. 先hash到具体是哪一个segment(segmentFor方法中通过位操作确定到底在哪一个segment中)
  2. 对count进行了一次判断(count表示Segment中元素的数量,count是volatile的,保证了写操作对后续的读操作都是可见的,这样后面get的后续操作就可以拿到完整的元素内容。)
  3. 在segment里面hash到具体是哪一个链表
  4. 遍历这个链表,得到key对应的value(有可能取到的value是null,这时候可能这个kv正在put操作,这时就需要加锁保证取出来的值是完整的)

put操作

  1. 先hash到具体是哪一个segment
  2. 调用segment中的put方法(这个过程需要加锁操作)
  3. put方法中判断segment中元素数量是否超过阈值,若超过则需要扩容 + rehash
  4. 找到具体是哪一个链表
  5. 遍历链表,如果找到相同key,则更新对应的value;如果没有找到,则生成新的HashEntry,加到整个segment头部,再更新count

remove操作

  1. 定位到具体的segment
  2. 定位到具体的链表
  3. 确定要删除的元素的位置后,不是简单地把待删除元素的前面的一个元素的next指向后面一个就完事了,我们之前已经说过HashEntry中的next是final的,一经赋值以后就不可修改,在定位到待删除元素的位置以后,程序就将待删除元素前面的那一些元素全部复制一遍,然后再一个一个重新接到链表上去

size方法

要获得ConcurrentHashMap的size,需要对多个segment进行统计。前面我们提到了每一个Segment中都有一个modCount变量,代表的是对Segment中元素的数量造成影响的操作的次数,这个值只增不减,size操作就是遍历了两次Segment,每次记录Segment的modCount值,然后将两次的modCount进行比较,如果相同,则表示期间没有发生过写入操作,就将原先遍历的结果返回,如果不相同,则把这个过程再重复做一次,如果再不相同,则就需要将所有的Segment都锁住,然后一个一个遍历了。

与JDK1.7和1.8中ConcurrentHashMap的变化

  • 取消了Segment分段锁的数据结构,取而代之的是数组+链表(红黑树)的结构。
  • 而对于锁的粒度,调整为对每个数组元素加锁(Node)。
  • put的实现通过cas操作插入元素
  • 然后是定位节点的hash算法被简化了,这样带来的弊端是Hash冲突会加剧。因此在链表节点数量大于8时,会将链表转化为红黑树进行存储。这样一来,查询的时间复杂度就会由原先的O(n)变为O(logN)。

© 著作权归作者所有

共有 人打赏支持
edwardGe
粉丝 9
博文 70
码字总数 106185
作品 0
杭州
高级程序员
私信 提问
HashTable、HashMap与ConCurrentHashMap源码解读

HashMap 的数据结构 hashMap 初始的数据结构如下图所示,内部维护一个数组,然后数组上维护一个单链表,有个形象的比喻就是想挂钩一样,数组脚标一样的,一个一个的节点往下挂。 我们可以看源...

金发只是水一下
07/20
0
0
ConcurrentHashMap源码跟踪记录

concurrentHashMap源码解读 主要理解几个问题1 ConcurrentHashMap如何实现分段锁2 存取数据是否读写分离 1 分段锁的实现 ①创建默认长度16的segments数组 ② put方法 1 从segments数组获取s...

xuklc
03/26
0
0
ConcurrentHashMap浅谈

1、实现原理介绍 ConcurrentHashMap采用分段锁的思想,将整个table分成不同的segment。每个Segment配有一个锁,这样每个段都能并行的做增删改查等功能。 2、ConcurrentHashMap在代码实现上有...

hyssop
2016/02/02
73
0
Java拾遗:003 - ConcurrentHashMap源码解读

JDK1.7 ConcurrentHashMap实现原理浅析 在多线程场景下使用HashMap会造成死循环,CPU100%等问题,所以我们不能在多线程场景下使用HashMap,另外一个集合类HashTable是线程安全的,但其使用这...

一别丶经年
08/03
0
0
第三章 spring-bean之DefaultListableBeanFactory(7)

前言 DefaultListableBeanFactory是beanFactory体系里面最后一个子类,也是唯一的操作类,唯一的实现。DefaultListableBeanFactory继承了AbstractAutowireCapableBeanFactory,实现了Configu...

鸟菜啊
08/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

探索802.11ax

802.11ax承诺在真实条件下改善峰值性能和最差情况。 如何改善今天的Wi-Fi? 在决定如何改进当前版本以外的Wi-Fi时,802.11ac,IEEE和Wi-Fi联盟调查了Wi-Fi部署和行为,以确定更广泛使用的障碍...

linuxprobe16
今天
2
0
使用linux将64G的SDCARD格式化为FAT32

一、命令如下: sudo fdisk -lsudo mkfs.vfat /dev/sda -Isudo fdisk /dev/sda Welcome to fdisk (util-linux 2.29.2). Changes will remain in memory only, until you decide to wri......

mbzhong
今天
4
0
深入理解Plasma(四):Plasma Cash

这一系列文章将围绕以太坊的二层扩容框架,介绍其基本运行原理,具体操作细节,安全性讨论以及未来研究方向等。本篇文章主要介绍在 Plasma 框架下的项目 Plasma Cash。 深入理解Plasma(1):...

HiBlock
昨天
1
0
命令参数的三大风格:Posix、BSD、GNU

今天读到命令行中参数的风格有三大类,即Unix/Posix、BSD、GNU。分别有以下特征: Unix/Posix风格,即命令后的参数,可以分组,便必须以连字符开头,如ps -aux。 BSD风格,即命令后的参数,可...

大别阿郎
昨天
2
0
PHP生成图片验证码

PHP生成图片验证码 /** * PHP生成图片验证码 * Class VerifyImage */class VerifyImage{ // 生成随机字串 private $verifyCode; // 图片对象 private $image; /**...

DrChenXX
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部