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扩容内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-06-09

深入了解JAVA HASHMAP的死循环

前言 在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环.这个事情我4.5年前也经历过,本来觉得没什么好写的,因为Java的HashMap是非线程安全的,所以在并发下必然出现问题.但是,我发现近几年,很多人都经历过这个事(在网上查"HashMap Infinite Loop"可以看到很多人都在说这个事)所以,觉得这个是个普遍问题,需要写篇疫苗文章说一下这

JDK1.8中ConcurrentHashMap中computeIfAbsent死循环bug问题

死循环问题的提出:https://bugs.openjdk.java.net/browse/JDK-8062841 map.computeIfAbsent("AaAa",key->map.computeIfAbsent("BBBB",key2->42)); computeIfAbsent在1.8中才有的方法 computeIfAbsent意思是:key不存在时候,调用mappingFunction函数结果作为value值 debug 两个key的hash

为什么JDK8中HashMap依然会死循环

JDK8中HashMap依然会死循环! 是否你听说过JDK8之后HashMap已经解决的扩容死循环的问题,虽然HashMap依然说线程不安全,但是不会造成服务器load飙升的问题. 然而事实并非如此.少年可曾了解一种红黑树成环的场景,=v= 今日在查看监控时候发现,某一台机器load飙升 感觉问题不对劲,ssh大法登陆机器,top,top -Hp,jstack,jmap四连击保存下来堆栈,cpu使用最高的线程,内存信息准备分析. 首先查看使用最耗费cpu的线程堆栈信息 cat stack | g

关于HashMap 并发时会引起死循环的问题解析

今天研读Java并发容器和框架时,看到为什么要使用ConcurrentHashMap时,其中有一个原因是:线程不安全的HashMap, HashMap在并发执行put操作时会引起死循环,是因为多线程会导致HashMap的Entry链表形成环形数据结构,查找时会陷入死循环. 纠起原因看了其他的博客,都比较抽象,所以这里以图形的方式展示一下,希望支持! 1)当往HashMap中添加元素时,会引起HashMap容器的扩容,原理不再解释,直接附源代码,如下: /** * * 往表中添加元素,如果插入元素

基于Java HashMap的死循环的启示详解

一.单线程改造为多线程也是个技术活 正如我们看到耗子叔叔博客里写的那样,原来是单线程的应用程序,"后来,我们的程序性能有问题,所以需要变成多线程的,于是,变成多线程后到了线上,发现程序经常占了100%的CPU". 考虑到是淘宝的工程师曝出来的问题,他们的技术基础一般都很扎实,连他们都用错了,所以把单线程改造为多线程并不是想象中的那么简单,我认为. 你可能很不服气地反问,淘宝的工程师又怎么了,单线程改为多线程有什么难的?无非就是应用现有的多线程技术嘛,你看,我有非常强烈的线程安全意识,我

基于Java中的数值和集合详解

数组array和集合的区别: (1) 数值是大小固定的,同一数组只能存放一样的数据. (2) java集合可以存放不固定的一组数据 (3) 若程序事不知道究竟需要多少对象,需要在空间不足时自动扩增容量,则需要使用容器类库,array不适用 数组转换为集合: Arrays.asList(数组) 示例: int[] arr = {1,3,4,6,6}; Arrays.asList(arr); for(int i=0;i<arr.length;i++){ System.out.println(arr[

基于java涉及父子类的异常详解

java中的异常涉及到父子类的问题,可以归纳为一句话:子类的构造函数抛出的异常必须包含父类的异常,子类的方法可以选择抛出"范围小于等于"父类的异常或不抛出异常. 1. 为什么构造函数必须抛出包含父类的异常? 在<thingking in java>中有这么一段话: 异常限制:当覆盖方法时,只能抛出在基类方法的异常说明中列出的那些异常 异常限制对构造器不起作用,你会发现StormyInning的构造器可以抛出任何异常,而不必理会基类构造函数所抛出的异常.然而因为必须构造函数必

classloader类加载器_基于java类的加载方式详解

基础概念 Classloader 类加载器,用来加载 Java 类到 Java 虚拟机中.与普通程序不同的是.Java程序(class文件)并不是本地的可执行程序.当运行Java程序时,首先运行JVM(Java虚拟机),然后再把Java class加载到JVM里头运行,负责加载Java class的这部分就叫做Class Loader. JVM本身包含了一个ClassLoader称为Bootstrap ClassLoader,和JVM一样,BootstrapClassLoader是用本地代码实现

java HashMap,TreeMap与LinkedHashMap的详解

 java HashMap,TreeMap与LinkedHashMap的详解 今天上午面试的时候 问到了Java,Map相关的事情,我记错了HashMap和TreeMap相关的内容,回来赶紧尝试了几个demo理解下 package Map; import java.util.*; public class HashMaps { public static void main(String[] args) { Map map = new HashMap(); map.put("a", &

基于java 线程的几种状态(详解)

线程可以有六种状态: 1.New(新创建) 2.Runnable(可运行)(运行) 3.Blocked(被阻塞) 4.Waiting(等待) 5.Timed waiting(计时等待) 6.Terminated(被终止) 新创建线程: 当用new操作符创建一个新线程时,如new Thread(r),该线程还没有开始运行,它的当前状态为new,在线程运行之前还有一些基础工作要做. 可运行线程: 一旦线程调用start方法,线程处于runnable状态.在这个状态下的线程可能正在运行也可能没有运行(

基于Java回顾之JDBC的使用详解

尽管在实际开发过程中,我们一般使用ORM框架来代替传统的JDBC,例如Hibernate或者iBatis,但JDBC是Java用来实现数据访问的基础,掌握它对于我们理解Java的数据操作流程很有帮助. JDBC的全称是Java Database Connectivity. JDBC对数据库进行操作的流程:•连接数据库•发送数据请求,即传统的CRUD指令•返回操作结果集JDBC中常用的对象包括:•ConnectionManager•Connection•Statement•CallableStat

java HashMap和HashTable的区别详解

HashMap和HashTable,这二者的区别经常被别人问起,今天在此总结一下. (一)继承的历史不同 public class Hashtable extends Dictionary implements Map public class HashMap extends AbstractMap implements Map Hashtable是继承自Dictionary类的,而HashMap则是Java 1.2引进的Map接口的一个实现. (二)安全性不同 HashMap是非synchro

基于Java内存溢出的解决方法详解

一.内存溢出类型1.java.lang.OutOfMemoryError: PermGen spaceJVM管理两种类型的内存,堆和非堆.堆是给开发人员用的上面说的就是,是在JVM启动时创建:非堆是留给JVM自己用的,用来存放类的信息的.它和堆不同,运行期内GC不会释放空间.如果web app用了大量的第三方jar或者应用有太多的class文件而恰好MaxPermSize设置较小,超出了也会导致这块内存的占用过多造成溢出,或者tomcat热部署时侯不会清理前面加载的环境,只会将context更改

基于Java 注解(Annotation)的基本概念详解

什么是注解(Annotation): Annotation(注解)就是Java提供了一种元程序中的元素关联任何信息和着任何元数据(metadata)的途径和方法.Annotion(注解)是一个接口,程序可以通过反射来获取指定程序元素的Annotion对象,然后通过Annotion对象来获取注解里面的元数据. Annotation(注解)是JDK5.0及以后版本引入的.它可以用于创建文档,跟踪代码中的依赖性,甚至执行基本编译时检查.从某些方面看,annotation就像修饰符一样被使用,并应用于包