ConcurrentHashMap的实现原理(JDK1.7和JDK1.8)
yuyutoo 2025-03-26 18:54 12 浏览 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)。
感谢诸君的观看,文中如有纰漏,欢迎在评论区来交流。如果这篇文章帮助到了你,欢迎点赞关注。
相关推荐
- ETCD 故障恢复(etc常见故障)
-
概述Kubernetes集群外部ETCD节点故障,导致kube-apiserver无法启动。...
- 在Ubuntu 16.04 LTS服务器上安装FreeRADIUS和Daloradius的方法
-
FreeRADIUS为AAARadiusLinux下开源解决方案,DaloRadius为图形化web管理工具。...
- 如何排查服务器被黑客入侵的迹象(黑客 抓取服务器数据)
-
---排查服务器是否被黑客入侵需要系统性地检查多个关键点,以下是一份详细的排查指南,包含具体命令、工具和应对策略:---###**一、快速初步检查**####1.**检查异常登录记录**...
- 使用 Fail Ban 日志分析 SSH 攻击行为
-
通过分析`fail2ban`日志可以识别和应对SSH暴力破解等攻击行为。以下是详细的操作流程和关键分析方法:---###**一、Fail2ban日志位置**Fail2ban的日志路径因系统配置...
- 《5 个实用技巧,提升你的服务器安全性,避免被黑客盯上!》
-
服务器的安全性至关重要,特别是在如今网络攻击频繁的情况下。如果你的服务器存在漏洞,黑客可能会利用这些漏洞进行攻击,甚至窃取数据。今天我们就来聊聊5个实用技巧,帮助你提升服务器的安全性,让你的系统更...
- 聊聊Spring AI Alibaba的YuQueDocumentReader
-
序本文主要研究一下SpringAIAlibaba的YuQueDocumentReaderYuQueDocumentReader...
- Mac Docker环境,利用Canal实现MySQL同步ES
-
Canal的使用使用docker环境安装mysql、canal、elasticsearch,基于binlog利用canal实现mysql的数据同步到elasticsearch中,并在springboo...
- RustDesk:开源远程控制工具的技术架构与全场景部署实战
-
一、开源远程控制领域的革新者1.1行业痛点与解决方案...
- 长安汽车一代CS75Plus2020款安装高德地图7.5
-
不用破解原车机,一代CS75Plus2020款,安装车机版高德地图7.5,有红绿灯读秒!废话不多讲,安装步骤如下:一、在拨号状态输入:在电话拨号界面,输入:*#518200#*(进入安卓设置界面,...
- Zookeeper使用详解之常见操作篇(zookeeper ui)
-
一、Zookeeper的数据结构对于ZooKeeper而言,其存储结构类似于文件系统,也是一个树形目录服务,并通过Key-Value键值对的形式进行数据存储。其中,Key由斜线间隔的路径元素构成。对...
- zk源码—4.会话的实现原理一(会话层的基本功能是什么)
-
大纲1.创建会话...
- Zookeeper 可观测性最佳实践(zookeeper能够确保)
-
Zookeeper介绍ZooKeeper是一个开源的分布式协调服务,用于管理和协调分布式系统中的节点。它提供了一种高效、可靠的方式来解决分布式系统中的常见问题,如数据同步、配置管理、命名服务和集群...
- 服务器密码错误被锁定怎么解决(服务器密码错几次锁)
-
#服务器密码错误被锁定解决方案当服务器因多次密码错误导致账户被锁定时,可以按照以下步骤进行排查和解决:##一、确认锁定状态###1.检查账户锁定状态(Linux)```bash#查看账户锁定...
- zk基础—4.zk实现分布式功能(分布式zk的使用)
-
大纲1.zk实现数据发布订阅...
- 《死神魂魄觉醒》卡死问题终极解决方案:从原理到实战的深度解析
-
在《死神魂魄觉醒》的斩魄刀交锋中,游戏卡死犹如突现的虚圈屏障,阻断玩家与尸魂界的连接。本文将从技术架构、解决方案、预防策略三个维度,深度剖析卡死问题的成因与应对之策,助力玩家突破次元壁障,畅享灵魂共鸣...
你 发表评论:
欢迎- 一周热门
-
-
前端面试:iframe 的优缺点? iframe有那些缺点
-
带斜线的表头制作好了,如何填充内容?这几种方法你更喜欢哪个?
-
漫学笔记之PHP.ini常用的配置信息
-
推荐7个模板代码和其他游戏源码下载的网址
-
其实模版网站在开发工作中很重要,推荐几个参考站给大家
-
[干货] JAVA - JVM - 2 内存两分 [干货]+java+-+jvm+-+2+内存两分吗
-
正在学习使用python搭建自动化测试框架?这个系统包你可能会用到
-
织梦(Dedecms)建站教程 织梦建站详细步骤
-
【开源分享】2024PHP在线客服系统源码(搭建教程+终身使用)
-
2024PHP在线客服系统源码+完全开源 带详细搭建教程
-
- 最近发表
-
- ETCD 故障恢复(etc常见故障)
- 在Ubuntu 16.04 LTS服务器上安装FreeRADIUS和Daloradius的方法
- 如何排查服务器被黑客入侵的迹象(黑客 抓取服务器数据)
- 使用 Fail Ban 日志分析 SSH 攻击行为
- 《5 个实用技巧,提升你的服务器安全性,避免被黑客盯上!》
- 聊聊Spring AI Alibaba的YuQueDocumentReader
- Mac Docker环境,利用Canal实现MySQL同步ES
- RustDesk:开源远程控制工具的技术架构与全场景部署实战
- 长安汽车一代CS75Plus2020款安装高德地图7.5
- Zookeeper使用详解之常见操作篇(zookeeper 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)