大厂面试:谈谈你对ConcurrentHashMap的理解?

HashMap在多线程情况下,通过put方法进行插入操作时,如果元素超过了容量(由负载因子决定)的范围就会触发扩容操作,重新将原数组的内容重新hash到新的扩容数组中。在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。

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

其实HashTable有很多的优化空间,锁住整个table这么粗暴的方法可以变得柔和点,比如在多线程的环境下,对不同的数据集进行操作时其实根本就不需要去竞争一个锁,因为他们不同hash值,不会因为rehash造成线程不安全,所以互不影响,这就是锁分离技术,将锁的粒度降低,利用多个锁来控制多个小的table。

一、JDK1.7实现

1.数据结构

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

Segment数组的意义就是将一个大的数组分割成多个小的数组来进行加锁,即锁分离技术,而每一个Segment元素存储的是HashEntry数组+链表,相当于一个HashMap的数据结构。Segment包含一个HashEntry数组,数组中的每一个HashEntry既是一个键值对,也是一个链表的头节点。单一的Segment如下:

像这样的Segment对象,在ConcurrentHashMap集合中有多少个呢?有2的N次方个,共同保存在一个名为segments的数组(这个数组是不会扩容的)当中。因此整个ConcurrentHashMap的结构如下:

ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度,让并发操作效率更高。

HashEntry大小的计算也是2的N次方(cap <<=1),cap的初始值为1,所以HashEntry最小的容量为2。

另外核心数据value,以及链表都是volatile修饰的,保证了获取时的可见性。

ConcurrentHashMap 采用了分段锁技术,其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理,理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时,不会影响到其他的Segment。

2.put操作

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

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

3.get操作

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

由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的,保证了内存可见性,所以每次获取时都是最新值。

ConcurrentHashMap 的 get 方法是非常高效的,因为整个过程都不需要加锁

4.size操作

计算ConcurrentHashMap的元素大小是一个有趣的问题,因为他是并发操作的,就是在你计算size的时候,他还在并发的插入数据,可能会导致你计算出来的size和你实际的size有相差(在你return size的时候,插入了多个数据),要解决这个问题,JDK1.7版本用两种方案:第一种方案他会使用不加锁的模式去尝试多次计算ConcurrentHashMap的size,最多三次,比较前后两次计算的结果,结果一致就认为当前没有元素加入,计算的结果是准确的;如果第一种方案不符合,他就会给每个Segment加上锁,然后计算ConcurrentHashMap的size返回。

二、JDK1.8实现

1.数据结构

JDK1.8的实现已经摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,并发控制使用Synchronized和CAS来操作,整个看起来就像是优化过且线程安全的HashMap,虽然在JDK1.8中还能看到Segment的数据结构,但是已经简化了属性,只是为了兼容旧版本。

另外,将 1.7 中存放数据的 HashEntry 改为 Node,但作用都是相同的。其中的 val next 都用了 volatile 修饰,保证了可见性。

2.Put()方法

这个put的过程很清晰,对当前的table进行无条件自循环直到put成功,可以分成以下六步流程来概述:

  • 如果没有初始化就先调用initTable()方法来进行初始化过程
  • 如果没有hash冲突就直接调用Unsafe的方法CAS插入该元素
  • 如果还在进行扩容操作就先进行扩容
  • 如果存在hash冲突,就加锁来保证线程安全,这里有两种情况,一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入,
  • 最后一个如果该链表的数量大于阈值8,就要先转换成黑红树的结构,break再一次进入循环
  • 如果添加成功就调用addCount()方法统计size,并且检查是否需要扩容

3.get()方法

ConcurrentHashMap的get操作的流程很简单,也很清晰,可以分为三个步骤来描述:

  • 计算hash值,定位到该table索引位置,如果是首节点符合就返回
  • 如果遇到扩容的时候,会调用标志正在扩容节点ForwardingNode的find方法,查找该节点,匹配就返回
  • 以上都不符合的话,就往下遍历节点,匹配就返回,否则最后就返回null
全部评论
感谢参与【创作者计划2期·技术干货场】!欢迎更多牛油来写干货,瓜分总计20000元奖励!!技术干货场活动链接:https://www.nowcoder.com/link/czz2jsghtlq(参与奖马克杯将于每周五结算,敬请期待~)
点赞 回复
分享
发布于 2021-03-08 16:17
求更新
点赞 回复
分享
发布于 2021-03-09 22:03
微众银行
校招火热招聘中
官网直投
求问你们这些画图工具用的是啥
点赞 回复
分享
发布于 2021-03-19 13:43

相关推荐

2 38 评论
分享
牛客网
牛客企业服务