A股上市公司传智教育（股票代码 003032）旗下高端IT教育品牌

全国咨询/投诉热线：400-618-4000

好口碑IT培训机构

全国中心

 

JavaEE 鸿蒙应用开发 集成电路应用开发
(含嵌入式) 人工智能开发 AI+Linux云计算运维 Python+大数据开发 跨境电商 AI+设计 软件测试 新媒体+短视频
直播运营 HTML&JS+前端
首页新闻动态正文

HashMap在并发下可能出现的问题分析【黑马java培训】

更新时间:2019年07月26日 11时09分18秒 来源:黑马程序员论坛



HashMap在并发下可能出现的问题分析


我们都知道，HashMap在并发环境下使用可能出现问题，但是具体表现，以及为什么出现并发问题，
可能并不是所有人都了解，这篇文章记录一下HashMap在多线程环境下可能出现的问题以及如何避免。

在分析HashMap的并发问题前，先简单了解HashMap的put和get基本操作是如何实现的。

1.HashMap的put和get操作

大家知道HashMap内部实现是通过拉链法解决哈希冲突的，也就是通过链表的结构保存散列到同一数组位置的两个值，

put操作主要是判空，对key的hashcode执行一次HashMap自己的哈希函数，得到bucketindex位置，还有对重复key的覆盖操作。

对照源码分析一下具体的put操作是如何完成的：

涉及到的几个方法：
数据put完成以后，就是如何get，我们看一下get函数中的操作：
看一下链表的结点数据结构，保存了四个字段，包括key，value，key对应的hash值以及链表的下一个节点：
2.Rehash/再散列扩展内部数组长度

哈希表结构是结合了数组和链表的优点，在最好情况下，查找和插入都维持了一个较小的时间复杂度O(1)，
不过结合HashMap的实现，考虑下面的情况，如果内部Entry[] tablet的容量很小，或者直接极端化为table长度为1的场景，那么全部的数据元素都会产生碰撞，
这时候的哈希表成为一条单链表，查找和添加的时间复杂度变为O(N)，失去了哈希表的意义。
所以哈希表的操作中，内部数组的大小非常重要，必须保持一个平衡的数字，使得哈希碰撞不会太频繁，同时占用空间不会过大。

这就需要在哈希表使用的过程中不断的对table容量进行调整，看一下put操作中的addEntry()方法：

这里面resize的过程，就是再散列调整table大小的过程，默认是当前table容量的两倍。

关键的一步操作是transfer(newTable)，这个操作会把当前Entry[] table数组的全部元素转移到新的table中，
这个transfer的过程在并发环境下会发生错误，导致数组链表中的链表形成循环链表，在后面的get操作时e = e.next操作无限循环，Infinite Loop出现。


下面具体分析HashMap的并发问题的表现以及如何出现的。

3.HashMap在多线程put后可能导致get无限循环

HashMap在并发环境下多线程put后可能导致get死循环，具体表现为CPU使用率100%，
看一下transfer的过程：


并发下的Rehash

1）假设我们有两个线程。我用红色和浅蓝色标注了一下。

我们再回头看一下我们的 transfer代码中的这个细节：

1
2
3
4
5
6
7
do {
    Entry<K,V> next = e.next;// <--假设线程一执行到这里就被调度挂起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable;
    newTable = e;
    e = next;
} while (e != null);

而我们的线程二执行完成了。于是我们有下面的这个样子。

注意，因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

2）线程一被调度回来执行。

  • 先是执行 newTalbe = e;
  • 然后是e = next，导致了e指向了key(7)，
  • 而下一次循环的next = e.next导致了next指向了key(3)

3）一切安好。

线程一接着工作。把key(7)摘下来，放到newTable的第一个，然后把e和next往下移。

4）环形链接出现。

e.next = newTable 导致  key(3).next 指向了 key(7)

注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

于是，当我们的线程一调用到，HashTable.get(11)时，悲剧就出现了——Infinite Loop。

针对上面的分析模拟这个例子，

这里在run中执行了一个自增操作，i++非原子操作，使用AtomicInteger避免可能出现的问题：
测试一下：

注意并发问题并不是一定会产生，可以多执行几次，

我试验了上面的代码很容易产生无限循环，控制台不能终止，有线程始终在执行中，

这是其中一个死循环的控制台截图，可以看到六个线程顺利完成了put工作后销毁，还有四个线程没有输出，卡在了put阶段，感兴趣的可以断点进去看一下：

上面的代码，如果把注释打开，换用ConcurrentHashMap就不会出现类似的问题。

4.多线程put的时候可能导致元素丢失

HashMap另外一个并发可能出现的问题是，可能产生元素丢失的现象。

考虑在多线程下put操作时，执行addEntry(hash, key, value, i)，如果有产生哈希碰撞，
导致两个线程得到同样的bucketIndex去存储，就可能会出现覆盖丢失的情况：

5.使用线程安全的哈希表容器

那么如何使用线程安全的哈希表结构呢，这里列出了几条建议：

使用Hashtable 类，Hashtable 是线程安全的；
使用并发包下的java.util.concurrent.ConcurrentHashMap，ConcurrentHashMap实现了更高级的线程安全；
或者使用synchronizedMap() 同步方法包装 HashMap object，得到线程安全的Map，并在此Map上进行操作。

推荐了解热门学科

java培训 Python人工智能 Web前端培训 PHP培训
区块链培训 影视制作培训 C++培训 产品经理培训
UI设计培训 新媒体培训 产品经理培训 Linux运维
大数据培训 智能机器人软件开发




传智播客是一家致力于培养高素质软件开发人才的科技公司，“黑马程序员”是传智播客旗下高端IT教育品牌。自“黑马程序员”成立以来，教学研发团队一直致力于打造精品课程资源，不断在产、学、研3个层面创新自己的执教理念与教学方针，并集中“黑马程序员”的优势力量，针对性地出版了计算机系列教材50多册，制作教学视频数+套，发表各类技术文章数百篇。

传智播客从未停止思考

传智播客副总裁毕向东在2019IT培训行业变革大会提到，“传智播客意识到企业的用人需求已经从初级程序员升级到中高级程序员，具备多领域、多行业项目经验的人才成为企业用人的首选。”

中级程序员和初级程序员的差别在哪里?
项目经验。毕向东表示，“中级程序员和初级程序员最大的差别在于中级程序员比初级程序员多了三四年的工作经验，从而多出了更多的项目经验。“为此，传智播客研究院引进曾在知名IT企业如阿里、IBM就职的高级技术专家，集中研发面向中高级程序员的课程，用以满足企业用人需求，尽快补全IT行业所需的人才缺口。

何为中高级程序员课程?

传智播客进行了定义。中高级程序员课程，是在当前主流的初级程序员课程的基础上，增加多领域多行业的含金量项目，从技术的广度和深度上进行拓展。“我们希望用5年的时间，打造上百个高含金量的项目，覆盖主流的32个行业。”传智播客课程研发总监于洋表示。




黑马程序员热门视频教程【点击播放】

Python入门教程完整版（懂中文就能学会） 零起点打开Java世界的大门
C++| 匠心之作 从0到1入门学编程 PHP|零基础入门开发者编程核心技术
Web前端入门教程_Web前端html+css+JavaScript 软件测试入门到精通


相关阅读

分享到：QQ空间新浪微博腾讯微博人人网微信

北京传智播客教育科技有限公司版权所有
Copyright 2006-2019, All Rights Reserved

在线咨询 我要报名
和我们在线交谈！