重庆分公司,新征程启航

为企业提供网站建设、域名注册、服务器等服务

HashMap,Hashtable,ConcurrentHashMap-创新互联

目录

创新互联成立于2013年,我们提供高端成都网站建设网站制作网站设计、网站定制、成都营销网站建设微信小程序开发、微信公众号开发、成都网站推广服务,提供专业营销思路、内容策划、视觉设计、程序开发来完成项目落地,为成都发电机租赁企业提供源源不断的流量和订单咨询。

一、多线程使用HashMap的一些线程安全问题

①造成数据新增丢失

②扩容时候,造成链表成环

二、Hashtable和HashMap的区别 

①核心方法加锁

②其他语法上面的略微差异 

三、引入ConcurrentHashMap【重要】

①ConcurrentHashMap相比于Hashtable的优势

Hashtable的缺点:

ConcurrentHashMap的一些优化措施(jdk1.8往后)

(1)每一个哈希桶,都是一把"锁"

 ​编辑

(2)ConcurrentHashMap不针对get(Object key)方法加锁

(3)ConcurrentHashMap针对部分修改操作,采用了volatile+原子的方式,让写的操作与不加锁的get()方式不会产生锁冲突 

(4)扩容操作的优化


 这三种数据结构,都是对于哈希表的具体实现。

 有关哈希表的具体设计,我们在前面的文章当中也提到了,关于HashMap的简单源码分析,以及HashMap的具体的一些实现,也在下面这两篇文章当中提到了:

 (1条消息) HashMap简单源码分析_革凡成圣211的博客-博客https://blog.csdn.net/weixin_56738054/article/details/127786631?spm=1001.2014.3001.5501
(1条消息) Java的手写简单的哈希表_革凡成圣211的博客-博客https://blog.csdn.net/weixin_56738054/article/details/127416821?spm=1001.2014.3001.5501


下面,将重点分析,多线程使用HashMap的一些问题,以及Hashtable、ConcurrentHashMap和HashMap之间的一些区别。


一、多线程使用HashMap的一些线程安全问题      ①造成数据新增丢失

  因为HashMap当中,并没有涉及任何的加锁操作,因此:当多个线程同时调用put()的时候,有可能在两个键的哈希值一样的时候,之后调用put()的线程新增的值覆盖掉最开始线程新增的值。

  图解:

  


②扩容时候,造成链表成环

 我们了解到,扩容的操作,实际上是HashMap重现初始化一个原来大小2倍的数组,并且根据新的数组的长度,重新哈希的这样一个过程。

  如果执行并发扩容,那么,很有可能在扩容的时候,让哈希表当中某一个哈希桶的链表变成了一个"环"。那么,也就意味着如果想获取某一个元素,对哈希桶对应位置的链表进行遍历的时候,没有任何一个节点的next指针为null,那么将引发死循环。


二、Hashtable和HashMap的区别        ①核心方法加锁

  Hashtable的核心方法put()和get()方法被加锁了。因此,Hashtable是线程安全的

  


②其他语法上面的略微差异 

 (1)HashMap允许null值作为键和值,而Hashtable不允许null作为键和值。

 (2)添加值的哈希算法不同,对于HashMap来说,添加值的哈希算法采用的是内部自定义的一个哈希算法,而Hashtable采用的直接是key.hash()的方式计算出的哈希值。但是负载因子都是0.75.

 (3)初始化的容量不同:HashMap的默认初始容量为16,而Hashtable默认的初始容量为11.

 (4)扩容的方式不同:HashMap采用的是2倍大小的方式扩容,而Hashtable扩容的规则为当前容量*2+1.

 ...这些差异,罗列一部分即可,最重要的还是多线程和单线程的使用环境区别。


三、引入ConcurrentHashMap【重要】 ①ConcurrentHashMap相比于Hashtable的优势

对于Hashtable来说,它解决线程安全问题的方式,比较"粗鲁”。

Hashtable的缺点:

 第一:

 Hashtable使用的直接是synchronized修饰核心方法的方式来加锁的,那么,如果两个线程同时只是读取某一个变量的值,根据之前对线程安全问题的概述,如果线程仅仅只是对变量进行读操作而并非写操作,那么并不会发生线程安全问题。

 但是Hashtable即使是在多个线程同时读取某个Entry的值的时候,也照样会造成阻塞等待的情况,因此Hashtable的锁的粒度是比较大的。


 第二:

 即使是put()、get()操作,发生线程安全问题的前提条件也必须是需要put()的两个键的哈希值相同的情况,也就是,针对同一个哈希桶进行put()或者get()的情况。

 而Hashtable采用的是直接“一棒打死”。无论是否针对同一个哈希桶进行读写操作,只要多个线程同时调用一个map的put()或者get()方法,都会发生阻塞等待的情况。


ConcurrentHashMap的一些优化措施(jdk1.8往后)      (1)每一个哈希桶,都是一把"锁"

 让每一个哈希桶都是一把锁。当新增元素发生哈希冲突,也就是散列到同一个哈希地址的时候,才会发生锁冲突。

 这样,就有效减少了不必要的锁冲突,减小了锁的粒度

 

观察上面的图:当两个线程同时尝试分别修改同一个哈希地址的1,2节点的时候,会产生阻塞等待的情况。

当两个线程同时修改3,4节点的时候,不会产生阻塞等待。

也就是,只有发生了哈希冲突的时候,才会产生阻塞等待的情况 

观察一下源码:

 


  对于jdk1.8之前的代码,是采用分段锁的方式进行修改的。也就是,其中的N个哈希桶作为一把锁,如果有线程同时针对这N个为一把锁的哈希桶进行修改操作,会产生锁冲突,造成阻塞等待。


(2)ConcurrentHashMap不针对get(Object key)方法加锁

由于get()方法是通过key得到对应的value的值的方法,本质上是“读取”操作,当多个线程同时调用get()方法的时候,不存在线程安全问题。

因此,ConcurrentHashMap取消了对于get()方法加锁的机制。

 

这里需要注意的地方是,ConcurrentHashmap当中:

  Ⅰ一个线程读去数据,另外一个线程也同时去读取数据,这个时候不存在线程安全问题,也不存在锁冲突;因为ConcurrentHashMap没有针对get方法加锁

  Ⅱ一个线程去写数据,另外一个线程也去写数据,不存在线程安全问题,但是有可能存在锁冲突;存在锁冲突的前提是两个线程针对同一个哈希桶进行写操作。

  Ⅲ一个线程去读数据,另外一个线程去写数据,不存在线程安全问题,但是有可能产生锁冲突。

  对于第Ⅲ点,如果产生了锁冲突,那么就是意味着两个线程一个对于同一哈希桶进行"读"操作,另外一个针对哈希桶进行"写"操作,并且都是哈希桶有存放元素,也就是需要遍历的时候,才会产生锁冲突。

  如果哈希桶没有存放元素,是null的,那么,请往下面第(3)点查看。


(3)ConcurrentHashMap针对部分修改操作,采用了volatile+原子的方式,让写的操作变为"原子"的,从而与不加锁的读操作不会产生锁冲突 

 ConcurrentHashMap内部充分利用了CAS,来削减了加锁的次数。

 下面,举几个例子,关于ConcurrentHashMap是如何使用CAS的:

  例子1、当让存放元素之后,个数+1的时候,采用的是CAS的做法来保证数组当中实际存储key的数量+1这个操作的原子性

  

其中,addCount方法内部采用的就是CAS的做法来实现个数+1的原子性的。 


  例子2、 当对应的HashEntry数组当中,某一个位置不存放任何元素,也就是为null的时候,会采用cas的方式填充到对应的哈希地址。

 

 对于ConcurrentHashMap当中修改key的个数,本质上还是在addCount方法内部,通过CAS的方式来修改


(4)扩容操作的优化

      回顾一下HashMap或者Hashtable扩容的操作,它们都是创建一个更大容量的数组,然后把每一个元素重新哈希的做法。

  在数据量比较大的时候,会造成可能某次put()之后,线程会阻塞等待很长的时间,才可以完成扩容。

 扩容条件:

 ①当存放Node节点的数组长度小于64,并且单个哈希桶的链表的存放节点个数达到8的时候,会触发扩容;如果存放节点的数组长度>=64,那么会把当前的链表树化为红黑树。

 ②当存储的实际key的数量/Node数组的长度达到负载因子的时候,会触发扩容


以上两点,和jdk1.8版本的HashMap的扩容前提条件类似,没有太大的差别。

满足上面的条件之后,会进入到下面的操作:

首先申请一个原来数组大小2倍的新数组

如果有多个线程同时尝试扩容,那么,ConcurrentHashMap会对这些线程进行"分工”。何为分工呢?画个图简单看一看:

 也就是,每一个线程,分别对原有的数组上面的元素分别进行"搬运"操作,让它们都被各自的线程重新哈希到新的数组上面的位置,这样的效率会更加的高。


  同时,如果ConcurrentHashMap如果正在扩容的时候:

  其他线程调用get方法,那么调用的线程会查询旧数组和新的数组当中是否存在对应的key。

  其他线程如果调用remove方法,那么调用的线程会把旧数组和新的数组当中的key都删除掉。

  而不是一直阻塞等待,直到扩容执行完毕。


  

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


分享题目:HashMap,Hashtable,ConcurrentHashMap-创新互联
网站链接:http://cqcxhl.com/article/eigdp.html

其他资讯

在线咨询
服务热线
服务热线:028-86922220
TOP