Java京東面試題之為什麼HashMap線程不安全
01、多線程下擴容會死循環
眾所周知,HashMap 是通過拉鏈法來解決哈希沖突的,也就是當哈希沖突時,會將相同哈希值的鍵值對通過鏈表的形式存放起來。
JDK 7 時,采用的是頭部插入的方式來存放鏈表的,也就是下一個沖突的鍵值對會放在上一個鍵值對的前面(同一位置上的新元素被放在鏈表的頭部)。擴容的時候就有可能導致出現環形鏈表,造成死循環。
resize 方法的源碼:
// newCapacity為新的容量 void resize(int newCapacity) { // 小數組,臨時過度下 Entry[] oldTable = table; // 擴容前的容量 int oldCapacity = oldTable.length; // MAXIMUM_CAPACITY 為最大容量,2 的 30 次方 = 1<<30 if (oldCapacity == MAXIMUM_CAPACITY) { // 容量調整為 Integer 的最大值 0x7fffffff(十六進制)=2 的 31 次方-1 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); }
transfer 方法用來轉移,將小數組的元素拷貝到新的數組中。
void transfer(Entry[] newTable, boolean rehash) { // 新的容量 int newCapacity = newTable.length; // 遍歷小數組 for (Entry<K,V> e : table) { while(null != e) { // 拉鏈法,相同 key 上的不同值 Entry<K,V> next = e.next; // 是否需要重新計算 hash if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 根據大數組的容量,和鍵的 hash 計算元素在數組中的下標 int i = indexFor(e.hash, newCapacity); // 同一位置上的新元素被放在鏈表的頭部 e.next = newTable[i]; // 放在新的數組上 newTable[i] = e; // 鏈表上的下一個元素 e = next; } } }
註意 e.next = newTable[i]
和 newTable[i] = e
這兩行代碼,就會將同一位置上的新元素被放在鏈表的頭部。
擴容前的樣子假如是下面這樣子。
那麼正常擴容後就是下面這樣子。
假設現在有兩個線程同時進行擴容,線程 A 在執行到 newTable[i] = e;
被掛起,此時線程 A 中:e=3、next=7、e.next=null
線程 B 開始執行,並且完成瞭數據轉移。
此時,7 的 next 為 3,3 的 next 為 null。
隨後線程A獲得CPU時間片繼續執行 newTable[i] = e
,將3放入新數組對應的位置,執行完此輪循環後線程A的情況如下:
執行下一輪循環,此時 e=7,原本線程 A 中 7 的 next 為 5,但由於 table 是線程 A 和線程 B 共享的,而線程 B 順利執行完後,7 的 next 變成瞭 3,那麼此時線程 A 中,7 的 next 也為 3 瞭。
采用頭部插入的方式,變成瞭下面這樣子:
好像也沒什麼問題,此時 next = 3,e = 3。
進行下一輪循環,但此時,由於線程 B 將 3 的 next 變為瞭 null,所以此輪循環應該是最後一輪瞭。
接下來當執行完 e.next=newTable[i]
即 3.next=7 後,3 和 7 之間就相互鏈接瞭,執行完 newTable[i]=e
後,3 被頭插法重新插入到鏈表中,執行結果如下圖所示:
套娃開始,元素 5 也就成瞭棄嬰,慘~~~
不過,JDK 8 時已經修復瞭這個問題,擴容時會保持鏈表原來的順序,參照HashMap 擴容機制的這一篇。
02、多線程下 put 會導致元素丟失
正常情況下,當發生哈希沖突時,HashMap 是這樣的:
但多線程同時執行 put 操作時,如果計算出來的索引位置是相同的,那會造成前一個 key 被後一個 key 覆蓋,從而導致元素的丟失。
put 的源碼:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 步驟①:tab為空則創建 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 步驟②:計算index,並對null做處理 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 步驟③:節點key存在,直接覆蓋value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 步驟④:判斷該鏈為紅黑樹 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 步驟⑤:該鏈為鏈表 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //鏈表長度大於8轉換為紅黑樹進行處理 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // key已經存在直接覆蓋value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 步驟⑥、直接覆蓋 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 步驟⑦:超過最大容量 就擴容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
問題發生在步驟 ② 這裡:
if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
兩個線程都執行瞭 if 語句,假設線程 A 先執行瞭 tab[i] = newNode(hash, key, value, null)
,那 table 是這樣的:
接著,線程 B 執行瞭 tab[i] = newNode(hash, key, value, null)
,那 table 是這樣的:
3 被幹掉瞭。
03、put 和 get 並發時會導致 get 到 null
線程 A 執行put時,因為元素個數超出閾值而出現擴容,線程B 此時執行get,有可能導致這個問題。
註意來看 resize 源碼:
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 超過最大值就不再擴充瞭,就隻好隨你碰撞去吧 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 沒超過最大值,就擴充為原來的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 計算新的resize上限 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; }
線程 A 執行完 table = newTab
之後,線程 B 中的 table 此時也發生瞭變化,此時去 get 的時候當然會 get 到 null 瞭,因為元素還沒有轉移。
這是《Java 程序員進階之路》專欄的第 58 篇,我們來聊瞭聊為什麼 HashMap 是線程不安全的。
為瞭便於大傢更系統化地學習 Java,二哥已經將《Java 程序員進階之路》專欄開源到 GitHub 上瞭,大傢隻需輕輕地 star 一下,就可以和所有的小夥伴一起打怪升級瞭。
GitHub 地址:https://github.com/itwanger/toBeBetterJavaer
到此這篇關於Java京東面試題之為什麼HashMap線程不安全的文章就介紹到這瞭,更多相關Java HashMap線程內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Java詳細分析講解HashMap
- JDK8中的HashMap初始化和擴容機制詳解
- 基於hashmap 的擴容和樹形化全面分析
- 解析HashMap中的put方法執行流程
- 深入理解Java中的HashMap