您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

剖析ConcurrentHashMap

1.7以前

一个ConcurrentHashMap里包含一个Segment数组,每个Segment里包含一个HashEntry数组,我们称之为table,每个HashEntry是一个链表结构的元素,每个key和value最后会计算出一个hash值,hash值如果相同的key,value会封装成一个对象,然后放入到HashEntity的相同链表中,不同则放在其他链表中,其实总结就是,Segment数组就是一个加锁的数组,每个线程对应一个Segment,每个Segment中包含一个hashmap。

注意:ConcurrentHashMap采用了二次hash的方式,第一次hash将key映射到对应的segment,而第二次hash则是映射到segment的不同桶(bucket)中。

保证线程安全性的原因:
ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术,对segment进行加锁,segment本身也是一个锁(继承了ReentrantLock),就保证了线程安全,初始化是根据并发数的大小和数组的大小来确定segment的大小,同时为了快速定位,通过算法保证segment的大小为2的指数,初始化的时候只初始化segment的第一个元素。

concurrencyLevel并发度:
默认16。并发度可以理解为程序运行时能够同时更新ConccurentHashMap且不产生锁竞争的最大线程数,实际上就是ConcurrentHashMap中的分段锁个数,即Segment[]的数组长度。如果并发度设置的过小,会带来严重的锁竞争问题;如果并发度设置的过大,原本位于同一个Segment内的访问会扩散到不同的Segment中,CPU cache命中率会下降,从而引起程序性能下降。

扩容:
concurrencyLevel(并发度)一经指定,不可改变,后续如果ConcurrentHashMap的元素数量增加导致ConrruentHashMap需要扩容,ConcurrentHashMap不会增加Segment的数量,而只会增加Segment中链表数组的容量大小,这样的好处是扩容过程不需要对整个ConcurrentHashMap做rehash,而只需要对Segment里面的元素做一次rehash就可以了。table中的元素位置变化,是根据扩容多大,比如扩大n,则元素下标不变化的就位置把持不变,变化的就在原来下标的基础上+n即可,可以快速定位和减少重排次数。
这边需要特别注意一下两个变量,分别是segmentShift和segmentMask,这两个变量在后面将会起到很大的作用,假设构造函数确定了Segment的数量是2的n次方,那么segmentShift就等于32减去n,而segmentMask就等于2的n次方减一。

get:
1,定位segment:先通过获取key的hashCode方法获取到哈希值,然后再通过WangJenkins哈希算法再进行散列,通过偏移量获取到一个高位哈希串再取模,然后寻找到具体所在的segment位置。
2,定位table:先通过获取key的hashCode方法获取到哈希值,然后再通过WangJenkins哈希算法再进行散列,再和table的长度进行取模,然后寻找到具体所在的table位置。
3,再在table中寻找对应的链表,去循环链表中的元素。
在高并发下的情况下如何保证取得的元素是最新的?
答:用于存储键值对数据的HashEntry,在设计上它的成员变量value等都是volatile类型的,这样就保证别的线程对value值的修改,get方法可以马上看到。

put:
1、首先定位segment,当这个segment在map初始化后,还为null,由ensureSegment方法负责填充这个segment。
2、对Segment加锁。
3、定位所在的table元素,hash(key)得到hash值,并扫描table下的链表,如果有相同的hash值,再判断key是否相同,如果相同就覆盖,不同就将这个值挂在链表尾部。

size:首次会进行两次不加锁的统计,如果一致就返回,不一致就加锁之后再统计。因为可能会存在把segment所有的都加锁,所以尽量避免使用size方法。

弱一致性:
get方法和containsKey方法没有加锁,他们都是通过对链表遍历判断是否存在key相同的节点以及获得该节点的value。但由于遍历过程中其他线程可能对链表结构做了调整,因此get和containsKey返回的可能是过时的数据,这一点是ConcurrentHashMap在弱一致性上的体现。

1.8以后

与1.7相比的重大变化:
1、 取消了segment数组,直接用table保存数据,锁的粒度更小,减少并发冲突的概率。
2、 存储数据时采用了链表+红黑树的形式,纯链表的形式时间复杂度为O(n),红黑树则为O(log2n),性能提升很大。什么时候链表转红黑树?当key值相等的元素形成的链表中元素个数超过8个并且容量大于64的时候,如果容量小于64就先扩容。

主要数据结构和关键变量:
	Node类存放实际的key和value值。
	sizeCtl:
		负数:表示进行初始化或者扩容,-1表示正在初始化,-N表示有N-1个线程正在进行扩容
		正数:0 表示还没有被初始化,>0的数,初始化或者是下一次进行扩容的阈值
	TreeNode用在红黑树,表示树的节点, TreeBin是实际放在table数组中的,代表了这个红黑树的根,将TreeNode进行了封装。

初始化过程:
在put的时候,会调用initTable方法,
if ((sc = sizeCtl) < 0)
Thread.yield();
会判断当sizeCtl小于0的时候,表示有其他线程正在初始化,当前线程就会进行yield,让出cpu的执行权。否则:
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) ,会用一个CAS操作设置sizeCtl的值,并初始化Node数组,然后:
sc = n - (n >>> 2); sc =0.75n。将sizeCtl设置为0.75n的阈值。

扩容操作:
transfer()方法进行实际的扩容操作,table大小也是翻倍的形式,有一个并发扩容的机制。同时检测到某个table链表元素小于6个了的红黑树,就会自动把红黑树又转为链表结构。
同时,在put的时候,判断如果有线程正在进行扩容,当前线程会帮助扩容,tab=helpTransfer(tab,f);,这个其实是put和hashmap最大不同之处,可以并发扩容,帮助移动数组中的Node的位置。

链表转为红黑树:
	if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
    其中,if (binCount >= TREEIFY_THRESHOLD)表示当链表长度大于8的时候,通过treeifyBin(tab, i);转为红黑树。

put操作:
1,根据key进行两次hash算法得到hash值。
2,判断Node数组是否为空,如果为空进行初始化。
3,根据hash值得出所在的数组的位置,并判断当前数组里有没有链表存在,没有就通过CAS操作将元素加入到当前位置中。
4,else if ((fh = f.hash) == MOVED),判断是否有线程正在进行扩容,当前线程会帮助扩容,tab = helpTransfer(tab, f);,这个其实是put和hashmap最大不同之处。
5,如果当前数组位置已经存在元素了,就先用synchronized加锁,然后再判断当前位置是链表,还是红黑树,再对比hash值和equl s,hash值相同的,如果key相同就覆盖,key不相同就挂在当前链表后面,hash值不同,就挂在新节点上。

get操作:
1,首先判断当前node数组的位置的元素是否就是当前key,并且就是一个元素,没有链表,如果是就直接返回。
2,如果不是,再判断是否是红黑树,是就去红黑树中查找。
3,如果不是,就去链表中查找。
4,如果当前table为空,还没初始化,就直接返回null。

size方法:
估计的大概数量,不是精确数量,因为没有加锁,所以是弱一致性的。

putIfAbsent():
如果没有对应好的key就放入map,有这个值则返回key原来对应的值。

转载来源 https://blog.csdn.net/qq_28822933/article/details/83181939


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进