HashMap扩容死循环问题

今天药忘吃喽~ 2022-05-16 13:50 257阅读 0赞

### JDK 1.7 HashMap 扩容核心算法 ###

下面这是JDK 1.7中HashMap扩容时调用的核心代码，作用是将原hash桶中的节点转移到新的hash桶中：

void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

其中核心代码是下面这一段：

1 do {
    2     //保留要转移指针的下一个节点
    3     Entry<K,V> next = e.next;
    4     //计算出要转移节点在hash桶中的位置
    5     int i = indexFor(e.hash, newCapacity);
    6     //使用头插法将需要转移的节点插入到hash桶中原有的单链表中
    7     e.next = newTable[i];
    8     //将hash桶的指针指向单链表的头节点
    9     newTable[i] = e;
    10    //转移下一个需要转移的节点
    11    e = next;
    12 }  while (e != null);

下面我们来模拟一下多线程场景下扩容会出现的问题：

假设在扩容过程中旧hash桶中有一个单链表，单链表中只有一个节点A，也就是e引用的对象。新hash桶中有一个单链表，单链表中的节点是B->C，也就是newTable\[i\]引用的对象。

### 单线程扩容 ###

如果只有一个线程在执行扩容：  
\- 执行到第 3 行next = e.next的时候next == null  
\- 从第 5 行到第 9 行会将A节点按照头插法插入到newTable\[i\]所引用的单链表中，此时newTable\[i\]所引用的单链表中的节点是A->B->C  
\- 第 11 行e = next会将next赋值给e，所以e == null  
\- 这时候循环就结束了，整个扩容过程中毫无问题

### 多线程扩容 ###

如果是多个线程同时在扩容，我们以T1线程的扩容过程为主视角，T2和T3线程只是会在T1线程扩容过程中捣乱的：  
\- T1线程执行到第 7 行e.next = newTable\[i\]的时候会使得 e.next == B  
\- 此时T2线程过来捣乱了，执行到第 3 行next = e.next，那么会使得next == B，此时T2线程的使命结束了，下面不去考虑T2线程了  
\- T1线程执行到第 9 行newTable\[i\] = e的时候，使用头插法将A插入到newTable\[i\]所引用的单链表中，此时newTable\[i\]所引用的单链表中的节点是A->B->C  
\- T1线程继续执行到 11 行e = next，将使得e == B，由于e != null，所以循环将继续  
\- T1线程开启新的一轮循环，执行到第 3 行next = e.next的时候因为B.next == C，所以next == C  
\- 由于e == B，newTable\[i\] == A，当T1线程执行到第 7 行e.next = newTable\[i\]的时候，将导致A.next == B， B.next == A

当执行到这一步的时候，大家会发现好像看见了一个环，离真相越来越近了，下面我们两种情况来继续执行下去：

#### 没有T3线程介入，导致get请求死循环 ####

*  T1线程继续向下执行到第 11 行e = next，将使得e == C，将继续进行下一轮循环
 *  T1在这一轮新的循环中没有其他线程介入，这一轮执行完毕之后将跳出循环，而此时newTable\[i\]所引用的单链表会形成一个闭环  
    ![HashMap闭环][HashMap]
 *  这时候如果用户发送一个get(A)的请求，将导致get请求发生死循环

#### 有T3线程介入，导致T1线程扩容过程发生死循环 ####

*  当T1线程执行到第 7 行e.next = newTable\[i\]的时候会使得 e.next == A
 *  此时T3线程过来捣乱了，执行到第 3 行next = e.next，那么会使得next == A，此时T3线程的使命结束了，下面不去考虑T2线程了
 *  此时A.next == B， B.next == A， next == A，T1线程继续往下执行next指针会在A和B之间无线循环，导致T1扩容过程中发生死循环

### 扩容死循环代码示例 ###

import java.util.HashMap;
    import java.util.Map;
    import java.util.UUID;
    
    public class HashMapTest { 
    
        public static void main(String[] args) throws Exception {
            HashMap<String,String> map = new HashMap<String, String>();
            TestDeadLock t1 = new TestDeadLock(map);
            t1.start();
            TestDeadLock t2 = new TestDeadLock(map);
            t2.start();
            TestDeadLock t3 = new TestDeadLock(map);
            t3.start();
        }
    }
    
    class TestDeadLock extends Thread {
    
        private HashMap<String,String> map;
    
        public TestDeadLock(HashMap<String, String> map) {
            super();
            this.map = map;
        }
    
        @Override
        public void run() {
            for (int i = 0; i<500000; i++) {
                map.put(UUID.randomUUID().toString(), UUID.randomUUID().toString());
                System.out.println("Running ~~");
            }
        }
    }

main方法执行到一半后不会再打印”Running ~~”，并且方法不会执行结束，所以判断扩容过程造成死循环了。

### JDK 1.7 HashMap扩容导致死循环的主要原因 ###

HashMap扩容导致死循环的主要原因在于扩容后链表中的节点在新的hash桶使用头插法插入。

新的hash桶会倒置原hash桶中的单链表，那么在多个线程同时扩容的情况下就可能导致产生一个存在闭环的单链表，从而导致死循环。

### JDK 1.8 HashMap扩容不会造成死循环的原因 ###

在JDK 1.8中执行上面的**扩容死循环代码示例**就不会发生死循环，我们可以理解为在JDK 1.8 HashMap扩容不会造成死循环，但还是需要理论依据才有信服力。

首先通过上面的分析我们知道JDK 1.7中HashMap扩容发生死循环的主要原因在于扩容后链表倒置以及链表过长。

那么在JDK 1.8中HashMap扩容不会造成死循环的主要原因就从这两个角度去分析一下。

由于扩容是按两倍进行扩，即 N 扩为 N + N，因此就会存在低位部分 0 - (N-1)，以及高位部分 N - (2N-1)， 所以在扩容时分为 loHead (low Head) 和 hiHead (high head)。

然后将原hash桶中单链表上的节点按照尾插法插入到loHead和hiHead所引用的单链表中。

由于使用的是尾插法，不会导致单链表的倒置，所以扩容的时候不会导致死循环。

通过上面的分析，不难发现循环的产生是因为新链表的顺序跟旧的链表是完全相反的，所以只要保证建新链时还是按照原来的顺序的话就不会产生循环。