文档章节

ConcurrentHashMap源码解读

edwardGe
 edwardGe
发布于 08/18 15:05
字数 1583
阅读 5
收藏 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
博文 68
码字总数 105179
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

中秋快乐!!!

HiBlock
19分钟前
0
0
Node安装教程

1、安装最新版的node 2、设置相关目录(以D盘为例) 分别建立目录:D:\node,D:\node\node-globa,D:\node\node-cache 命令行输入: // 设置npm国内镜像 npm config set registry https://re...

Mohan710
47分钟前
1
0
中国发布域名系统基础软件 “红枫”

9月12日消息,域名工程中心(英文缩写 ZDNS)发布了宣称自主开发的域名系统基础软件 “红枫(Maple DNS)”。 9月12日消息,域名工程中心(英文缩写 ZDNS)发布了宣称自主开发的域名系统基础软...

问题终结者
今天
3
0
Shell编程(分发系统介绍、expect远程登录、expect远程执行命令、expect传递参数)

分发系统介绍expect 分发系统expect即分发脚本,是一种脚本语言;通过他可以实现传输,输入命令(上线代码) 应用场景:业务越来越大,网站app,后端,编程语言是php,所以就需要配置lamp或者...

蛋黄_Yolks
今天
2
0
Java Http请求工具类

public static String httpPost(String source, String params) {URL url = null;HttpURLConnection conn = null;OutputStream os = null;String ret = null;try {......

yuewawa
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部