ConcurrentHashMap的实现原理(JDK1.7和JDK1.8)
yuyutoo 2025-03-26 18:54 4 浏览 0 评论
前言
今天就来介绍一下ConcurrentHashMap的实现原理(JDK1.7和JDK1.8)
哈希表
介绍
哈希表就是一种以键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即 key,即可查找到其对应的值。
哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。
链式哈希表
链式哈希表从根本上说是由一组链表构成。每个链表都可以看做是一个“桶”,我们将所有的元素通过散列的方式放到具体的不同的桶中。插入元素时,首先将其键传入一个哈希函数(该过程称为哈希键),函数通过散列的方式告知元素属 于哪个“桶”,然后在相应的链表头插入元素。查找或删除元素时,用同们的方式先找到元素的“桶”,然后遍历相应的链表,直到发现我们想要的元素。因为每个“桶”都是一个链表,所以链式哈希表并不限制包含元素的个数。然而,如果表变得太大,它的性能将会降低。
应用场景
我们熟知的缓存技术(比如 redis、memcached)的核心其实就是在内存中维护一张巨大的哈希表,还有大家熟知的 HashMap、CurrentHashMap 等的应用。
ConcurrentHashMap 与 HashMap 等的区别
HashMap
我们知道 HashMap 是线程不安全的,在多线程环境下,使用 Hashmap 进行 put 操作会引起死循环,导致 CPU 利用率接近 100%,所以在并发情况下不能使用 HashMap。
HashTable
HashTable 和 HashMap 的实现原理几乎一样,差别无非是
- HashTable 不允许 key 和 value 为 null
- HashTable 是线程安全的
但是 HashTable 线程安全的策略实现代价却太大了,简单粗暴,get/put 所有相关操作都是 synchronized 的,这相当于给整个哈希表加了一把大锁。
多线程访问时候,只要有一个线程访问或操作该对象,那其他线程只能阻塞,相当于将所有的操作串行化,在竞争激烈的并发场景中性能就会非常差。
ConcurrentHashMap
主要就是为了应对 hashmap 在并发环境下不安全而诞生的, ConcurrentHashMap 的设计与实现非常精巧,大量的利用了 volatile,final, CAS 等 lock-free 技术来减少锁竞争对于性能的影响。
我们都知道 Map 一般都是数组+链表结构(JDK1.8 改为数组+红黑树)。
ConcurrentHashMap 避免了对全局加锁改成了局部加锁操作,这样就极大地提高了并发环境下的操作速度,由于 ConcurrentHashMap 在 JDK1.7 和 1.8 中的实现非常不同,接下来我们谈谈 JDK 在 1.7 和 1.8 中的区别。
JDK1.7 版本的 CurrentHashMap 的实现原理
在 JDK1.7 中 ConcurrentHashMap 采用了数组+Segment+分段锁的方式实现。
1.Segment(分段锁)
ConcurrentHashMap 中的分段锁称为 Segment,它即类似于 HashMap 的结构,即内部拥有一个 Entry 数组,数组中的每个元素又是一个链表,同时又是一个 ReentrantLock(Segment 继承了 ReentrantLock)。
2.内部结构
ConcurrentHashMap 使用分段锁技术,将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问,能够实现真正的并发访问。如下图是 ConcurrentHashMap 的内部结构图:
从上面的结构我们可以了解到,ConcurrentHashMap 定位一个元素的过程需要进行两次 Hash 操作。
第一次 Hash 定位到 Segment,第二次 Hash 定位到元素所在的链表的头部。
3.该结构的优劣势
坏处:
这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长
好处:
写操作的时候可以只对元素所在的 Segment 进行加锁即可,不会影响到其他的 Segment,这样,在最理想的情况下,ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作(刚好这些写操作都非常平均地分布在所有的 Segment 上)。
所以,通过这一种结构,ConcurrentHashMap 的并发能力可以大大的提高。
JDK1.8 版本的 CurrentHashMap 的实现原理
JDK8 中 ConcurrentHashMap 参考了 JDK8 HashMap 的实现,采用了数组+链表+红黑树的实现方式来设计,内部大量采用 CAS 操作,这里我简要介绍下 CAS。
CAS 是 compare and swap 的缩写,即我们所说的比较交换。cas 是一种基于锁的操作,而且是乐观锁。在 java 中锁分为乐观锁和悲观锁。悲观锁是将资源锁住,等一个之前获得锁的线程释放锁之后,下一个线程才可以访问。而乐观锁采取了一种宽泛的态度,通过某种方式不加锁来处理资源,比如通过给记录加 version 来获取数据,性能较悲观锁有很大的提高。
CAS 操作包含三个操作数——内存位置(V)、预期原值(A)和新值(B)。 如果内存地址里面的值和 A 的值是一样的,那么就将内存里面的值更新成 B。CAS 是通过无限循环来获取数据的,若果在第一轮循环中,a 线程获取地址里面的值被 b 线程修改了,那么 a 线程需要自旋,到下次循环才有可能机会执行。
JDK8 中彻底放弃了 Segment 转而采用的是 Node,其设计思想也不再是 JDK1.7 中的分段锁思想。
Node:保存 key,value 及 key 的 hash 值的数据结构。其中 value 和 next 都用 volatile 修饰,保证并发的可见性。
Java8 ConcurrentHashMap 结构基本上和 Java8 的 HashMap 一样,不过保证线程安全性。
在 JDK8 中 ConcurrentHashMap 的结构,由于引入了红黑树,使得ConcurrentHashMap 的实现非常复杂,我们都知道,红黑树是一种性能非常 好的二叉查找树,其查找性能为 O(logN),但是其实现过程也非常复杂,而且可读性也非常差,Doug Lea 的思维能力确实不是一般人能比的,早期完全采用链表结构时 Map 的查找时间复杂度为 O(N),JDK8 中 ConcurrentHashMap在链表的长度大于某个阈值的时候会将链表转换成红黑树进一步提高其查找性能。
总结
其实可以看出 JDK1.8 版本的 ConcurrentHashMap 的数据结构已经接近 HashMap,相对而言,ConcurrentHashMap 只是增加了同步的操作来控制并发,从 JDK1.7 版本的 ReentrantLock+Segment+HashEntry,到 JDK1.8 版本中 synchronized+CAS+HashEntry+红黑树。
- 数据结构:取消了 Segment 分段锁的数据结构,取而代之的是数组+链表+红黑树的结构。
- 保证线程安全机制:JDK1.7 采用 segment 的分段锁机制实现线程安全,其中 segment 继承自 ReentrantLock。JDK1.8 采用 CAS+Synchronized 保证线程 安全。
- 锁的粒度:原来是对需要进行数据操作的 Segment 加锁,现调整为对每个数组元素加锁(Node)。
- 链表转化为红黑树:定位结点的 hash 算法简化会带来弊端,Hash 冲突加剧,因此在链表节点数量大于 8 时,会将链表转化为红黑树进行存储。
- 查询时间复杂度:从原来的遍历链表 O(n),变成遍历红黑树O(logN)。
感谢诸君的观看,文中如有纰漏,欢迎在评论区来交流。如果这篇文章帮助到了你,欢迎点赞关注。
相关推荐
- 苹果要求全新App开发四月起必须支持“齐刘海”
-
今日消息,苹果公司通过邮件告知应用程序开发者,从2018年4月起提交给AppStore的所有新应用必须支持iPhoneX的超级视网膜显示器。这意味着新应用程序的开发者必须确保它们适应“齐刘海”,并...
- 耗时一年多,QEMU开发者成功在电脑上模拟了初版iPhone OS
-
IT之家12月24日消息,用户通过黑苹果(Hackintosh)工具,已经可以在非Mac设备上运行macOS系统。但由于种种限制,至今也没有多少人能够在PC上运行iOS系统。现...
- 下个月的WWDC后,苹果将发布原生Watch SDK测试版本
-
在近日Re/code举办的CodeConference上,苹果的运营副总裁JeffWilliams称,目前有4000多个AppleWatch应用上线,而未来的苹果表开发者套件,将允许开发者直接获...
- 苹果再次提醒:4月起强制要求APP进行适配
-
点击右上角关注我们,每天给您带来最新最潮的科技资讯,让您足不出户也知道科技圈大事!软件适配对于许多厂商来说都是一个比较头疼的事,苹果在握紧AppStore审核权的情况下情况要好许多。最近他们公布了...
- 苹果Xcode 16首个Beta版发布,AI代码补全最少需16GB内存
-
IT之家6月12日消息,在苹果WWDC24开发者大会上,苹果发布了iOS18、macOS15Sequoia等最新版本系统更新。与此同时,苹果推出了Xcode16开发工具的首...
- 传苹果已向特定开发者开放iWatch SDK
-
|责编:薄志强苹果会不会在这次发布会中发布全新的智能手表产品iWatch还很难说,不少人认为由于iWatch的消息少之又少,很可能这次还是没有iWatch。不过现在又有外媒传出消息称,苹果已经选定了...
- 苹果发布Swift 6语言:引入新测试框架、增强C++ 互操作性
-
IT之家9月20日消息,科技媒体devclass昨日(9月19日)报道,苹果公司在发布iOS/iPadOS18和macOS15Sequoia系统之外,还发布了Sw...
- 发布Siri SDK 之前苹果还是先想想这个问题
-
今年的GoogleI/O大会上,在预览GoogleHome时,我们就看到了设备可以互相对话的场景是多么惊艳,苹果快点跟上吧。最近因为亚马逊Echo和谷歌GoogleHome的火热...
- iOS 17.2 SDK代码确认古尔曼爆料:免开箱更新苹果iPhone系统
-
IT之家10月27日消息,彭博社的马克古尔曼(MarkGurman)本月早些时候发布报道,称苹果正在研发新的系统,可以让员工在不拆开包装的情况下,升级iPhone的iOS系统。根据国...
- 《企业应用架构模式》之事件驱动架构
-
事件驱动架构(Event-DrivenArchitecture,EDA)是一种强调事件流和异步通信的应用程序架构。在该架构中,应用程序被分解为多个小型、可独立部署的组件,这些组件通过事件进行通信...
- k8s中常用的controller以及用途和对应机制
-
controller的用途ReplicaSet、Deployment、StatefulSet:用于无状态和有状态应用的副本管理。DaemonSet:确保每个节点上都运行一个副本的控制器。...
- Disruptor框架源码阅读-如何不重复消费
-
RingBuffer如何保证数据不丢失由于ringbuffer是一个环形的队列,那么生产者和消费者在遍历这个队列的时候,如何制衡呢?1、生产快,消费慢,数据丢失?生产者速度过快,导致一个对象还没消...
- C# 控制电脑睡眠,休眠,关机以及唤醒
-
最近碰到一个关于芯片测试过程中的问题,这颗芯片是用在笔记本端口上,笔记本客户那边会有一个压力测试,就是频繁的电脑电源状态切换,S0(正常使用的开机状态),S3(睡眠模式),S4(休眠模式)以及S5(关...
- 大厂防止超卖的7种实现,很受用!(大厂防止超卖的7种实现,很受用的产品)
-
高并发场景在现场的日常工作中很常见,特别是在互联网公司中,这篇文章就来通过秒杀商品来模拟高并发的场景。本文环境:...
- 臻识车牌识别配制MQTT通讯,解析车号
-
在物联网项目中,我们的软件与车牌识别通讯,通常使用MQTT通讯更简单。...
你 发表评论:
欢迎- 一周热门
-
-
前端面试:iframe 的优缺点? iframe有那些缺点
-
带斜线的表头制作好了,如何填充内容?这几种方法你更喜欢哪个?
-
漫学笔记之PHP.ini常用的配置信息
-
[干货] JAVA - JVM - 2 内存两分 [干货]+java+-+jvm+-+2+内存两分吗
-
其实模版网站在开发工作中很重要,推荐几个参考站给大家
-
推荐7个模板代码和其他游戏源码下载的网址
-
正在学习使用python搭建自动化测试框架?这个系统包你可能会用到
-
织梦(Dedecms)建站教程 织梦建站详细步骤
-
2024PHP在线客服系统源码+完全开源 带详细搭建教程
-
【开源分享】2024在线客服系统PHP源码(安装教程+全新UI)
-
- 最近发表
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)