大家好,又见面了,我是全栈君。
概述
大神陈皓已经在疫苗:JAVA HASHMAP的死循环一文中详细描述了HashMap
多线程下产生死循环的原因,我仔细研读了这篇大作,做了一些笔记,加上自己的一些理解
整理出一些信息,发出来与大家交流交流。
HashMap存储的数据结构
陈皓在Hash表数据结构这一节提到了HashMap
的数据结构以及扩容问题,关于这一点我之前写过的
HashMap的put和get方法原理和HashMap扩容已经有详细的描述了。
多线程rehash的时候如何造成闭环链表
rehash源代码
正常的rehash过程
数据准备
在size=2的HashMap
中按照顺序添加5, 7, 3这三个key,假设按照mod 2的算法来计算元素数组下标,那么key 5,7,3都会落在下标为1的数组桶中(发生hash冲突),如下图:
把HashMap的size扩容为4后,rehash的过程
注意,发生hash冲突的5,7,3虽然都是在同一个链表中,但是每个元素都得走rehash的过程,因为
HashMap
扩容后,这几个元素就未必都是在同一个链表中了
1、第一个是处理3这个key,先把key为3这个元素的next设置为空,并计算它在新数组中的下标,并存到新下标对应桶中,如下图:
2、第二个是处理7这个key,按照上面的约定,在新数组中3和7这个两个key还是发生了hash冲突,那么按照HashMap
发生冲突的处理代码,链表的第一个元素存储的是最新插入的7,然后next指向3,如下图:
3、第三个是处理5这个key,如下图:
到这里一次正常rehash过程走完了,最后三个key的存储情况如下图:
并发下的rehash过程
当两个并发线程thread1和thread2都同时进入到transfer时,也即是,刚好thread1和thread2都要对HashMap
进行扩容,万一这个时候thread1执行下面的代码时,被线程调度器挂起了,而thread2则正常的把扩容的操作做完,如下图:
那这个时候,容器的数据存储情况如下:
对于thread1
对于thread2
这个时候,thread1拥有执行权限了,则继续它的扩容操作,等thread1扩容完后就产生了一个环形链表了(注意这里省略了一些步骤,不太明白的,则可以看我之前写的HashMap的put和get方法原理和HashMap扩容)
这个时候,如果有个get请求,就有可能发生死循环,一直在链表中绕来绕去的,没法终止。
原文链接
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108167.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...