2014-07-23 16 views
-3

我有seen something,它解釋了爲什麼HashMap在多線程中未被鎖定的原因。爲什麼HashMap在多個線程中是unsafed?

它說,做大小調整時,在鏈表對象的整個序列被逆轉,它顯示的例子:

例如,讓我們假設有3個按鍵具有相同的哈希碼,因此存儲(下面的格式在object_value(current_address,next_address)]中
初始結構:1(100,200) - > 2(200,300) - > 3(300,null)
After通過線程1調整大小:3(300,200) - > 2(200,100) - > 1(100,null)
當線程2開始調整大小時,通過將其放置在頭:
1(100,300) - > 3(300,200) - > 2(200,100)==>這將成爲下一個插入的無限循環,並且線程在此處掛起。

我很困惑的例子中,

初始結構:1 - > 2 - > 3

線程1:3-> 2-> 1

線程2:1 - > 3 - > 2爲什麼?

任何人都可以幫我分析一下這個例子或者展示一個更詳細的例子嗎?謝謝。

+2

拜託。當你可以更容易地發佈原始文本時,你是否必須創建和發佈圖片?爲什麼要在這個史詩般的規模上浪費時間和空間?考慮到你引用的同一段中給出了答案,很難看出你爲什麼要發佈這個問題。 – EJP

+0

您的鏈接已損壞。 – djechlin

+0

我對你在問什麼感到困惑:你有興趣知道爲什麼內部鏈表逆轉嗎?或者你想知道爲什麼HashMap不是線程安全的? –

回答

1

我不清楚你在問什麼。

你有興趣知道爲什麼HashMap不是線程安全的嗎?或者你只是想知道調整大小期間「反轉」效果的原因(這是線程不安全的原因之一)?

對於後一個問題(這是你的問題明確要求的),這裏的原因是:

通過檢查HashMap中的源代碼,有一個transfer()方法,其負責人向條目從舊移動表到新的一個:

void transfer(Entry[] newTable) { 
    Entry[] src = table; 
    int newCapacity = newTable.length; 
    for (int j = 0; j < src.length; j++) { 
     Entry<K,V> e = src[j]; 
     if (e != null) { 
      src[j] = null; 
      do { 
       Entry<K,V> next = e.next; 
       int i = indexFor(e.hash, newCapacity); 
       e.next = newTable[i]; 
       newTable[i] = e; 
       e = next; 
      } while (e != null); 
     } 
    } 
} 

反向是上述邏輯的副作用(看靠近do-while循環,它不應該是不難理解)。

如果你問他們爲什麼要讓訂單反向,那麼你最好問作者。不過,我可以告訴你,他們不打算「顛倒」訂單。由於HashMap沒有迭代次序,所以實現不需要維護任何次序。只要結果是正確的,實施者可以選擇最簡單和最快的方式來實現調整大小邏輯。目前的邏輯是他們的選擇。


更新:如果你只是想知道一個非線程安全的情況,還有其他一些更明顯的情況。

例如,添加到地圖中的條目時,邏輯是這樣的:首先計算該指數把條目,它在表中添加到該索引,如果表是「完全」,然後做調整。

有可能是,一個線程試圖添加一個條目,然後哈希碼是101,那麼它找出指標的情況下,和原來的表大小爲100,和值爲1

在這時間,另一個線程進來,並添加一個條目到表中,並發現表是「滿」,然後它進行調整大小。新表的大小現在是200

那麼在這個時候,線程1去的實際上是把條目表,並試圖把索引1.然而,隨着大小200,新表步驟正確的索引應該是101而不是1.

結果是地圖導致了一個損壞的狀態。

還有更多不同的線程不安全的例子。


對於您提到的給定示例。下面是它如何可能會導致問題的一個具體的例子:

假設現有的哈希表:

[0] -> E1 -> E2 -> E3 -> null 
[1] 

調整大小會做這樣的事情:

- Create a new table 
(old table) 
[0] -> E1 -> E2 -> E3 -> null 
[1] 

(new table) 
[0] 
[1] 
[2] 
[3] 


- iterate thru the original entries, and put it one by one 

(Put E1 to new table) 
[0] -  E2 -> E3 
[1] \ 
     \ 
     v 
[0] -> E1 ->null 
[1] 
[2] 
[3] 

(Put E2 to new table) 
[0] ------  E3 
[1]  \ 
      \ 
      v 
[0] -> E2 -> E1 ->null 
[1] 
[2] 
[3] 

你會在這一點看,指數舊錶的0仍然指向E1

如果另一個線程進來,嘗試做大小調整,做在這樣的中間狀態調整可能會導致所有這類問題:0錯誤與原始文章中一樣,或在結果表中缺少條目等。

+0

謝謝,阿德里安,我很抱歉,我沒有清楚描述我的問題,這個例子解釋了在多線程中會發生什麼,我無法理解,並且我在問爲什麼HashMap不是線程安全的。 –

+0

如果你只是想知道一個將會是非線程安全的情況,那麼就更加明顯。請檢查我的更新 –

0

從Oracle Java文檔(http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html

注意,此實現不是同步的。如果多個線程 同時訪問哈希映射,並且至少一個線程在結構上修改映射,則它必須在外部同步。 (A 結構修改是添加或刪除一個或更多映射的任何操作;僅更改與實例已包含的密鑰關聯的值不是結構修改。)這通常是通過同步某個對象自然 封裝了地圖。如果不存在此類對象,則應使用Collections.synchronizedMap方法將地圖「包裝」爲 。這是最好的 在創建時完成,以防止意外的不同步訪問, 地圖:

Map m = Collections.synchronizedMap(new HashMap(...)); 

當您添加的元素到一個HashMap,它的內部結構發生變化,所以你不能信任元素的順序在一個hashmap中。如果你想保持排序,使用一個TreeMap。