当前位置: 首页 > news >正文

HashMap ConcurrentHashMap

问题描述

翻翻别人的面试经历

这里在知乎上看到的,分享出了自己面试阿里Java岗的面试题。

clipboard.png

看了一下,除了Spring之外的其他很多题都不会,但是不能拿学校没讲Java作为借口,因为可能讲了也不会。

但是第九个问题,我觉得应该立刻话时间研究研究了,因为之前在缓存中用到了这个。

当时也不明白具体HashMapConcurrentHashMap究竟有什么区别。

clipboard.png

只是记得之前看过有关大数据的场景下利用缓存减轻数据库压力的文章,文中说常用ConcurrentHashMap,所以这里缓存就用这个了,其实并不懂原理,下面,让我们一起来研究一下。

Map

Map大家都熟悉了,Java中也有,JavaScript中也有。

Map是一种键值对类型的数据结构,根据键映射到值。

不分析源码了,就把思想给大家讲一下,以下主要以图为主。

HashMap

Java7

clipboard.png

HashMap的本质是一个可变长度的数组,在数组中每个位置保存的是一个Entry节点,该节点存储有hashkeyvaluenext等信息。

Java7中的HashMap实现与我们在数据结构中学习的类似,对key进行hash,如果冲突了,则添加到链表中。

然后查询的时候就先根据hash找到相应的位置,然后根据链表逐一比较,返回相应的value。时间复杂度取决于链表的长度,时间复杂度为O(N)

Java8

clipboard.png

Java8中对HashMap进行了优化,如果链表中元素超过8个时,就将链表转化为红黑树,以减少查询的复杂度,将时间复杂度降低为O(logN)

HashMap没有对多线程的场景下做任何的处理,不用说别的,就两个线程同时put,然后冲突了,两者需要操作一个链表/红黑树,这肯定就会有错误发生,所以HashMap是线程不安全的。

HashTable

HashTableJava7中的HashMap类似,也是一个数组加链表,不过这个线程安全。

HashTable线程安全,但是它的线程安全是依赖将所有修改HashTable的代码块都用synchronized修饰。

synchronized关键字我们之前在单例模式中用到过,它修饰的代码块,同一时刻只允许一个线程访问,其他线程会被阻塞,等待该线程执行完再执行。

所以,在HashTable中,一个线程在put,其余的线程在get的时候就会被阻塞,无法并行。所以不推荐使用HashTable,虽然它线程安全。

ConcurrentHashMap

HashMap线程不安全,HashTable性能又不好,当然需要设计一个新类去解决这些问题,这就是ConcurrentHashMap

Java7

clipboard.png

这是Java7中实现线程安全的思路,ConcurrentHashMap16segment组成,每个segment就相当于一个HashMap(数组+链表)。

segment最多16个,想要扩容,就是扩充每个segment中数组的长度。

然后只要实现每个segment是线程安全的,就让这个Map线程安全了。每个segment是加锁的,对修改segment的操作加锁,不影响其他segment的使用,所以理想情况下,最多支持16个线程并发修改segment,这16个线程分别访问不同的segment

同时,在segment加锁时,所有读线程是不会受到阻塞的。

这样设计,putget的基本操作就是先找segment,再找segment中的数组位置,再查链表。

Java8

后来人们发现Java7这样设计太复杂了,回归本质。

HashMap线程不安全的问题完全都是出在对链表/红黑树的操作上,为什么非要建一个segment加锁呢?直接对链表/红黑树加锁不就好了?

clipboard.png

所以Java8ConcurrentHashMap完全就是HashMap进行加锁,实现线程安全。

这里总结的很简单,其实源码中对这个的实现特别复杂,有兴趣的可以去看看,反正我是看着头大。

总结

  1. HashMap线程不安全。
  2. HashTable线程安全,但性能差,不推荐使用。
  3. ConcurrentHashMap线程安全。
  4. ConcurrentHashMapJava7中使用segment实现,对每个segment加锁。
  5. ConcurrentHashMapJava8中是直接在HashMap的基础上进行加锁。

参考文献:

Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析
ConcurrentHashMap、HashTable、HashMap三兄弟

相关文章:

  • 第三百九十三节,Django+Xadmin打造上线标准的在线教育平台—Xadmin后台进阶开发配置...
  • 软件下载
  • 7. Oracle数据加载和卸载
  • 工作的第6个年头发现DateFormat是not synchronized
  • JAVA自学笔记18
  • android 9 patch
  • C#中string.format用法详解
  • session共享问题解决方案
  • C#编程(六十)----------LINQ的概述
  • 使用 Zipkin 和 Brave 实现分布式系统追踪
  • 让XCode自动CodeReview你的代码-OCLint使用
  • 对话翁志:京东大数据如何让技术真正落地
  • Logstash+FileBeat+MongoDB+Flask打造的日志系统(三)
  • 【SignalR学习系列】5. SignalR WPF程序
  • 使用UAC白名单让指定的程序不受UAC限制
  • hexo+github搭建个人博客
  • 4. 路由到控制器 - Laravel从零开始教程
  • android高仿小视频、应用锁、3种存储库、QQ小红点动画、仿支付宝图表等源码...
  • JS题目及答案整理
  • PermissionScope Swift4 兼容问题
  • Python十分钟制作属于你自己的个性logo
  • Python学习之路13-记分
  • Swift 中的尾递归和蹦床
  • vue脚手架vue-cli
  • 闭包--闭包作用之保存(一)
  • 关于extract.autodesk.io的一些说明
  • 聊聊springcloud的EurekaClientAutoConfiguration
  • 面试总结JavaScript篇
  • 容器化应用: 在阿里云搭建多节点 Openshift 集群
  • 腾讯优测优分享 | Android碎片化问题小结——关于闪光灯的那些事儿
  • 系统认识JavaScript正则表达式
  • 新手搭建网站的主要流程
  • 云大使推广中的常见热门问题
  • d²y/dx²; 偏导数问题 请问f1 f2是什么意思
  • Linux权限管理(week1_day5)--技术流ken
  • 组复制官方翻译九、Group Replication Technical Details
  • #NOIP 2014# day.1 T3 飞扬的小鸟 bird
  • $(document).ready(function(){}), $().ready(function(){})和$(function(){})三者区别
  • (AngularJS)Angular 控制器之间通信初探
  • (Arcgis)Python编程批量将HDF5文件转换为TIFF格式并应用地理转换和投影信息
  • (附源码)springboot金融新闻信息服务系统 毕业设计651450
  • (九)One-Wire总线-DS18B20
  • (论文阅读40-45)图像描述1
  • (亲测)设​置​m​y​e​c​l​i​p​s​e​打​开​默​认​工​作​空​间...
  • (十)【Jmeter】线程(Threads(Users))之jp@gc - Stepping Thread Group (deprecated)
  • (转载)VS2010/MFC编程入门之三十四(菜单:VS2010菜单资源详解)
  • .NET Core6.0 MVC+layui+SqlSugar 简单增删改查
  • .NET 中让 Task 支持带超时的异步等待
  • .NET/C# 编译期间能确定的相同字符串,在运行期间是相同的实例
  • .NET/C# 反射的的性能数据,以及高性能开发建议(反射获取 Attribute 和反射调用方法)
  • .NET/C# 使用 ConditionalWeakTable 附加字段(CLR 版本的附加属性,也可用用来当作弱引用字典 WeakDictionary)
  • @Data注解的作用
  • [20140403]查询是否产生日志
  • [android] 天气app布局练习
  • [Asp.net MVC]Bundle合并,压缩js、css文件