Categories
程式開發

HashMap將cpu打滿始末


什麼情況下使用HashMap會導致cpu被打滿呢?

一般来说cpu被打满,我们会有一个下意识的想法是程序出现了死循环,那死循环是怎么产生的呢?这种情况很诡异,正常的单线程情况下不会出现,所以,以造成诡异bug著称的多线程就得出来背锅了。

事實上,該問題的確是在多線程中不恰當使用HashMap導致的,因為HashMap不是線程安全的。

下面通過舉例分析多線程情況下,死循環的產生過程:

1、首先,該過程發生在HashMap進行容量擴容的過程,核心代碼如下:

1: // Transfer method in java.util.HashMap -
2: // called to resize the hashmap
3:
4: for (int j = 0; j < src.length; j++) { 5: Entry e = src[j]; 6: if (e != null) { 7: src[j] = null; 8: do { 9: Entry next = e.next; 10: int i = indexFor(e.hash, newCapacity); 11: e.next = newTable[i]; 12: newTable[i] = e; 13: e = next; 14: } while (e != null); 15: } 16: }

正常情況下(無線程競爭)的擴容過程:

1)假設size=2的一個HashMap,準備擴容到size=4.

HashMap將cpu打滿始末 1

2)遍歷數組中的每條鍊錶,將元素插入到新數組的鍊錶中,直至next=null:

HashMap將cpu打滿始末 2

HashMap將cpu打滿始末 3

HashMap將cpu打滿始末 4

多線程不同步情況下會產生死循環的場景:

1)我們假設有T1和T2。 兩個線程同時調用擴容過程,也即上面那段代碼。 當T1執行完第9行,線程被切換:

1: // Transfer method in java.util.HashMap -
2: // called to resize the hashmap
3:
4: for (int j = 0; j < src.length; j++) { 5: Entry e = src[j]; 6: if (e != null) { 7: src[j] = null; 8: do { 9: Entry next = e.next; // Thread1 STOPS RIGHT HERE 10: int i = indexFor(e.hash, newCapacity); 11: e.next = newTable[i]; 12: newTable[i] = e; 13: e = next; 14: } while (e != null); 15: } 16: }

此時的HashMap的指針情況:e和next被設置指向如下(在e和next後面加1,代表T1線程):

HashMap將cpu打滿始末 5

2)緊接著,T2開始執行,並執行完整個擴容過程:

HashMap將cpu打滿始末 6

3)重點:此時T2將B指向了A,e1指向A,next1指向B。 當T1恢復執行時,會將A的next指向B,循環指向產生。 完整的執行過程如下:

HashMap將cpu打滿始末 7

HashMap將cpu打滿始末 8

HashMap將cpu打滿始末 9

以上就是HashMap將cpu打滿的全過程,是線程安全的典型案例。 解決方法很簡單,就是做好同步。

參考資料:

美麗的比賽條件