哈希映射在多線程環境中時做調整

我下面的教程，它基本上解釋了有關競爭狀態的原因在多線程環境調整的Hashmap時發生的情況：哈希映射在多線程環境中時做調整

在Java中，如果兩個線程在同一時間發現，現在HashMap需要調整大小，並且它們都嘗試調整大小。在Java中對HashMap進行大小調整的過程中，存儲在鏈表中的存儲區中的元素在遷移到新存儲區時會按順序顛倒過來，因爲Java HashMap不會在尾部附加新元素，而是在頭部添加新元素避免尾部遍歷。如果隨後的比賽情況發生了，你會看完這個結束了一個無限循環

我有兩個問題：

爲什麼每個區塊的鏈接列表中的順序顛倒？
我可以看到可能存在競爭條件，但看不到無限循環如何來？是否因爲一個線程可能會將元素頭附加到尾部，而另一個線程則以相反的順序進行呢？

請幫我澄清一下，非常感謝！

來源

2013-04-12 Kevin

我不知道回答你的問題 - 我只是想建議你使用線程安全的[ConcurrentHashMap的（多線程程序中的http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentHashMap.html）。 –

'HashMap'不是線程安全的，在多線程環境中使用它是一個壞主意。您將在另一種方法中獲得競賽條件。 – gaborsch

實際上至少有一個競賽條件與重新哈哈有關。看看這個代碼片段（它是來自Sun JDK 7）：

boolean oldAltHashing = this.useAltHashing; 
this.useAltHashing |= sun.misc.VM.isBooted() && (this.newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 
boolean rehash = oldAltHashing^this.useAltHashing; 
transfer(newTable, rehash); 
this.table = newTable;

這裏有可能是線程T1與rehash = true結束了和線程T2與rehash = false（讓我們假設T1已經改變的this.useAltHashing值）結束了。

現在，猜猜哪個線程將寫入this.table - 你不知道，也可以。所以，不管你是否獲得一致的內部狀態，這都是一個幸運的問題。

無論如何，正如我在我的評論中提到的那樣，它不應該在多線程環境中使用HashMap。不起作用。要麼是因爲這個原因，要麼是因爲其他原因。以上只是一個例子，爲什麼你不應該試圖違背合同。

來源

2013-04-12 14:37:51 gaborsch

我不知道這個例子是否有效。明確的是，它是特定於實施的。我認爲它也忽略了更大的圖景。

HashMap的contract清晰狀態（強調他們的）：

如果多個線程同時訪問一個散列映射，並且線程中的至少一個修改了該映射結構，它必須進行外部同步。（結構上的修改是指添加或刪除一個或多個映射關係的操作;僅改變與實例已經包含的鍵關聯的值不是結構修改。）

如果撕毀合同，所有的賭注已關閉。這張地圖可以以任意的，不確定的方式自由地炸燬。

來源

2013-04-12 14:37:02 NPE

關於第一個問題的答案是引用的文字：

「因爲Java的HashMap不附加在尾部的新元素，而不是它在頭部添加新元素，以避免尾穿越」

如果HashMap按照插入順序存儲它們，它必須在每次插入時遍歷列表或存儲一個指向列表末尾的額外指針（並維護它）。無論如何以插入順序將元素存儲在存儲區中不會帶來任何好處（至少我不能想到任何）。

回答你的第二個問題依賴這裏：

http://mailinator.blogspot.hu/2009/06/beautiful-race-condition.html

來源

2013-04-12 17:43:58

+1 – Songo

哈希映射在多線程環境中時做調整

回答

相關問題