面試中HashMap鏈表成環的問題你答出了嗎

HashMap作為老生常談的問題，備受面試官的青睞，甚至成為了面試必問的問題。由於大量的針對HashMap的解析橫空出世，面試官對HashMap的要求越來越高，就像面試官對JVM掌握要求越來越高一樣，今天我們來研究下HashMap的鏈表環化的問題，你知道其中的原理嘛？關注公眾號「程序員清辭」，獲取更多內容

在JDK1.7版本下，有個線程安全的問題，經常會被問到，很多求職者可能還在對比Hashtable線程安全性，其實面試官想得到的鏈表成環造成線程安全的問題，而這個問題在JDK1.8中已經得到了解決，但至於出現這樣問題的原因，我翻看了很多帖子，大家剖析的很透徹，但是很難理解，今天結合自己的研究利用一篇帖子來闡述其中的奧秘。

JDK1.7擴容源碼解析

首先我來了解下HashMap中經典的擴容代碼，回顧下擴容的過程

public class HashMap<K,V> extends AbstractMap<K,V> 
  implements Map<K,V>, Cloneable, Serializable { 
    
    //......
    
    // 擴容方法
    void resize(int newCapacity) {
        // 1、創建臨時變量，將HashMap數組數據賦值給新數組作臨時存儲
        Entry[] oldTable = table;
        // 2、判斷老數組長度是否超過了允許的最大長度，最大長度為 1 << 30
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        // 3、創建新的Entry數組，並擴容
        Entry[] newTable = new Entry[newCapacity];
        // 4、擴容賦值，即將老數組中的數據賦值到新數組中
        // initHashSeedAsNeeded(newCapacity) 得到的是一個hash的隨機值（哈希種子），
       //在計算哈希碼時會用到這個種子，作用是減少哈希碰撞
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        // 6、擴容後賦值
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    
    // newTable : 表示新數組，即擴容後創建的新數組
    // rehash ： 是否需要重新計算哈希值
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        // 5、將老map中的數據賦值到新map中（數組和鏈表複製遷移）
        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);
                }
                // 計算Entry元素在Entry[]數組中的位置
                int i = indexFor(e.hash, newCapacity);

                // 鏈表頭插法賦值過程
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }
    
    //......
    
}

創建臨時變量，將HashMap數組數據賦值給新數組作臨時存儲
判斷老數組長度是否超過了允許的最大長度，最大長度為 1 << 30
創建新的Entry數組，並擴容
擴容賦值，即將老數組中的數據賦值到新數組中
將老map中的數據賦值到新map中（數組和鏈表複製遷移）
擴容後賦值

鏈表遷移過程

以下三行代碼描述了鏈表頭插的整個過程，下面來剖析下這個過程：

e.next = newTable[i];
newTable[i] = e;
e = next;

關注公眾號「程序員清辭」，獲取更多內容

假設HashMap的存儲狀態如下：

關注公眾號「程序員清辭」，獲取更多內容

e為數組位置的元素，e1、e2為e下形成的鏈表，h為將要賦值的位置，箭頭代表鏈表指向

e.next = newTable[i]

對oldTable進行遍歷的過程中，取出元素e，假設先取出圖中的元素e，在執行這行代碼時，相當於斷開x位置e與e1的鏈表關係，並與newTable[i]建立鏈表關係，此時newTable[i]位置為null

newTable[i] = e

此時將oldTable中的e複製到newTable中的i位置，同時鏈表e指向null

問題：那oldTable中e1和e2形成的鏈表怎麼辦？

其實在之前的代碼中已經闡述了，詳情如下：

while(null != e) {

    // 這裡已經將e.next存儲為一個臨時變量，也就是e1和e2形成的鏈表
    Entry<K,V> next = e.next;
    if (rehash) {
        e.hash = null == e.key ? 0 :hash(e.key);
    }
    ......
}

e = next;

將next的值賦值給e，這行代碼對上述的鏈表沒有實質的影響，並且這已經是while循環的最後一行代碼了，這行代碼的目的是為下一次while遍歷過程能從e1元素開始，而不是e，因為此時需要的遍歷的e已經變成了e1。

通過這次數據遷移可能沒有得到比較有參考意義的分析，所以我們需要再進行一次遍歷分析，而這次遍歷分析從e1開始。這裡就不詳細闡述，直接上圖。

e.next = newTable[i]