资讯专栏INFORMATION COLUMN

HashMap ConcurrentHashMap

forrest23 / 2863人阅读

摘要:与中的类似,也是一个数组加链表,不过这个线程安全。线程安全,但是它的线程安全是依赖将所有修改的代码块都用修饰。这是中实现线程安全的思路,由个组成,每个就相当于一个数组链表。线程安全,但性能差,不推荐使用。

问题描述 翻翻别人的面试经历

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

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

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

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

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

Map

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

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

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

HashMap Java7

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

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

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

Java8

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

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

HashTable

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

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

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

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

ConcurrentHashMap

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

Java7

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

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

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

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

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

Java8

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

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

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

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

总结

HashMap线程不安全。

HashTable线程安全,但性能差,不推荐使用。

ConcurrentHashMap线程安全。

ConcurrentHashMapJava7中使用segment实现,对每个segment加锁。

ConcurrentHashMapJava8中是直接在HashMap的基础上进行加锁。

参考文献:

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

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/76851.html

相关文章

  • 这几道Java集合框架面试题在面试中几乎必问

    摘要:若遇到哈希冲突,则将冲突的值加到链表中即可。之后相比于之前的版本,之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值默认为时,将链表转化为红黑树,以减少搜索时间。有序,唯一红黑树自平衡的排序二叉树。 本文是最最最常见Java面试题总结系列第三周的文章。主要内容: Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...

    bigdevil_s 评论0 收藏0
  • java中ConcurrentHashMap的使用及在Java 8中的冲突方案

    摘要:中的使用及在中的冲突方案引言简称是在作为的替代选择新引入的,是包的重要成员。为了解决在频繁冲突时性能降低的问题,中使用平衡树来替代链表存储冲突的元素。目前,只有和会在频繁冲突的情况下使用平衡树。 java中ConcurrentHashMap的使用及在Java 8中的冲突方案 1、引言 ConcurrentHashMap(简称CHM)是在Java 1.5作为Hashtable的替代选择新...

    kun_jian 评论0 收藏0
  • JDK1.8下ConcurrentHashMap的一些理解(一)

    摘要:如下代码省略相关代码省略相关代码可以看到在里面,是直接采用数组链表红黑树来实现,时间复杂度在和之间,如果链表转化为红黑树了,那么就是到。 在JDK1.8里面,ConcurrentHashMap在put方法里面已经将分段锁移除了,转而是CAS锁和synchronized ConcurrentHashMap是Java里面同时兼顾性能和线程安全的一个键值对集合,同属于键值对的集合还有Hash...

    Andrman 评论0 收藏0
  • 面试官:说说快速失败和安全失败是什么

    摘要:我们都接触这些集合类,这些在包的集合类就都是快速失败的而包下的类都是安全失败,比如。安全失败明白了什么是快速失败之后,安全失败也是非常好理解的。最后说明一下,快速失败和安全失败是对迭代器而言的。 什么是快速失败(fail-fast)和安全失败(fail-safe)?它们又和什么内容有关系。以上两点就是这篇文章的内容,废话不多话,正文请慢用。 我们都接触 HashMap、ArrayLis...

    calx 评论0 收藏0
  • Java容器类研究9:其它Map

    摘要:和的区别和的区别是,在操作的方法上加入关键字,使得线程安全。使用进行比较,或者传入的比较器。基于,它自己的任务主要是维护保持顺序的双向链表。和的区别提供了一个高效的线程安全的访问和更新的方式。在中的过程和类似。 HashTable和HashMap的区别 HashTable和HashMap的区别是,HashTable在操作table的方法上加入synchronized关键字,使得线程安全...

    zilu 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<