HashMap是如何形成死循环的?(读后感)

660 阅读3分钟

   看到掘友写的一篇文章挺不错的,图也挺好,但是有些地方没有描述,可能是忽略了,特意加下我的理解。juejin.cn/post/684490…

第一个状态:

当线程一刚刚扩容好数组,此时刚要准备进行rehash,但是此时线程二强行插入进来执行,并且线程二已经rehash完成之后的状态图(上半部分表示的线程一,下半部分表示的是线程二)

在这里插入图片描述


第二个状态:

此时线程一已经被唤醒了,要开始进行操作rehash操作,把key为5的节点还是挂在数组下标为1的位置上,并且key为5的后面是9这个节点(这里其实吧之前的数组扩容为4个了,然后肯定需要重新定位下标啊,所以这里是对4进行取余,然后对应查到对应的数组下标下的链表中)在这里插入图片描述

第三个状态:

从第一个状态开始继续接着处理key为9的节点,所以应该是都挂在桶数组下标为1的链表上顺序为9---->5---->NULL

在这里插入图片描述

第四个状态:

此时在第三步时候处理9完毕之后,他发现节点9后面还有一个节点5(这个节点5是因为线程二中已经rehash完毕之后留下的),此时他又会把节点5放在线程一中的首部此时也就是5---->9----5(后面这部分的9–>5是保留的第三个状态留下的),到这里就形成了死循环。

在这里插入图片描述


上文都是引用,juejin.cn/post/684490…,这是链接,下文是本人简介,如有失误请私我。

     hashmap死循环出现的场景是两个线程同时对同一个hashmap进行了rehash操作导致。
     在理解其本质时首先得了解下hashmap的rehash流程:
     hashmap就是一个数组加链表的数据结构,等存储数据达到一定程度时就会生成一个新的更大的数据结构相同的hashmap,然后将其原有的数据存储到新的hashmap中。

   其重新存储过程:

       会先遍历hashmap数组元素中的某一条链,然后按照从尾到头的方式将链条中的值重新进行hash然后存储到新的hashmap中去。

       所以上图中原先的hashmap中,本来是5-》9,重新hash后就变成9-》5了。就是rehash时遍历顺序导致的。
而导致死循环的原因是:线程2 rehash后 链条变成了9-》5,这时线程一苏醒,它也开始进行rehash,然后遍历链条,这时就出现死循环了,因为9后面已经有5了(这个5是线程2加的),所以线程rehash时就会一直找不到链条的尾部,导致死循环了。
其中的关键是:hashmap虽然重新把链条上面的元素重新挪地方了,但是其内存地址是没变的。理解了这点就能理解了。