hashMap扩容时应该注意这些死循环问题
hashMap死循环
1.原因: jdk1.7时使用头插入法 ,1.8之后改成了尾插入法解决了这个问题
HashMap死循环问题图解
在HashMap的数组真实长度达到阈值后,会调用扩容方法:
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); }
这里可以看到如果有两个线程A和B,那么在调用transfer方法之前会在各自的线程中创建新的数组,然后进入到transfer方法中将节点转移,再看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; ------(1) 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; } } }
我在上面的程序中标记了一个(1),待会会用到,首先假设HashMap中的结构是这样的:
那么线程A如果执行到(1)的位置,那么e为节点5,next为节点6,这个时候线程B开始运行,在自己的扩容数组里面运行:
e.next = newTable[i]; newTable[i] = e;
这个时候结构图:
然后e=next;
在进入循环执行:
e.next = newTable[i]; newTable[i] = e;
这个时候结构为:
然后线程B执行完毕。线程A开始从(1)后面继续执行,这个时候也是先执行
e.next = newTable[i]; newTable[i] = e;
然后e=next;这个时候e是节点6,然后再进入循环,执行上面两行程序后的结构如下:
但是这个时候由于6的next是有值的,是节点5,所以再执行e=next;的时候,e不为空,还会进入一次循环,在执行将节点插入头部的操作,所以这个时候的结构图:
可以,看到已经成为了环状链表,当执行get操作的时候就会产生死循环。
到此这篇关于hashMap扩容时应该注意这些死循环问题的文章就介绍到这了,更多相关hashMap扩容内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
java中JSONObject转换为HashMap(方法+main方法调用实例)
这篇文章主要介绍了java中JSONObject转换为HashMap(方法+main方法调用实例),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-14- 这篇文章主要介绍了解决vue-router路由拦截造成死循环问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-05
- 这篇文章主要给大家介绍了关于如何检测JavaScript中死循环的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-08-31
- 今天给大家带来的是关于Java的相关知识,文章围绕着hashMap扩容时的死循环问题展开,文中有非常详细的介绍及代码示例,需要的朋友可以参考下...2021-06-10
- 本篇文章给大家带来的内容是关于Java中HashMap集合的常用方法详解,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。下面我们就来学习一下吧...2021-11-04
- Map用于保存具有映射关系的数据,Map集合里保存着两组值,一组用于保存Map的key,另一组保存着Map的value,和查字典类似,通过key找到对应的value,通过页数找到对应的信息。用学生类来说,key相当于学号,value对应name,age,sex等信息。用这种对应关系方便查找...2021-10-21
- 这篇文章主要介绍了在Unity中检测死循环和卡死的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-11-03
解析ConcurrentHashMap: 红黑树的代理类(TreeBin)
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment的结构和HashMap类似,是一种数组和链表结构,今天给大家普及java面试常见问题---ConcurrentHashMap知识,一起看看吧...2021-06-11- 这篇文章主要介绍了Java中HashMap里面key为null存放到哪,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04
Java中ConcurrentHashMap是如何实现线程安全
ConcurrentHashMap是一个哈希表,支持检索的全并发和更新的高预期并发。本文主要介绍了Java中ConcurrentHashMap是如何实现线程安全,感兴趣的可以了解一下...2021-11-03- HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。本文将深入探讨HashMap的结构实现和功能原理...2021-06-11
- 这几天学习了HashMap的底层实现,但是发现好几个版本的,代码不一,很多文章都是旧版本JDK1.6.JDK1.7的。现在我来分析下JDK7与JDK8中HashMap的实现过程...2021-09-18
- 这篇文章主要介绍了java中Hashmap的get方法使用,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-13
- 这篇文章主要介绍了Java中使用HashMap改进查找性能的步骤,帮助大家更好的理解和使用Java,感兴趣的朋友可以了解下...2021-02-07
- 这篇文章主要介绍了hashmap 的扩容和树形化的使用,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-11
Java面试题之HashMap 的 hash 方法原理是什么
那天,小二去蔚来面试,面试官老王一上来就问他:HashMap 的 hash 方法的原理是什么?当时就把裸面的小二给蚌埠住了,这篇文章将详细解答该题目...2021-11-05- 这篇文章主要介绍了谈谈Hashmap的容量为什么是2的幂次问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-09-24
Java多线程高并发中解决ArrayList与HashSet和HashMap不安全的方案
ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步,HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,关于HashSet有一件事应该牢记,即就条目数和容量之和来讲,迭代是线性的,接下来让我们详细来了解吧...2021-11-16- 这篇文章主要介绍了哈希表HashMap的深入学习,哈希表是一种非常重要的数据结构,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对java集合框架中HashMap的实现原理进行讲解。感兴趣的话可以一起来学习...2020-07-13
- 这篇文章是一篇java小白进阶篇本文教大家手写一个HashMap实现的示例代码,有需要的朋友可以借鉴参考下,希望对大家能够有所进益,祝大家早日升职加薪...2021-10-15