面試官：HashMap死循環形成的原因是什麼？

之前的文章已經分析了HashMap在JDK1.7的實現，這篇文章就只分析HashMap死循環形成的原因

死循環形成是在擴容轉移元素的時候發生的

<code>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);
}/<code>

發生的具體時機在transfer函數中，默認情況下rehash為false

<code>void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry e : table) {
        while(null != e) {
            Entry next = e.next;
            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;
        }
    }
}/<code>

正常的transfer過程

例子不考慮擴容閾值，假設放4個元素時開始擴容

主要有2個有意思的地方

原來在oldTable[i]位置的元素，會被放到newTable[i]或者newTable[i+oldTable.length]的位置鏈表在複製的時候會反轉併發下異常的transfer

假設線程1執行完Entry next = e.next後被掛起，此時e指向key3，next指向key7

void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length;

for (Entry e : table) { while(null != e) { Entry 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; } } }

線程2也來執行transfer函數，並執行完成，此時的狀態為 此時線程1接著執行餘下的代碼，將key3放到線程1的table[3]處 接著將e指向key7，不為null，再次進入循環，將next指向key3如下圖

當跑完這次循環時key7被放入線程1的table中，e指向key3，next指向null

e不為null，還能再次執行循環，key3再次插入線程1中table[3]的頭節點，此時e變為null,循環完畢。結構如下

環形鏈表形成，此時無論將線程1還是線程2的table設置為newTable，當調用get方法執行到這條鏈上時，死循環形成。

關注私信【555】獲取面試視頻，還可領取更多Java面試題資料

閱讀更多 來一杯82年的Java 的文章

關鍵字: 執行 線程 面試