HashMap多线程下发生死循环的原因

HashMap多线程下发生死循环的原因

大家好,又见面了,我是全栈君。

概述


大神陈皓已经在疫苗: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请求,就有可能发生死循环,一直在链表中绕来绕去的,没法终止。


原文链接


HashMap多线程下发生死循环的原因

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108167.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ucosii操作系统内核源码学习第一篇

    ucosii操作系统内核源码学习第一篇待会就开始学习

  • windows7添�windows2008R2域配置

    windows7添�windows2008R2域配置

    2021年11月15日
  • android之View和ViewGroup介绍

    资源描述: Activity(活动)中包含views(视图)和ViewGroups(视图组)。“视图”(View)就是显示在屏幕上的一个组件(Widget)。View的例子:按钮(Button)、标签(TextView)和文本框(EditText)。每个“视图”(View)都继承自基类android.view.View。“视图组”(ViewGroup)可以包含一个或多个

  • mongodb 唯一索引 性能_什么是唯一索引

    mongodb 唯一索引 性能_什么是唯一索引MongoDB支持的索引种类很多,诸如单键索引,复合索引,多键索引,TTL索引,文本索引,空间地理索引等。同时索引的属性可以具有唯一性,即唯一索引。唯一索引用于确保索引字段不存储重复的值,即强制索引字段的唯一性。缺省情况下,MongoDB的_id字段在创建集合的时候会自动创建一个唯一索引。本文主要描述唯一索引的用法。

  • context和getApplicationContext()介绍

    在android中常常会遇到与context有关的内容浅论一下context : 在语句 AlertDialog.Builder builder = new AlertDialog.Builder(this); 中,要求传递的 参数就是一个context,在这里我们传入的是this,那么这个this究竟指的是什么呢? 这里的this指的是Activity.this,是这个语句所在的Acti

  • 主、外键约束_创建主键约束

    主、外键约束_创建主键约束主、外键约束点关注不迷路,欢迎再来!主键和外键是两种类型的约束;1.主键是能唯一的标识表中的每一行,就是说这一列非空且值不重复,可以指定为主键;作用是用来强制约束表中的每一行数据的唯一性;2.外键是b表中的某一列引用的值来源于a表中的主键列。也是约束b表中的外键列的值必须取致a表中的主键列值,不是其中的值就不能插入b表中。可以形成a表b表的联系,保持数据的约束和关联性。创建主表主键…

    2022年10月20日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号