写点什么

面试官:高并发下 HashMap 的死循环是怎么形成的?

发布于: 2021 年 02 月 07 日

代码回顾

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



一尘



慧能


这个听为师慢慢道来


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



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



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


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



阈值 = 容量 * 加载因子


threshold = capacity * loadFactor


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



环的形成


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



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



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



此时,线程 1 内的 e 指向 <1,“A”>,next 指向<9,”C”>



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



生成完 newTable 后用 transfer 方法进行迁移,执行完 Entry<K,V> next = e.next;后与线程 1 一样,e 指向<1,”A”>,next 指向<9,”C”>



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



线程 2 执行完之后为下图



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



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



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



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



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



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



执行完后为下图



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



执行完为下图



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


先执行 Entry<K,V> next = <1,A>.next



然后执行 <1,A>.next = newTable[1]



此时环已经形成


然后执行剩余的两行代码



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



死循环的发生

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



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



原来死循环是这样形成的



一尘



慧能


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


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



一尘



慧能


用 ConcurrentHashMap


转载自微信公众号:趣谈编程


用户头像

爱学习,爱Java,爱生活,冲鸭~ 2020.11.03 加入

领取文中资料加微信:mxx2020666, 备注:InfoQ 即可

评论

发布
暂无评论
面试官:高并发下HashMap的死循环是怎么形成的?