多图详解的HashMap1.7扩容死循环

2021年9月16日 43点热度 0条评论 来源: SIDOS007

1.7HashMap扩容过程详解

一、1.7HashMap扩容死循环

1.效果展示

1.7HashMap在高并发场景下,会发生扩容链表死循环问题!并非必然现象,这里需要先使用代码(多试试),查看下效果!

图形已开放出来,免费copy!地址如下:
多线程下1.7HashMap扩容图例

package com.woniuxy.testforHashMap;

import java.util.HashMap;

/** * Auther: mayuhang <br/> * Date: 2020/7/23:17:04 <br/> * Description:1.7扩容死循环测试 */
public class TestForHashMap { 
    static HashMap<Object, Object> map = new HashMap<>(2);
    public static void main(String[] args) throws InterruptedException { 
        for (int i = 0; i < 1000; i++) { 
            new Thread() { 
                @Override
                public void run() { 
                    for (int j = 0; j < 100; j++) { 
                       map.put(j, j);
                    }
                }
            }.start();
            for (int j = 0; j <1000 ; j++) { 
                new Thread() { 
                    @Override
                    public void run() { 
                        for (int j = 0; j < 100; j++) { 
                            map.put(j, j);
                        }
                    }
                }.start();
            }
        }
    }
}

2、源码分析

首先,分析是由于插入方法导致的!然后明白插入后,会出现扩容重排!此刻,为了节省分析时间,直接展示扩容链表重排的代码块!

 /** * Transfers all entries from current table to newTable. */
    void transfer(Entry[] newTable, boolean rehash) { 
    	//新数组长度
        int newCapacity = newTable.length;
        //table为旧表,此处为遍历Hash表,落在桶上的所有节点!也就是链表头结点!
        for (Entry<K,V> e : table) { 
            while(null != e) { 
                Entry<K,V> next = e.next;//此处为多线程下,发生问题的点!非常重要,切记!
                if (rehash) { //重新进行Hash计算,这个if方法不用管!
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);//重新计算这个节点放在新newTable表的位子!
                //这3段代码, 通过下面的图来解释!
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

3、原因图例分析

3.1 单线程下复制过程!

如果这个能看懂,那么,多线程下扩容也能理解了!不过,请忽略扩容长度问题(不管1.7还是1.8长度不管合不合理,太长了不好画……)

	首先第一步:我们只关注这while中的代码,同时进行简化理解
while(null != e) { //直接找到对应的下标3的元素e
      Entry<K,V> next = e.next;//此处为多线程下,发生问题的点!非常重要,切记!
      //省略中间重新Hash,与计算下标的代码;
      //假设,下标最后计算结果为7则:
      int i=7;
      //这3段代码, 通过下面的图来解释!
      e.next = newTable[i];
      newTable[i] = e;
      e = next;
}
	然后第二步: 看这个图解


接着第三步: 执行代码!
因为for循环遍历,所以链表头就是变量e;同时执行Entry<K,V> next = e.next; 图形为:

第四步: 头插法,新表对应下标指向头部key=3的entry对象地址!
第一: e.next = newTable[7]; 第二: newTable[7] = e; 第三 : e = next; 则e对象赋值为7 entry!

最后一步:
Entry<K,V> next = e.next; next则为null!
e.next = newTable[i]; 则 e.next=key(3);

第一步: newTable[i] = e;
第二步: e = next;

至此,单线程下的扩容过程结束!

3.2 多线程下复制过程!

其中,一个线程A,停在这里,CPU调度执行其他线程!

图解如下图: A线程停下后,对应的entry元素如下图!

此时,A停,B线程重头开始执行,完成完成的单线程扩容过程!实现新数组的扩容重排!

新数组来源截图:

此时A线程开始执行:此时,entry节点属性已经发生了变化!

此时,节点之间的指针已经发生了变化,但是赋值的变量next和e都未改变,如下图:

此时:A线程重新获得CPU调度,继续执行!代码复制过来:

while(null != e) { 
      Entry<K,V> next = e.next;//A线程 继续往下执行!
      //省略中间重新Hash,与计算下标的代码;
      //假设,下标最后计算结果为7则:
      int i=7;
      //这3段代码, 通过下面的图来解释!
      e.next = newTable[i];
      newTable[i] = e;
      e = next;
}

此时:执行到这个地方,图解送上:
第一步: e.next = newTable[i];
第二步: newTable[i] = e;
第三步: e = next;

最后:
重回去while循环,进入那最重要的一步操作:

Entry<K,V> next = e.next;//此处为多线程下,发生问题的点!非常重要,切记!


此时,已经看出了问题出现了,next变量,又指回了3 entry节点;
继续执行:到这个地方,图解送上:
第一步: e.next = newTable[i];
第二步: newTable[i] = e;
第三步: e = next;

此刻,是不是很奇怪,好像没得问题啊,虽然第一步执行前后状态都没有实际变化,但是,重要的是next变量的指针,依然指向了我们的3 entry节点!也就是说,我们的e=next后,e非空!循环还要继续!
此刻,继续循环,依然是这些步骤!

Entry<K,V> next = e.next;//此处为多线程下,发生问题的点!非常重要,切记!

这段代码后next 指向了 null;

接着,继续执行:到这个地方,图解送上:
第一步: e.next = newTable[i]; // 这一步 操作后, 惊喜出现了(假设正好又一次 i=7 !! 这个是前提)
第二步: newTable[i] = e;
第三步: e = next;

第一步操作后,如下图!!!

此刻, 死循环出现了!!
第二步: newTable[i] = e;
第三步: e = next;
继续执行后, 如图:

此时, e已经为null while循环结束!死循环已经发生!但是此次的扩容过程结束!!

结论:

死循环已经出现了,但是本次扩容过程完美结束!那,啥时候会发生真正的死循环调用呢?
网上很多文章都是说最后再get的时候,会发生死循环,此时,请回忆最上面我展示效果的代码,并未使用get!只是单纯的put!
也就是说,环形链表形成后,并非get才会出现问题!
那也就是说,单纯多线程下,会在形成环形链表之后,再次发生了什么,导致死循环!
那么,请问各位读者,现在环形链表出现了,而造成我们真正出现死循环的代码片段在哪里呢?请不要考虑get的情况!

    原文作者:SIDOS007
    原文地址: https://blog.csdn.net/u011433316/article/details/107403427
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。