niceyoo博客 niceyoo博客

ConcurrentHashMap底层原理?

in Java基础 文章转载请注明来源!

本文为面试必备系列篇,不深入叙述,具体细节可自行查询。

可能会问的问题

1、用过ConcurrentHashMap吗?
2、为什么要用ConcurrentHashMap?
3、HashMap与HashTable的区别,引出ConcurrentHashMap…
4、HashMap在多线程环境下存在线程安全问题,那你一般都是怎么处理这种情况的?
5、能说一下ConcurrentHashMap是怎么实现的吗?

为什么要用ConcurrentHashMap?

在并发编程中使用HashMap可能会导致程序陷入死循环,而使用线程安全的HashTable效率又非常低,所以采用了ConcurrentHashMap。

单看这个回答,就会牵扯到「为和编发编程中使用HashMap会导致程序陷入死循环?」和「HashTable为何效率低下?」这两个问题,具体可参考上篇 > 面试必备:HashMap底层数据结构?jdk1.8算法优化,hash冲突,扩容等问题

关于ConcurrentHashMap实现原理的两个参考回答,自己可以重新组织一下:

ConcurrentHashMap采用的是分段式锁,与之对应的就是HashTable,HashTable使用的是Synchronize关键字,是对一个大的数组加一把锁,其实是对对象加锁,锁住的是对象整体,性能肯定是比较差的,现在ConcurrentHashMap是将大数组拆分成许多的小数组,每一个小数组拥有一把锁,允许多个修改操作并发进行。

ConcurrentHashMap采用的是分段式锁,可以理解为把一个大的Map拆封成N个小的Segment,在put数据时会根据hash<key>来确定具体存放在哪个Segment中,Segment内部的同步机制是基于Lock操作的,每一个Segment都会分配一把锁,当线程占用锁访问其中一段数据时,其他段的数据也能被其他线程访问,也就是实现并发访问。

继续拓展,分段式锁是如何实现的?

ConcurrentHashMap在JDK1.7和JDK1.8之间是有区别的,当然,这个问题也可以这样问:

能说一下ConcurrentHashMap在JDK1.7和JDK1.8中的区别吗?

1、JDK1.7:

HashEntry数组 + Segment数组 + Unsafe 「大量方法运用」

JDK1.7中数据结构是由一个Segment数组和多个HashEntry数组组成的,每一个Segment元素中存储的是HashEntry数组+链表,而且每个Segment均继承自可重入锁ReentrantLock,也就带有了锁的功能,当线程执行put的时候,只锁住对应的那个Segment 对象,对其他的 Segment 的 get put 互不干扰,这样子就提升了效率,做到了线程安全。

额外补充:我们对 ConcurrentHashMap 最关心的地方莫过于如何解决 HashMap 在 put 时候扩容引起的不安全问题?

在 JDK1.7 中 ConcurrentHashMap 在 put 方法中进行了两次 hash 计算去定位数据的存储位置,尽可能的减小哈希冲突的可能行,然后再根据 hash 值以 Unsafe 调用方式,直接获取相应的 Segment,最终将数据添加到容器中是由 segment对象的 put 方法来完成。由于 Segment 对象本身就是一把锁,所以在新增数据的时候,相应的 Segment对象块是被锁住的,其他线程并不能操作这个 Segment 对象,这样就保证了数据的安全性,在扩容时也是这样的,在 JDK1.7 中的 ConcurrentHashMap扩容只是针对 Segment 对象中的 HashEntry 数组进行扩容,还是因为 Segment 对象是一把锁,所以在 rehash 的过程中,其他线程无法对 segment 的 hash 表做操作,这就解决了 HashMap 中 put 数据引起的闭环问题。

2、JDK1.8:

JDK1.7:ReentrantLock+Segment+HashEntry
JDK1.8:Synchronized+CAS+Node+红黑树

JDK1.8屏蔽了JDK1.7中的Segment概念呢,而是直接使用「Node数组+链表+红黑树」的数据结构来实现,并发控制采用 「Synchronized + CAS机制」来确保安全性,为了兼容旧版本保留了Segment的定义,虽然没有任何结构上的作用。

总之JDK1.8中优化了两个部分:

放弃了 HashEntry 结构而是采用了跟 HashMap 结构非常相似的 Node 数组 + 链表(链表长度大于8时转成红黑树)的形式

Synchronize替代了ReentrantLock,我们一直固有的思想可能觉得,Synchronize是重量级锁,效率比较低,但为什么要替换掉ReentrantLock呢?

1、随着JDK版本的迭代,本着对Synchronize不放弃的态度,内置的Synchronize变的越来越“轻”了,某些场合比使用API更加灵活。

2、加锁力度的不同,在JDK1.7中加锁的力度是基于Segment的,包含多个HashEntry,而JDK1.8锁的粒度就是HashEntry(首节点),也就是1.8中加锁力度更低了,在粗粒度加锁中 ReentrantLock 可能通过 Condition 来控制各个低粒度的边界,更加的灵活,而在低粒度中,Condition的优势就没有了,所以使用内置的 Synchronize 并不比ReentrantLock效果差。

18年专科毕业后,期间一度迷茫,最近我创建了一个公众号用来记录自己的成长。

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

本文基于《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
文章链接:http://sscai.club/index.php/archives/95/ (转载时请注明本文出处及文章链接)

ConcurrentHashMap
发表新评论
前篇 后篇
雷姆
拉姆