分享

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

问题导读:

1.HashMap是一个什么结构,主要用途是什么?
2.HashMap为啥会产生死循环?
3.HashMap死循环如何解决?

前言

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


a1.png


一尘


a2.png


慧能

这个听为师慢慢道来

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


a3.png


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


a4.png

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


a5.png


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


a6.png


环的形成

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


a7.png


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


a8.png


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


a9.png


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


a10.png


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


a11.png


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


a12.png


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


a13.png


线程2执行完之后为下图


a14.png


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


a15.png


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


a16.png


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


a17.png


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


a18.png


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


a19.png


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


a20.png


执行完后为下图


a21.png


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


a22.png


执行完为下图


a23.png


线程1继续第三遍循环(注意:此次循环会形成环)
先执行 Entry<K,V> next = <1,A>.next


a24.png


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


a25.png


此时环已经形成
然后执行剩余的两行代码


a26.png


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


a27.png


死循环的发生

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


a28.png


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


a29.png


原来死循环是这样形成的



一尘







慧能



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

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



一尘





慧能

用ConcurrentHashMap



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


最新经典文章,欢迎关注公众号










没找到任何评论,期待你打破沉寂

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

推荐上一条 /2 下一条