java HashMap碰撞

Question

我在讀關於hashmap是如何工作的。我讀通過 "What will happen if two different objects have same hashcode"。

根據它，如果兩個對象具有相同的哈希碼都將被存儲在LinkedList但據我所知，如果兩個哈希碼，然後上一個將被覆蓋新的（糾正我，如果我錯了）。

請問有人可以更多地瞭解hashmap如何在內部使用對象作爲關鍵字，以及如果兩個對象具有相同的哈希碼以及如何使用get()獲取這兩個對象，會發生什麼？

Answer 1

沒有，只是因爲第二個具有相同hashCode第一個是沒有被覆蓋。

應當覆蓋僅當它也等於（由equals所述）。如果不是，則這兩個值將保留在鏈接列表中。

當提取密鑰時，所有具有相同hashCode的節點將與提供的密鑰進行比較，直到其中一個相等，然後返回其值（使用equals方法）。

如果地圖沒有鑰匙是平等的，你會得到null。

如果許多對象具有相同的hashCode（或者更確切地說，相同的hashCode以內部Entry[] table的大小爲模），唯一的問題是鏈表總是被讀取，這是比較慢的（並且失敗了任何散列表）。這就是設計hashcode方法以確保生成的整數分佈均勻的原因。

Answer 2

假設您遵循的規則defining hashCode and equals，您所描述的情況下不會導致數據丟失。性能會隨着時間的推移而降低。

Answer 3

在Java的HashMap他們可以用幾種方式來做到這一點。從我的舊CS 201的數據結構類在黑暗時代背：

1）在哈希表每個桶能成爲一個鏈表保存所有條目的頭補充說，具有相同的哈希值。添加時的衝突意味着您將新條目添加到鏈接列表的末尾。搜索意味着您必須線性檢查任何鏈接列表中的所有鏈接列表，只要您將其存入存儲區中即可。

2）如果發生碰撞和實體店是概念上的數組，你可以迭代開始在這一點上，直到你找到一個空白點，並添加新條目出現。對於搜索來說，這意味着如果您發現哈希桶已被佔用，那麼您必須從該點線性比較數組中支持哈希映射的下一個空白點。

在這兩種情況下，如果有相同的哈希多個條目的性能下降。在一般情況下，這意味着散列函數（用於生成散列碼）返回少量可能的值，隨着映射填充，性能將降低。 Java HashMap利用了50年來對這些事情的研究，以適應一般數據進入散列圖的一般情況。

注@dystroy作出關於根據equals（）方法，你不能在地圖上的兩個條目與比賽規則的註釋。

Answer 4

讓我解釋一下HashMap的工作。

工作put方法：

的HashMap作品上散列的原則，我們對存儲和檢索對象的形式HashMap的put()和get()方法。當我們將一個key和value都傳遞給存儲在HashMap上的方法時，它使用關鍵對象hashcode()方法來計算哈希碼，並且他們通過對該哈希碼應用哈希來標識存儲值對象的存儲桶位置。檢索它時使用鍵對象equals方法來找出與該鍵相關的正確的鍵值對和返回值對象。 HashMap在發生衝突時使用鏈表，對象將存儲在鏈表的下一個節點中。在鏈表

get方法的工作的每一個節點 此外HashMap中同時存儲鍵+值的元組：

當我們通過鍵和值對象到Java的HashMap的put()方法，HashMap的實現調用hashCode方法Key對象並將返回的散列碼應用到其自己的散列函數中以查找存儲Entry對象的存儲區位置，重要的一點是Java中的HashMap將存儲區中的key和value對象存儲爲Map.Entry。如果在桶中找到多個Entry對象，它將調用同一個桶中每個節點的ke.equals方法。