IT源码网

ConcurrentHashMap 线程安全讲解

itxm 2021年04月02日 编程语言 204 0

简介

众所周知,在 Java 中,HashMap 是非线程安全的,如果想在多线程下安全的操作 map,主要有以下解决方法:

  1. 使用 Hashtable 线程安全类
  2. 使用 Collections.synchronizedMap方法,对方法进行加同步锁
  3. 使用并发包中的ConcurrentHashMap

关于 Hashtable 类,Hashtable 是一个线程安全的类,Hashtable 几乎所有的添加、删除、查询方法都加了synchronized同步锁

相当于给整个哈希表加了一把大锁,多线程访问时候,只要有一个线程访问或操作该对象,那其他线程只能阻塞等待需要的锁被释放,在竞争激烈的多线程场景中性能就会非常差,所以 Hashtable 不推荐使用!

在这里插入图片描述
再来看看第二种方法,使用Collections.synchronizedMap方法,我们打开 JDK 源码,部分内容如下:

在这里插入图片描述
可以很清晰的看到,如果传入的是 HashMap 对象,其实也是对 HashMap 做的方法做了一层包装,里面使用对象锁来保证多线程场景下,操作安全,本质也是对 HashMap 进行全表锁!

使用Collections.synchronizedMap方法,在竞争激烈的多线程环境下性能依然也非常差,所以不推荐使用!

上面 2 种方法,由于都是对方法进行全表锁,所以在多线程环境下容易造成性能差的问题,因为hashMap 是数组 + 链表的数据结构,如果我们把数组进行分割多段,对每一段分别设计一把同步锁,这样在多线程访问不同段的数据时,就不会存在锁竞争了,这样是不是可以有效的提高性能

再来看看第三种方法,使用并发包中的ConcurrentHashMap类!

ConcurrentHashMap 类所采用的正是分段锁的思想,将 HashMap 进行切割,把 HashMap 中的哈希数组切分成小数组,每个小数组有 n 个 HashEntry 组成,其中小数组继承自ReentrantLock(可重入锁),这个小数组名叫Segment, 如下图:
在这里插入图片描述
当然,JDK1.7 和 JDK1.8 对 ConcurrentHashMap 的实现有很大的不同!

JDK1.8 对 HashMap 做了改造,当冲突链表长度大于 8 时,会将链表转变成红黑树结构,上图是 ConcurrentHashMap 的整体结构,参考 JDK1.7!

我们再来看看 JDK1.8 中 ConcurrentHashMap 的整体结构,内容如下:

在这里插入图片描述

JDK1.8 中 ConcurrentHashMap 类取消了 Segment 分段锁,采用 CAS + synchronized 来保证并发安全,数据结构跟 jdk1.8 中 HashMap 结构类似,都是数组 + 链表(当链表长度大于 8 时,链表结构转为红黑二叉树)结构。

ConcurrentHashMap 中 synchronized 只锁定当前链表或红黑二叉树的首节点,只要节点 hash 不冲突,就不会产生并发,相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍!

JDK1.7 中的 ConcurrentHashMap

JDK 1.7 的 ConcurrentHashMap 采用了非常精妙的分段锁策略,打开源码,可以看到 ConcurrentHashMap 的主存是一个 Segment 数组。

在这里插入图片描述
我们再来看看 Segment 这个类,在 ConcurrentHashMap 中它是一个静态内部类,内部结构跟 HashMap 差不多,源码如下:

在这里插入图片描述

存放元素的 HashEntry,也是一个静态内部类,源码如下:

在这里插入图片描述

HashEntry和HashMap中的 Entry非常类似,唯一的区别就是其中的核心数据如value ,以及next都使用了volatile关键字修饰,保证了多线程环境下数据获取时的可见性!

从类的定义上可以看到,Segment 这个静态内部类继承了ReentrantLock类,ReentrantLock是一个可重入锁。

ReentrantLock和synchronized都可以实现对线程进行加锁,不同点是:ReentrantLock可以指定锁是公平锁还是非公平锁,操作上也更加灵活。

ConcurrentHashMap 在存储方面是一个 Segment 数组,一个 Segment 就是一个子哈希表,Segment 里维护了一个 HashEntry 数组,其中 Segment 继承自 ReentrantLock,并发环境下,对于不同的 Segment 数据进行操作是不用考虑锁竞争的,因此不会像 Hashtable 那样不管是添加、删除、查询操作都需要同步处理。

理论上 ConcurrentHashMap 支持 concurrentLevel(通过 Segment 数组长度计算得来) 个线程并发操作,每当一个线程独占一把锁访问 Segment 时,不会影响到其他的 Segment 操作,效率大大提升!

上面介绍完了对象属性,我们继续来看看 ConcurrentHashMap 的构造方法,源码如下:

在这里插入图片描述
this调用对应的构造方法,源码如下:
在这里插入图片描述

从源码上可以看出,ConcurrentHashMap 初始化方法有三个参数,initialCapacity(初始化容量)为 16、loadFactor(负载因子)为 0.75、concurrentLevel(并发等级)为 16,如果不指定则会使用默认值。

其中,值得注意的是 concurrentLevel 这个参数,虽然 Segment 数组大小 ssize 是由 concurrentLevel 来决定的,但是却不一定等于 concurrentLevel,ssize 通过位移动运算,一定是大于或者等于 concurrentLevel 的最小的 2 的次幂!

通过计算可以看出,按默认的 initialCapacity 初始容量为 16,concurrentLevel 并发等级为 16,理论上就允许 16 个线程并发执行,并且每一个线程独占一把锁访问 Segment,不影响其它的 Segment 操作!

ConcurrentHashMap 的 put 方法,源码如下:

在这里插入图片描述

从源码可以看出,这部分的 put 操作主要分两步:

定位 Segment 并确保定位的 Segment 已初始化;
调用 Segment 的 put 方法;
真正插入元素的 put 方法,源码如下:

在这里插入图片描述

从源码可以看出,真正的 put 操作主要分以下几步:

  1. 尝试获取对象锁,如果获取到返回 true,否则执行scanAndLockForPut方法,这个方法也是尝试获取对象锁;
  2. 获取到锁之后,类似 hashMap 的 put 方法,通过 key 计算所在 HashEntry 数组的下标;
  3. 获取到数组下标之后遍历链表内容,通过 key 和 hash 值判断是否 key 已存在,如果已经存在,通过标识符判断是否覆盖,默认覆盖;
  4. 如果不存在,采用头插法插入到 HashEntry 对象中;
  5. 最后操作完整之后,释放对象锁;

我们再来看看,上面提到的scanAndLockForPut这个方法,源码如下:
在这里插入图片描述

scanAndLockForPut这个方法,操作也是分以下几步:

  1. 当前线程尝试去获得锁,查找 key 是否已经存在,如果不存在,就创建一个 HashEntry 对象;
  2. 如果重试次数大于最大次数,就调用lock()方法获取对象锁,如果依然没有获取到,当前线程就阻塞,直到获取之后退出循环;
  3. 在这个过程中,key 可能被别的线程给插入,所以在第 5 步中,如果 HashEntry 存储内容发生变化,重置重试次数;

通过scanAndLockForPut()方法,当前线程就可以在即使获取不到segment锁的情况下,完成需要添加节点的实例化工作,当获取锁后,就可以直接将该节点插入链表即可。

这个方法还实现了类似于自旋锁的功能,循环式的判断对象锁是否能够被成功获取,直到获取到锁才会退出循环,防止执行 put 操作的线程频繁阻塞,这些优化都提升了 put 操作的性能。

get 操作

get 方法就比较简单了,因为不涉及增、删、改操作,所以不存在并发故障问题,源码如下:
在这里插入图片描述

由于 HashEntry 涉及到的共享变量都使用 volatile 修饰,volatile 可以保证内存可见性,所以不会读取到过期数据。

remove 操作

remove 操作和 put 方法差不多,都需要获取对象锁才能操作,通过 key 找到元素所在的 Segment 对象然后移除,源码如下:
在这里插入图片描述

与 get 方法类似,先获取 Segment 数组所在的 Segment 对象,然后通过 Segment 对象去移除元素,源码如下:
在这里插入图片描述

先获取对象锁,如果获取到之后执行移除操作,之后的操作类似 hashMap 的移除方法,步骤如下:

  1. 先获取对象锁;
  2. 计算 key 的 hash 值在 HashEntry[]中的角标;
  3. 根据 index 角标获取 HashEntry 对象;
  4. 循环遍历 HashEntry 对象,HashEntry 为单向链表结构;
  5. 通过 key 和 hash 判断 key 是否存在,如果存在,就移除元素,并将需要移除的元素节点的下一个,向上移;
  6. 最后就是释放对象锁,以便其他线程使用;

JDK1.8 中的 ConcurrentHashMap

虽然 JDK1.7 中的 ConcurrentHashMap 解决了 HashMap 并发的安全性,但是当冲突的链表过长时,在查询遍历的时候依然很慢!

在 JDK1.8 中,HashMap 引入了红黑二叉树设计,当冲突的链表长度大于 8 时,会将链表转化成红黑二叉树结构,红黑二叉树又被称为平衡二叉树,在查询效率方面,又大大的提高了不少。

在这里插入图片描述
因为 HashMap 并不支持在多线程环境下使用, JDK1.8 中的 ConcurrentHashMap 和往期 JDK 中的 ConcurrentHashMap 一样支持并发操作,整体结构和 JDK1.8 中的 HashMap 类似,相比 JDK1.7 中的 ConcurrentHashMap, 它抛弃了原有的 Segment 分段锁实现,采用了 CAS + synchronized 来保证并发的安全性。

JDK1.8 中的 ConcurrentHashMap 对节点Node类中的共享变量,和 JDK1.7 一样,使用volatile关键字,保证多线程操作时,变量的可见行!
在这里插入图片描述

put 操作

打开 JDK1.8 中的 ConcurrentHashMap 中的 put 方法,源码如下:
在这里插入图片描述

当进行 put 操作时,流程大概可以分如下几个步骤:

  1. 首先会判断 key、value 是否为空,如果为空就抛异常!
  2. 接着会判断容器数组是否为空,如果为空就初始化数组;
  3. 进一步判断,要插入的元素f,在当前数组下标是否第一次插入,如果是就通过 CAS 方式插入;
  4. 在接着判断f.hash == -1是否成立,如果成立,说明当前f是ForwardingNode节点,表示有其它线程正在扩容,则一起进行扩容操作;
  5. 其他的情况,就是把新的Node节点按链表或红黑树的方式插入到合适的位置;
  6. 节点插入完成之后,接着判断链表长度是否超过8,如果超过8个,就将链表转化为红黑树结构;
  7. 最后,插入完成之后,进行扩容判断;

put 操作大致的流程,就是这样的,可以看的出,复杂程度比 JDK1.7 上了一个台阶。

initTable 初始化数组

再来看看源码中的第 3 步 initTable()方法,如果数组为空就初始化数组,源码如下:
在这里插入图片描述

sizeCtl 是一个对象属性,使用了 volatile 关键字修饰保证并发的可见性,默认为 0,当第一次执行 put 操作时,通过Unsafe.compareAndSwapInt()方法,俗称CAS,将 sizeCtl修改为 -1,有且只有一个线程能够修改成功,接着执行 table 初始化任务。

如果别的线程发现sizeCtl<0,意味着有另外的线程执行 CAS 操作成功,当前线程通过执行Thread.yield()让出 CPU 时间片等待 table 初始化完成。

helpTransfer 帮组扩容

put 方法中第 5 步helpTransfer()方法,如果f.hash == -1成立,说明当前f是ForwardingNode节点,意味有其它线程正在扩容,则一起进行扩容操作,源码如下:
在这里插入图片描述

这个过程,操作步骤如下:

  1. 对 table、node 节点、node 节点的 nextTable,进行数据校验;
  2. 根据数组的 length 得到一个标识符号;
  3. 进一步校验 nextTab、tab、sizeCtl 值,如果 nextTab 没有被并发修改并且 tab 也没有被并发修改,同时 sizeCtl < 0,说明还在扩容;
  4. 对 sizeCtl 参数值进行分析判断,如果不满足任何一个判断,将sizeCtl + 1, 增加了一个线程帮助其扩容;

addCount 扩容判断

再来看看源码中的第 9 步 addCount()方法,插入完成之后,扩容判断,源码如下:
在这里插入图片描述

这个过程,操作步骤如下:

  1. 利用 CAS 将方法更新 baseCount 的值
  2. 检查是否需要扩容,默认 check = 1,需要检查;
  3. 如果满足扩容条件,判断当前是否正在扩容,如果是正在扩容就一起扩容;
  4. 如果不在扩容,将 sizeCtl 更新为负数,并进行扩容处理;

put 的流程基本分析完了,可以从中发现,里面大量的使用了CAS方法,CAS 表示比较与替换,里面有 3 个参数,分别是目标内存地址、旧值、新值,每次判断的时候,会将旧值与目标内存地址中的值进行比较,如果相等,就将新值更新到内存地址里,如果不相等,就继续循环,直到操作成功为止!

get 操作

get 方法操作就比较简单了,因为不涉及并发操作,直接查询就可以了,源码如下:
在这里插入图片描述

从源码中可以看出,步骤如下:

  1. 判断数组是否为空,通过 key 定位到数组下标是否为空;
  2. 判断 node 节点第一个元素是不是要找到,如果是直接返回;
  3. 如果是红黑树结构,就从红黑树里面查询;
  4. 如果是链表结构,循环遍历判断;

reomve 操作

reomve 方法操作和 put 类似,只是方向是反的,源码如下:
在这里插入图片描述

replaceNode 方法,源码如下:
在这里插入图片描述

从源码中可以看出,步骤如下:

  1. 循环遍历数组,接着校验参数;
  2. 判断是否有别的线程正在扩容,如果是一起扩容;
  3. 用 synchronized 同步锁,保证并发时元素移除安全;
  4. 因为 check= -1,所以不会进行扩容操作,利用 CAS 操作修改 baseCount 值;

总结

虽然 HashMap 在多线程环境下操作不安全,但是在 java.util.concurrent 包下,java 为我们提供了 ConcurrentHashMap 类,保证在多线程下 HashMap 操作安全!

在 JDK1.7 中,ConcurrentHashMap 采用了分段锁策略,将一个 HashMap 切割成 Segment 数组,其中 Segment 可以看成一个 HashMap, 不同点是 Segment 继承自 ReentrantLock,在操作的时候给 Segment 赋予了一个对象锁,从而保证多线程环境下并发操作安全。

但是 JDK1.7 中,HashMap 容易因为冲突链表过长,造成查询效率低,所以在 JDK1.8 中,HashMap 引入了红黑树特性,当冲突链表长度大于 8 时,会将链表转化成红黑二叉树结构。

在 JDK1.8 中,与此对应的 ConcurrentHashMap 也是采用了与 HashMap 类似的存储结构,但是 JDK1.8 中 ConcurrentHashMap 并没有采用分段锁的策略,而是在元素的节点上采用 CAS + synchronized 操作来保证并发的安全性,源码的实现比 JDK1.7 要复杂的多。

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

常用 vm 参数分析讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。