天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!

时间:2021-6-30 作者:qvyue

前言

师傅,我常常听别人说,不要在并发情况下使用HashMap,可能会出现死循环,这个死循环是怎么形成的呢?

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

一尘

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

慧能

这个听为师慢慢道来

我们都知道,HashMap的底层是由数组加链表来实现的

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

当往HashMap中put一个键值对时,如果HashMap中的键值对数量 size 大于或等于阈值(threshold) 并且null != table[bucketIndex] 时会进行扩容

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

bucketIndex为该键值对最后被散列到hash表table的位置

比如 table的初始容量为4,加载因子为0.75,此时阈值为3,table已有三个元素,现在put一个元素,被散列到table[1]处,而table[1] != null,此时满足扩容条件

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

阈值 = 容量 * 加载因子

threshold = capacity * loadFactor

扩容时先生成一个是table大小2倍的newTable,然后把table中的元素迁移到newTable中,迁移的工作就由 transfer方法来完成,这个方法就是引起死循环的原因所在

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

环的形成

现在我们来模拟一下环是如何形成的,设HashMap的初始容量为4,先往HashMap中依次put三个元素、、,它们都被散列到table[1]处,形成了链

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

假设此时有两个线程并发对该HashMap进行put,线程1 put 时,这个键值对被散列到table[1]处,满足扩容条件,进行扩容(生成newTable并进行迁移)

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

此时,线程1用 transfer 方法将 table中的元素迁移到 newTable 中,假设线程1执行完 transfer 方法中的 Entry next = e.next 语句后时间片用完,挂起

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

此时,线程1内的 e 指向 ,next指向

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

然后线程2 put ,同样这个键值对被散列到table[1]处,满足扩容条件,进行扩容

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

生成完newTable后用transfer方法进行迁移,执行完Entry next = e.next;后与线程1一样,e指向,next指向

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

线程2 然后执行循环体下面的语句

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

线程2执行完之后为下图

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

然后线程2按照同样的逻辑进行第二次循环(while循环),下面是第二遍循环后的结果

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

下面是第三遍循环后的结果

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

此时,线程2时间片用完,线程1得到时间片,开始执行

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

注意,此时线程1的e指向,next指向,在线程2操作链表的时候,线程1 中的e,next指向的元素没变(一直是红色的e和next)

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

线程一和线程二整体图为:

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

然后线程1开始执行循环内剩下的代码

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

执行完后为下图

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

线程1继续执行第二遍循环

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

执行完为下图

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

线程1继续第三遍循环(注意:此次循环会形成环)

先执行 Entry next = .next

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

然后执行 .next = newTable[1]

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

此时环已经形成

然后执行剩余的两行代码

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

执行完,e 为 null,退出循环

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

死循环的发生

当形成环后,当给HashMap中put元素的时候,这个元素恰巧落在了table[1](不管有没有更新table),而这个元素的Key不在table[1]这条链上,此时会发生死循环

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

或者在get元素的时候,该元素恰巧落在table[1]上,并且该元素的Key不在该链上,会发生死循环

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

原来死循环是这样形成的

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

一尘

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

慧能

对,核心就是线程2修改了原来的链表结构,而线程1却以原来的逻辑执行迁移

那并发下我还想使用散列表这种数据结构怎么办呢

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

一尘

天猫面试官:说说高并发下的HashMap的死循环是怎么形成的!
image

慧能

用ConcurrentHashMap

今日份读者福利:转发+关注公众号:麒麟改bug,获取小编整理好的200多页Java核心学习笔记一份!

最后

喜欢小编今日的分享,记得关注我点赞哟,感谢支持!重要的事情说三遍,转发+转发+转发,一定要记得转发 关注哦!!!

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。