jdk1.7的hashmap为什么会出现死循环问题

原因在于链表结构出现了环状。为什么会出现环状的链表?

  • 原因在于多个线程同时进行扩容的时候。

  • 由于一个线程使用的是头插法进行迁移数据到新开辟的数组中,使得链表中的数据是颠倒的顺序。

  • 而当另一个线程扩容的时候就可能因为这个颠倒的顺序而出现指针指回前面结点的情况。

  • 也就是形成一个循环链表。

以下是详细解释:

当hashmap执行put方法时,我们知道,首先算出这个元素的hash值,然后算出这个元素在数组中的下标值。如果数组的这个下标位置中有元素且判断出这个元素的key与待插入的元素key相等,那么用新元素的value值替换,结束。而对于 情况①数组中这个下标位置为空,情况②头插法插入到链表中,都进入以下这个新增元素的方法:

void addEntry(int hash, K key, V value, int bucketIndex) {// 当数组的size >= 扩容阈值,且数组下标位置不为空,则触发扩容。size大小会在createEnty和removeEntry的时候改变if ((size >= threshold) && (null != table[bucketIndex])) {// 扩容到2倍大小,后边会跟进这个方法resize(2 * table.length);// 扩容后重新计算hash和indexhash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}// 创建一个新的链表节点,点进去可以了解到是将新节点添加到了链表的头部createEntry(hash, key, value, bucketIndex);
}

扩容方法:

 void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}// 创建2倍大小的新数组Entry[] newTable = new Entry[newCapacity];// 将旧数组的链表转移到新数组,就是这个方法导致的hashMap不安全,等下我们进去看一眼transfer(newTable, initHashSeedAsNeeded(newCapacity));table = newTable;// 重新计算扩容阈值(容量*加载因子)threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

出问题的就是这个transfer方法:

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;// 遍历旧数组for (Entry<K,V> e : table) {// 遍历链表while(null != e) {//获取下一个元素,记录到一个临时变量,以便后面使用Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}// 计算节点在新数组中的下标int i = indexFor(e.hash, newCapacity);// 将旧节点插入到新节点的头部e.next = newTable[i];//这行才是真正把数据插入新数组中,前面那行代码只是设置当前节点的next//这两行代码决定了倒序插入//比如:以前同一个位置上是:3,7,后面可能变成了:7、3newTable[i] = e;//将下一个元素赋值给当前元素,以便遍历下一个元素e = next;  }  }
}

比如说即将进入扩容的数组长这样:

线程1、2此时都进入了transfer方法中的Entry<K,V> next = e.next;

需要注意的是线程1和线程2的e都指向了key:3这个元素,e.next都指向了key:7这个元素。无论后续哪个线程进行扩容,元素地址还都是不变的。

假设现在线程1挂起,线程2接着执行transfer方法剩余的逻辑,得到如下新扩容后的数组,因为是头插法,导致7和3的位置颠倒了。

接着线程1被唤醒,开始执行。

线程1自己也开了个扩容后的新数组,但是头插法插入元素仍然是用的上图元素的地址。

我们根据以下代码演示一下线程1扩容时插入元素的过程:

//next= 7   e = 3  e.next = 7
//遍历链表
while(null != e) {Entry<K,V> next = e.next;int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;
}

 

所以问题就出在了:如果线程2创建的数据没有颠倒的话,就不会有7的next是3,从而形成一个闭环。

因为我们如果改用尾插法就可以解决这个问题。

参考:

java - 11张图让你彻底明白jdk1.7 hashmap的死循环是如何产生的 - 个人文章 - SegmentFault 思否

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/16906.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

微信小程序navigateTo:fail webview count limit exceed

theme: nico 你们好&#xff0c;我是金金金。 场景 uniapp编写微信小程序&#xff0c;使用uni.navigateTo跳转的过程中报错如下&#xff1a; 报错意思也非常明显了&#xff1a;errMsg":"navigateTo:fail webview 数量超出限制 排查 排查之前我先贴一下代码 代码非…

逆向攻防世界CTF系列33-流浪者

逆向攻防世界CTF系列33-流浪者 shiftf12看到pass&#xff0c;跟进 是个输入的处理&#xff0c;其实很简单&#xff0c;看不懂也没关系&#xff0c;先看看return 这里strcmp成功后return的就是成功 最后要为KanXueCTF2019JustForhappy while ( *(_DWORD *)(a1 4 * v4) < 0x…

算法--解决二叉树遍历问题

第一 实现树的结构 class Node(): # 构造函数&#xff0c;初始化节点对象&#xff0c;包含数据和左右子节点 def __init__(self, dataNone): self.data data # 节点存储的数据 self.left None # 左子节点&#xff0c;默认为None self.rig…

Ubuntu22.04.2 k8s部署

k8s介绍 简单介绍 通俗易懂的解释&#xff1a; Kubernetes&#xff08;也被称为 K8s&#xff09;就像是一个大管家&#xff0c;帮你管理你的云计算服务。想象一下&#xff0c;你有很多个小程序&#xff08;我们称之为“容器”&#xff09;&#xff0c;每个都在做不同的事情&…

游戏引擎学习第12天

视频参考:https://www.bilibili.com/video/BV1yom9YnEWY 这节没讲什么东西&#xff0c;主要是改了一下音频的代码 后面有介绍一些alloc 和malloc,VirtualAlloc 的东西 _alloca 函数&#xff08;或 alloca&#xff09;分配的是栈内存&#xff0c;它的特点是&#xff1a; 生命周…

Linux-软件管理-本地仓库和网络资源仓库配置(RHCSA)

该章节的目录如下&#xff1a; 认识rpm包 将设备挂载到/mnt上面 查看光驱上的相关信息 使用rpm包管理软件 仓库的配置(重要) 无相关文件 本地仓库配置&#xff08;书写相关的仓库文件&#xff09; 配置流程 效果测试&#xff08;安装卸载&#xff09; 查看仓库 清理…

【arxiv‘24】Vision-Language Navigation with Continual Learning

论文信息 题目&#xff1a;Vision-Language Navigation with Continual Learning 视觉-语言导航与持续学习 作者&#xff1a;Zhiyuan Li, Yanfeng Lv, Ziqin Tu, Di Shang, Hong Qiao 论文创新点 VLNCL范式&#xff1a;这是一个新颖的框架&#xff0c;它使得智能体能够在适…

数字化建设:指标如何驱动的企业KPI设计?

我们以KPI设定为例&#xff0c;简单说明在一套科学的经营分析体系的加持下&#xff0c;企业的经营KPI应该如何设定&#xff0c;如图所示。 指标驱动的企业KPI设计 每年年初企业做战略规划的同时&#xff0c;会启动年度业务KPI的设定。这个时候经营分析团队会主导整个过程。首先…

初级数据结构——栈题库(c++)

目录 前言1.杭电oj——Bitset2.杭电oj——进制转换[3.力扣——LCR 123. 图书整理 I](https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/description/)[4.力扣——LCR 027. 回文链表](https://leetcode.cn/problems/aMhZSa/)[5.力扣——1614. 括号的最大嵌…

数字化转型企业架构设计手册(交付版),企业数字化转型建设思路、本质、数字化架构、数字化规划蓝图(PPT原件获取)

1、企业架构现状分析 2、企业架构内容框架 3、企业架构设计方法 3.1 、业务架构设计方法 3.2 、数据架构设计方法 3.3 、应用架构设计方法 3.4 、技术架构设计方法 软件全套资料部分文档清单&#xff1a; 工作安排任务书&#xff0c;可行性分析报告&#xff0c;立项申请审批表&…

⾃动化运维利器Ansible-基础

Ansible基础 一、工作原理二、快速入门2.1 测试所有资产的网络连通性2.2 发布文件到被管理节点(资产) 三、资产(被管理节点)3.1 静态资产3.1.1 自定义资产3.1.2 自定义资产的使用3.1.3 资产选择器 四、Ansible Ad-Hoc 命令4.1 模块类型4.1.1 command & shell 模块4.1.2 cop…

鸿蒙NEXT自定义组件:太极Loading

【引言】&#xff08;完整代码在最后面&#xff09; 本文将介绍如何在鸿蒙NEXT中创建一个自定义的“太极Loading”组件&#xff0c;为你的应用增添独特的视觉效果。 【环境准备】 电脑系统&#xff1a;windows 10 开发工具&#xff1a;DevEco Studio NEXT Beta1 Build Vers…

AVL树了解并简单实现

这篇文章默认知道二叉搜索树&#xff0c;如果了解并不多可以先看看二叉搜索树了解和实现-CSDN博客 目录 1.AVL树概念 2.AVL树节点定义 3.AVL树的插入&#xff08;重点&#xff09; 3.1AVL树 3.2AVL树的旋转 3.3AVL树插入代码 4.AVL树的验证 5.AVL树的删除 6.AVL树的性能…

【MySQL】索引原理及操作

目录 索引原理 初识索引 磁盘原理 磁盘与系统之间的关系 MySQL、系统、磁盘之间的关系 理解索引 页目录 页目录设计的数据结构问题 聚簇索引与非聚簇索引 遗留问题 索引操作 创建索引 查询索引 删除索引 其他索引概念与操作 索引原理 索引&#xff08;I…

代码随想录算法训练营第三十一天| 56. 合并区间 、738.单调递增的数字 。c++转java

56. 合并区间 class Solution {public int[][] merge(int[][] intervals) {//对区间按照右边界排序Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));List<int[]> p new LinkedList<>();int l intervals[0][0],r intervals[0][1];for(int i 1;i…

厦大南洋理工最新开源,一种面向户外场景的特征-几何一致性无监督点云配准方法

导读 本文提出了INTEGER&#xff0c;一种面向户外点云数据的无监督配准方法&#xff0c;通过整合高层上下文和低层几何特征信息来生成更可靠的伪标签。该方法基于教师-学生框架&#xff0c;创新性地引入特征-几何一致性挖掘&#xff08;FGCM&#xff09;模块以提高伪标签的准确…

模型运行速度笔记: s/epoch VS s/iter

1 概念介绍 在模型训练中&#xff1a; s/epoch 表示每个epoch所需的秒数&#xff0c;即完成一轮完整数据集训练的时间。s/iter 表示每个iteration&#xff08;迭代&#xff09;所需的秒数&#xff0c;即处理一个batch的时间。 它们的关系是&#xff1a; 2 举例 比如我tra…

k8s 中传递参数给docker容器

文章目录 docker启动时传递参数使用k8s env传递完全覆盖 ENTRYPOINT 和 CMD 在 Kubernetes 中&#xff0c;可以通过多种方式将参数传递给 Dockerfile 或其运行的容器&#xff0c;常见的方式包括使用环境变量、命令行参数、配置文件等。以下是一些常用的方法&#xff1a; docker…

Map Set

在学习TreeMap和TreeSet之前需要先学习有关搜索树的相关知识以及接口Map和Set。 1. 搜索树 1.1 概念 二叉搜索树又称二叉排序树&#xff0c;其特点是&#xff0c;该节点的左边都比其小&#xff0c;右边都比其大&#xff0c;每一棵子树都必须满足这个条件。如下图所示例子。2…

Android OpenGLES2.0开发(八):Camera预览

严以律己&#xff0c;宽以待人 引言 终于到该章节了&#xff0c;还记得Android OpenGLES2.0开发&#xff08;一&#xff09;&#xff1a;艰难的开始章节说的吗&#xff1f;写这个系列的初衷就是因为每次用到GLSurfaceViewCamera预览时&#xff0c;总是CtrlC、CtrlV从来没有研究…