欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JDK7 HashMap多线程扩容导致的死循环问题

程序员文章站 2022-04-03 15:59:01
JDK7HashMap多线程扩容导致的死循环问题前言源码多线程扩容前言JDK8以前的HashMap,多线程扩容的时候可能会出现死循环,这个问题在JDK8得到了修复。本翔看了大半天JDK7HashMap扩容源码找这个问题,所以写篇博客记录记录。源码先来看看JDK7的HashMap扩容相关源码。//扩容void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTa...

JDK7HashMap多线程扩容导致的死循环问题


前言

JDK8以前的HashMap,多线程扩容的时候可能会出现死循环,这个问题在JDK8得到了修复。本翔看了大半天JDK7HashMap扩容源码找这个问题,所以写篇博客记录记录。

源码

先来看看JDK7的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);
    }
    
    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);
                //下面这两步很明显了,头插法。即先拿到桶原本指向的节点,把要插入的节点的next指向它,然后再把桶指向这个要插入的节点
                e.next = newTable[i];
                newTable[i] = e;
                //next记录了旧数组旧链表里的下一个节点,现在把e指向它,准备下次循环把它插到新桶
                e = next;
            }
        }
    }

可以看到 transfer 方法用的是头插法,我们重点注意以下几个步骤:

1.Entry<K,V> next = e.next; next指向旧链表中的下一个节点
2.e.next = newTable[i]; 把新链表的头结点摘下来放到将要插入的节点的尾部
3.newTable[i] = e; 插入节点,即把桶指向e
4.e = next; 把e指向next,准备继续插入下一个节点

多线程扩容

单线程的情况下扩容,是没什么问题的,我们直接来一步步分析多线程扩容的时候会出现什么问题。

假如扩容前的数组和链表是这样的,数组里有2个桶,桶1里有三个节点,它们的键分别为3、7、5。

JDK7 HashMap多线程扩容导致的死循环问题

1 现在有两个线程同时扩容这个数组。假如线程一先拿到了cpu资源,执行完了 Entry<K,V> next = e.next; 这一步后,e指向3,next指向7。
这时CPU资源交给了线程二,好家伙,线程二啪啦啪啦啪啦一下子就把整个链表都迁移了过去,直接扩容完成。
这个时候旧数组、链表和两个线程的状态是这样的。
JDK7 HashMap多线程扩容导致的死循环问题

2 现在轮到线程一继续执行了。线程一一顿操作猛如虎,执行完第一次循环后,把3插了进去,然后把next赋给了e,还记得在线程二执行的时候,线程一的next是7吗?现在e指向的节点就是7,准备下一次循环插入7。第一次循环过后变成了这样:
JDK7 HashMap多线程扩容导致的死循环问题

3 下次循环一开始,Entry<K,V> next = e.next 直接把next指向3。问题不大,没毛病。现在继续执行下去,把7的next指向3,然后再把桶指向7,即用头插法插入了7。执行完第二次循环后如下图,现在问题已经差不多出来了,执行完此次循环后,e指向了3,但是3已经被插入了,继续执行下去会怎么样呢?
JDK7 HashMap多线程扩容导致的死循环问题

4 这次循环执行情况是这样的
Entry<K,V> next = e.next; 现在e是3,而3的next是null,所以next指向了null
e.next = newTable[i]; 这一步把3的next指向了7,因为桶现在是指向7的
newTable[i] = e; 把桶指向3
e = next; 由于next是null了,所以e指向了null,跳出了while进行后面的for循环
现在问题出来了,3的next指向了7,而7的next原本就指向3,情况如下图:
JDK7 HashMap多线程扩容导致的死循环问题

显而易见,环形链表出现,这个时候如果我们再去做一些查询,查到这个桶3上面来的话,遍历的时候就出现了死循环,直接出不去了,出大问题……
还好JDK8修复了这个死循环问题。

本文地址:https://blog.csdn.net/weixin_42101155/article/details/109695128

相关标签: Java