专栏首页niceyooConcurrentHashMap底层原理?
原创

ConcurrentHashMap底层原理?

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

可能会问的问题

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效果差。

本文首发于博客园:https://www.cnblogs.com/niceyoo

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • uniapp增加百度统计代码(h5)

    请复制如下代码到上方新建的 html 中,修改自己的百度统计代码,不清楚如何获取统计代码的可以参考 步骤4

    niceyoo
  • 毕业两年的大专生程序员工作总结(java后端)

    如题,这是我毕业第二年的工作总结,对第一年工作总结感兴趣的请戳这《毕业一年的大专生程序员工作总结》,再简单介绍一下我以及这个系列的文章。

    niceyoo
  • 如何理解Java中的自动拆箱和自动装箱?

    回到家后小伟赶紧查资料,我透,这不就是问基本类型跟封装类型吗,面试官整啥名词呢...

    niceyoo
  • Java集合--ConcurrentHashMap原理

    贾博岩
  • 大数据架构和模式(三)——理解大数据解决方案的架构层

    作者:Divakar Mysore等 来源:DeveloperWorks 摘要:大数据解决方案的逻辑层可以帮助定义和分类各个必要的组件,大数据解决方案需要使用...

    机器学习AI算法工程
  • 老曹眼中的面向数据架构

    数据是系统的核心,在面向服务的架构之外,也可以考虑一下面向数据的架构方式。面向数据的服务架构需要支持多数据源异构,支持动态数据和静态数据,既支持公有云部署又支持...

    半吊子全栈工匠
  • “达观杯”NLP 竞赛,再启航

    人工智能在2018年继续强势发展,在运算智能和感知智能取得了很大的突破和优于人类的表现。

    昱良
  • 张涵诚:贵阳模式值得参考,政府发展大数据需要方法论

    大数据是提升政府管理能力的有效技术路径,驱动智慧政府转型的关键力量,这已是各地政府的广泛共识,但能真正将大数据应用落地到政府日常工作管理中的目前为数不多 作者 ...

    数据猿
  • 汇总|医学图像数据集

    http://academictorrents.com/details/80ecfefcabede760cdbdf63e38986501f7becd49

    3D视觉工坊
  • 数据又多又散,“孤岛困境”怎样破局?

    导读:企业数据指的是企业内部员工及其合作伙伴跨越不同部门、不同地点而共享,跨越不同大洲而传播的数据。这些数据对企业具有很高的价值,包括财务数据、业务数据、员工个...

    华章科技

扫码关注云+社区

领取腾讯云代金券