hashMap擴容時應該註意這些死循環問題

hashMap死循環

1.原因: jdk1.7時使用頭插入法 ,1.8之後改成瞭尾插入法解決瞭這個問題

HashMap死循環問題圖解

在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);
    }

這裡可以看到如果有兩個線程A和B,那麼在調用transfer方法之前會在各自的線程中創建新的數組,然後進入到transfer方法中將節點轉移,再看transfer方法:

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;   ------(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;
            }
        }
    }

我在上面的程序中標記瞭一個(1),待會會用到,首先假設HashMap中的結構是這樣的:

  

那麼線程A如果執行到(1)的位置,那麼e為節點5,next為節點6,這個時候線程B開始運行,在自己的擴容數組裡面運行:

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

這個時候結構圖: 

 

然後e=next; 
在進入循環執行:

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

這個時候結構為: 

然後線程B執行完畢。線程A開始從(1)後面繼續執行,這個時候也是先執行

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

 

然後e=next;這個時候e是節點6,然後再進入循環,執行上面兩行程序後的結構如下: 

但是這個時候由於6的next是有值的,是節點5,所以再執行e=next;的時候,e不為空,還會進入一次循環,在執行將節點插入頭部的操作,所以這個時候的結構圖:

可以,看到已經成為瞭環狀鏈表,當執行get操作的時候就會產生死循環。 

到此這篇關於hashMap擴容時應該註意這些死循環問題的文章就介紹到這瞭,更多相關hashMap擴容內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!