文档章节

ConcurrentHashMap源码解读

edwardGe
 edwardGe
发布于 2018/08/18 15:05
字数 1583
阅读 8
收藏 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
粉丝 10
博文 71
码字总数 106188
作品 0
杭州
高级程序员
私信 提问
HashTable、HashMap与ConCurrentHashMap源码解读

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

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

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

xuklc
2018/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是线程安全的,但其使用这...

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

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

鸟菜啊
2018/08/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx日志自动切割

1.日志配置(Nginx 日志) access.log----记录哪些用户,哪些页面以及用户浏览器,IP等访问信息;error.log------记录服务器错误的日志 #配置日志存储路径:location / {      a...

em_aaron
昨天
0
0
java 反射

基本概念 RTTI,即Run-Time Type Identification,运行时类型识别。RTTI能在运行时就能够自动识别每个编译时已知的类型。   要想理解反射的原理,首先要了解什么是类型信息。Java让我们在运...

细节探索者
昨天
1
0
推荐转载连接

https://www.cnblogs.com/ysocean/p/7409779.html#_label0

小橙子的曼曼
昨天
3
0
雷军亲自打造的套餐了解下:用多少付多少

12月28日消息,小米科技创始人兼CEO雷军微博表示,小米移动任我行套餐方案,原则上就是明明白白消费,用多少付多少,不用不花钱!上网、电话和短信都是一毛钱,上网0.1元/M,电话0.1元/分钟,...

linuxCool
昨天
6
0
协议简史:如何学习网络协议?

大学时,学到网络协议的7层模型时,老师教了大家一个顺口溜:物数网传会表应。并说这是重点,年年必考,5分的题目摆在这里,你们爱背不背。 考试的时候,果然遇到这个问题,搜索枯肠,只能想...

Java干货分享
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部