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

Posted on by

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！

推薦閱讀：