HashMap死循环精简说

在JDK1.8之前的版本中,HashMap的底层实现是数组+链表。当调用HashMap的put方法添加元素时,如果新元素的hash值或key在原Map中不存在,会检查容量size有没有超过设定的threshold,如果超过则需要进行扩容,扩容的容量是原数组的两倍,具体代码如下:

void addEntry(int hash, K key, V value, int bucketIndex) { //检查容量是否超过threshold if ((size >= threshold) && (null != table[bucketIndex])) { //扩容 resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }

扩容就是新建Entry数组,并将原Map中元素重新计算hash值,然后存到新数组中,具体代码如下:

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //新数组 Entry[] newTable = new Entry[newCapacity]; //原数组元素转存到新数组中 transfer(newTable, initHashSeedAsNeeded(newCapacity)); //指向新数组 table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } 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]; newTable[i] = e; e = next; } } }

假设一个HashMap的初始容量是4,使用默认负载因子0.75,有三个元素通过Hash算法计算出的数组下标都是2,但是key值都不同,分别是a1、a2、a3,HashMap内部存储如下图:

假设插入的第四个元素a4,通过Hash算法计算出的数组下标也是2,当插入时则需要扩容,此时有两个线程T1、T2同时插入a4,则T1、T2同时进行扩容操作,它们各自新建了一个Entry数组newTable。

T2线程执行到transfer方法的Entry<K,V> next = e.next;时被挂起,T1线程执行transfer方法后Entry数组如下图:

在T1线程没返回新建Entry数组之前,T2线程恢复,因为在T2挂起时,变量e指向的是a1,变量next指向的是a2,所以在T2恢复执行完transfer之后,Entry数组如下图:

可以看到在T2执行完transfer方法后,a1元素和a2元素形成了循环引用,此时无论将T1的Entry数组还是T2的Entry数组返回作为扩容后的新数组,都会存在这个环形链表,当调用get方法获取该位置的元素时就会发生死循环,更严重会导致CPU占用100%故障。

为了更方便的技术交流,建了一个微信群,加博主微信wind7rui,盛邀你进群!

END

本文分享自微信公众号 - JavaQ(Java-Q)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专注 Java 基础分享

深入理解Java常用类-----时间日期

     除了String这个类在日常的项目中比较常用之外,有关时间和日期的操作也是经常遇到的,本篇就讲详细介绍下Java API中对时间和日期的支持。其实在J...

28380
来自专栏Java3y

TreeMap就这么简单【源码剖析】

25250
来自专栏aCloudDeveloper

百炼OJ 2972 2973

一、2972相邻数字的基数等比:确定进制      所谓基数等比就是后一个数与前一个数有倍数的关系。如 111 = 1 + 1 * 2(1 + 2 * 1); ...

25280
来自专栏算法channel

二叉树非递归版的后序遍历算法

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

441100
来自专栏算法channel

二叉树非递归版的中序遍历算法

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

36250
来自专栏C语言及其他语言

【编程经验】关于链表、还有编译器

关注我们 最近有小白来问VC6.0和其他编译器怎么下,小编回了一些,但是也是确实比较多......所以今天就不单单分享知识了,还要分享资源! ...

307100
来自专栏JavaEdge

Java8集合源码解析-Hashtable源码剖析1 概述2 源码解析rehash方法3 总结

30160
来自专栏老付的网络博客

Java中的容器

在Java中有常用的三种类型的容器,分别是List 、Map、Set,基于这个三个基本的类型,派生出很多其它的类型,具体关系如下:

50120
来自专栏Android机动车

Java 基础(五)——集合源码解析 Set

前面我们学了 List 集合。我们知道 List 是一个有序的集合,可以根据元素的整数索引访问元素,并且允许重复。

11110
来自专栏冷冷

ArrayList foreach 循环里进行元素的 remove add 操作有什么现象?

先来看看《阿里巴巴Java开发手册》中的一段 【强制】不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Itera...

32780

扫码关注云+社区

领取腾讯云代金券