多线程-ConcurrentHashMap(JDK1.8)

原文: https://www.cnblogs.com/lujiango/p/7580558.html

前言

HashMap非线程安全的,HashTable是线程安全的,所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table,这就意味着所有的线程都在竞争一把锁,在多线程的环境下,它是安全的,但是无疑效率低下的。

ConcurrentHashMap(JDK1.7)

在JDK1.7中,ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成的,如图:

Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁,也就是锁分离技术,而每一个Segment元素存储的是HashEntry数组+ 链表。分段是一开始就确定的,后期不能再进行扩容(即并发度不能改变),但是单个Segment里面的数组是可以扩容的。

而JDK1.8中,是bin扩容(并发度可变)。

put

对于ConcurrentHashMap的数据插入,这里要进行两次Hash去定位数据的存储位置。

从上Segment的继承体系可以看出,Segment实现了ReentrantLock,也就带有锁的功能,当执行put操作时,会进行第一次key的hash来定位Segment的位置,如果该Segment还没有初始化,即通过CAS操作进行赋值,然后进行第二次hash操作,找到相应的HashEntry的位置,这里会利用继承过来的锁的特性,在将数据插入指定的HashEntry位置时(链表的尾端),会通过继承ReentrantLock的tryLock()方法尝试去获取锁,如果获取成功就直接插入相应的位置,如果已经有线程获取该Segment的锁,那当前线程会以自旋的方式去继续的调用tryLock()方法去获取锁,超过指定次数就挂起,等待唤醒。

get

ConcurrentHashMap的get操作跟HashMap类似,只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置,然后再hash定位到指定的HashEntry,遍历该HashEntry下的链表进行对比,成功就返回,不成功就返回null。

size

计算ConcurrentHashMap的元素大小是一个有趣的问题,因为他是并发操作的,就是在你计算size的时候,他还在并发的插入数据,可能会导致你计算出来的size和你实际的size有相差(在你return size的时候,插入了多个数据),要解决这个问题,JDK1.7版本用两种方案:

  1. 第一种方案他会使用不加锁的模式去尝试多次计算ConcurrentHashMap的size,最多三次,比较前后两次计算的结果,结果一致就认为当前没有元素加入,计算的结果是准确的
  2. 第二种方案是如果第一种方案不符合,他就会给每个Segment加上锁,然后计算ConcurrentHashMap的size返回

ConcurrentHashMap(JDK1.8)

 JDK1.8的实现已经摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,并发控制使用Synchronized和CAS来操作,整个看起来就像是优化过且线程安全的HashMap,虽然在JDK1.8中还能看到Segment的数据结构,但是已经简化了属性,只是为了兼容旧版本;loadFactor仅用于构造函数中设定初始容量,已经不能影响扩容阈值,JDK1.8中阈值计算基本恒定为0.75;concurrencyLevel只影响初始容量,后续的并发度大小依赖于table数组的大小。

先看一些常量设计和数据结构:

基本属性定义了ConcurrentHashMap的一些边界以及操作时的一些控制。

类图

Node是ConcurrentHashMap存储结构的基本单元,实现了Map.Entry接口,用于存储数据。它对value和next属性设置了volatile同步锁(与JDK7的Segment相同),它不允许调用setValue方法直接改变Node的value域,它增加了find方法辅助map.get()方法。 

TreeNode继承于Node,但是数据结构换成了二叉树结构,它是红黑树的数据的存储结构,用于红黑树中存储数据,当链表的节点数大于8时会转换成红黑树的结构,他就是通过TreeNode作为存储结构代替Node来转换成黑红树。

TreeBin从字面含义中可以理解为存储树形结构的容器,而树形结构就是指TreeNode,所以TreeBin就是封装TreeNode的容器,它提供转换黑红树的一些条件和锁的控制。

ForwardingNode一个用于连接两个table的节点类。它包含一个nextTable指针,用于指向下一张表。而且这个节点的key value next指针全部为null,它的hash值为-1. 这里面定义的find的方法是从nextTable里进行查询节点,而不是以自身为头节点进行查找。

Unsafe和CAS

在ConcurrentHashMap中,随处可以看到U, 大量使用了U.compareAndSwapXXX的方法,这个方法是利用一个CAS算法实现无锁化的修改值的操作,他可以大大降低锁代理的性能消耗。这个算法的基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值是否相等,如果相等,则接受你指定的修改的值,否则拒绝你的操作。因为当前线程中的值已经不是最新的值,你的修改很可能会覆盖掉其他线程修改的结果。这一点与乐观锁,SVN的思想是比较类似的。

ConcurrentHashMap定义了三个原子操作,用于对指定位置的节点进行操作。正是这些原子操作保证了ConcurrentHashMap的线程安全。

get

通过key获取value

put

首先看一下put的源码:根据hash值计算这个新插入的点在table中的位置i,如果i位置是空的,直接放进去,否则进行判断,如果i位置是树节点,按照树的方式插入新的节点,否则把i插入到链

JDK8中的实现也是锁分离思想,只是锁住的是一个node,而不是JDK7中的Segment;锁住Node之前的操作是基于在volatile和CAS之上无锁并且线程安全的。

put操作的流程图如下:

从put可以看出有几个操作比较重要,下面我们就重点讲解这几个方法:initTable,helpTransfer,treeifyBin,addCount

initTable初始化

初始化方法主要应用了关键属性sizeCtl 如果这个值小于0,表示其他线程正在进行初始化,就放弃这个操作。在这也可以看出ConcurrentHashMap的初始化只能由一个线程完成。如果获得了初始化权限,就用CAS方法将sizeCtl置为-1,防止其他线程进入。初始化数组后,将sizeCtl的值改为0.75*n。

transfer

当ConcurrentHashMap容量不足的时候,需要对table进行扩容,它支持并发扩容,却没有锁。

扩容的场景:

(1)往hashMap中成功插入一个key/value节点时,有可能触发扩容动作:所在链表的元素个数达到了阈值 8,则会调用treeifyBin方法把链表转换成红黑树,不过在结构转换之前,会对数组长度进行判断,如果小于64,则优先扩容,而不是链表转树。

(2)新增节点之后,会调用addCount方法记录元素个数,并检查是否需要进行扩容,当数组元素个数达到阈值时,会触发transfer方法,重新调整节点的位置。

整个扩容操作分为两个部分

  •  第一部分是构建一个nextTable,它的容量是原来的两倍,这个操作是单线程完成的。这个单线程的保证是通过RESIZE_STAMP_SHIFT这个常量经过一次运算来保证的,这个地方在后面会有提到;
  • 第二个部分就是将原来table中的元素复制到nextTable中,这里允许多线程进行操作。

状态变化图:

(1)初始化有一个16大小的数组:

(2)创建一个二倍大小的nextTable,并且new ForwardingNode<K,V>(nextTab)

 (3)从后往前移动tab中元素到nextTable,比如:已经把tab[10-15]移动到nextTable中的状态图为:

treeifyBin 

在put操作中,如果发现链表结构中的元素超过8个,则会把链表转换为红黑树,便于提高查询效率。

addCount

把当前ConcurrentHashMap元素个数 + 1,主要有2个步骤:(1)更新baseCount值(2)检测是否进行扩容

size

最后,我们看看size方法

Leave a Comment

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据