我最近才知道，在Java中8名哈希映射使用二叉樹而不是鏈表和散列碼作爲分支factor.I理解，在高碰撞的情況下，查找是（log n）的由O至O （n）通過使用二叉樹。我的問題是它有什麼好處，因爲分期償還的時間複雜度仍然是O（1），並且如果您強制通過爲所有的散列碼提供相同的哈希碼來強制將所有條目存儲在同一個桶中我們可以看到重要的時間差異，但是他們正確的頭腦中沒有人會這樣做。爲什麼Java 8中的哈希映射使用二叉樹而不是鏈接列表？
二叉樹也使用它存儲左側和右側nodes.Why增加空間複雜度時存在時間複雜度完全沒有改善，除了一些虛假的測試情況下比單鏈表更多的空間。
這主要是與安全相關的更改。在正常情況下，如果散列鍵來自不受信任的源（例如，從客戶端接收到的HTTP標頭名稱），那麼很少有可能發生多次衝突，那麼專門製作輸入是可能的並且不是很難，所以得到的鍵將具有相同的哈希碼。現在，如果您執行很多查詢，您可能會遇到拒絕服務。看起來，這種攻擊很容易出現很多代碼，因此決定在Java端修復此問題。
欲瞭解更多信息，請參閱JEP-180。
同意但用戶如何在不知道底層散列函數的情況下製作輸入以增加衝突？ – user1613360
@ user1613360，'String'的散列函數是衆所周知的並且[記錄]（https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#hashCode--），所以這不是一個大問題。每個Java實現必須使用相同的功能。 –
除了某些哈希代碼是固定的並且有詳細記錄的事實之外，攻擊者總是可以嘗試找出服務器正在運行的特定版本，並查看計算特定類實現的哈希代碼的方式。這就是大多數攻擊的工作原理，首先，找出哪些軟件運行，然後嘗試針對特定軟件和版本進行適當的利用。 – Holger
你的問題包含一些錯誤的前提。
Map的大小應該是合理的，因此不能任意提高數組大小以避免存在桶衝突。甚至存在理論上的限制，即數組大小可能在最大2 3¹，而有2 3²可能的哈希碼。String s爲一個明顯的例子，但即使是Point帶有兩個int值或純Long鍵有不可避免的散列衝突。所以它們可能比你想象的更普遍，它很大程度上取決於用例。只有當碰撞在桶中的數量超過一定閾值，更高的內存成本僅適用時，他們將還清Comparable時，纔會使用其自然順序。您可能在網上找到的示例有意使用相同的散列碼作爲對象，以演示如何使用Comparable實現，否則該實現不會顯示。他們觸發的只是實施的最後手段。相關：[http://www.javaspecialists.eu /archive/Issue235.html](http://www.javaspecialists.eu/archive/Issue235.html） –
指出「桶衝突」不一定與「散列衝突」相同在這裏很重要。許多程序員錯誤地認爲它們是同義詞。 – nanosoft
這不是辯論。我引用：*我的問題是它真的有什麼好處呢[...]也許如果我們可以看到明顯的時間差異，但他們正確的頭腦中沒有人會這樣做。所以你的意思是說它的設計是爲了處理一個沒有人在他們正確的頭腦中會做的事情，因此，開發者**明確地處理了一個愚蠢的情況，因此開發者是愚蠢的，而你持有真理。我建議改寫你的問題。 – Tunaki
你的問題沒有意義。如果你認爲散列衝突不會發生，那麼二叉樹不會消耗更多空間，因爲二叉樹只有在有*散列衝突時纔會使用。更確切地說，在實現從鏈表切換到二叉樹之前，碰撞次數必須超過閾值。 – Holger
@Tunaki我特意指人們故意試圖說明這種情況，如果我認爲沒有其他更多的東西，我就不會將它作爲一個問題。 – user1613360