博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
(转)并发场景下HashMap死循环导致CPU100%的问题
阅读量:7224 次
发布时间:2019-06-29

本文共 952 字,大约阅读时间需要 3 分钟。

    问题的核心点在于多线程进行扩容的时候每个线程会生成一个新的hashtab对象,线程A生成新的hashtab以后,线程B在线程A新生成的hastab上进行操作会造成死循环。

    可以参考jdk1.7的hashmap扩容问题的文章。

核心摘录

正常的ReHash的过程

画了个图做了个演示。

我假设了我们的hash算法就是简单的用key mod 一下表的大小(也就是数组的长度)。

最上面的是old hash 表,其中的Hash表的size=2, 所以key = 3, 7, 5,在mod 2以后都冲突在table[1]这里了。

接下来的三个步骤是Hash表 resize成4,然后所有的 重新rehash的过程

img_5e5fa5460c618039690b7a736cbdf12f.png
串行rehash

并发下的Rehash

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

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

img_19233ede12aeb66b0373e68c0595e5ba.png
扩容代码

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

img_9d0405bdac6586641a14742c31a6d00a.png

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

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

先是执行 newTalbe[i] = e;

然后是e = next,导致了e指向了key(7),

而下一次循环的next = e.next导致了next指向了key(3)

img_4ea4930fb2b87d0553c3560f060e5ef2.png

3)一切安好。

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

img_96168bc9052094192ee23419dc3b0794.png

4)环形链接出现。

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

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

img_3e6aee62745527b5bc9a720ee34d5e81.png

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

此时两个线程put完毕,线程二先完成rehash,之后再线程一rehash,线程一最终put的链形成了闭环,但是这两个线程没有死循环,只是后来get的线程如果进入这个闭环链,就死循环了,并且进入的线程越多,CPU消耗的越大,最终到达100%

参考文章

jdk1.7:

jdk1.8:

转载地址:http://rtkfm.baihongyu.com/

你可能感兴趣的文章
我的友情链接
查看>>
CentOS 下安装 Lnmp
查看>>
redis系列:通过日志案例学习string命令
查看>>
世界冠军之路:菜鸟车辆路径规划求解引擎研发历程
查看>>
Linux-sendmail
查看>>
关于BSTR的困惑
查看>>
什么时候使用HashMap?它有什么特点?
查看>>
框架名
查看>>
编译安装PHP
查看>>
插入透明背景Flash的HTML代码
查看>>
无标题
查看>>
我的友情链接
查看>>
Web前端入门学习(3)——CSS选择器
查看>>
DNS的搭建
查看>>
Apache/Nginx 访问日志分析脚本
查看>>
Curator的使用
查看>>
第五章 集合类型
查看>>
我的友情链接
查看>>
nagios监控服务出现FLAPPING状态时无法发出邮件报警信息
查看>>
数据库链接字符串方法
查看>>