Java中的衝突解析HashMap

Java HashMap使用put方法在HashMap中插入K/V對。可以說，我已經使用put方法，現在HashMap<Integer, Integer>有key一個條目10和value爲17Java中的衝突解析HashMap

如果我在這個HashMap插入10,20它只是替換與此項上一個條目中因碰撞，因爲

如果密鑰衝突HashMap用新的K/V對替換舊的K/V對。

所以我的問題是什麼時候HashMap使用鏈接衝突解決技術？

爲什麼它沒有形成一個linkedlist與鍵爲10和價值17,20？

在此先感謝！ Shri

來源

2013-10-30 user2938723

嘿，誰是downvoting所有這些正確的答案？畢竟，這個行爲是Map接口需要的。 – Axel

@Axel：我想這是因爲人們誤解了OP。 OP基本上想知道當多個密鑰被哈希到同一個桶時會發生什麼。那是在使用衝突解決方案時。所有其他人的答案繼續關於多地圖和什麼不... –

但是，OP明確給出了用相同的鍵（10）放兩個元素的例子，並想知道爲什麼不存儲兩個不同的值。這*是MultiMap的行爲。 – Axel

當您插入(10, 17)對，然後(10, 20)時，在技術上不涉及碰撞。您只需用新值或給定密鑰10替換舊值（因爲在這兩種情況下，10等於10，並且10的散列碼始終爲10）。

當多個鍵散列到同一個存儲桶時發生碰撞。在這種情況下，您需要確保您可以區分這些鍵。鏈接衝突解決方案是用於此的那些技術之一。

如作爲例子，讓我們兩個字符串"abra ka dabra"和"wave my wand"收率散列碼100和200分別該假設。假設總陣列大小爲10，它們都會在同一個存儲區中結束（100 % 10和200 % 10）。鏈接確保無論何時您做map.get("abra ka dabra");，您最終都會得到與該關鍵字相關的正確值。在Java中的哈希映射的情況下，這通過使用equals方法來完成。

來源

2013-10-30 19:20:45

所以桶將存儲鏈的地址，鏈將包含節點;每個節點都有一個鍵/值結構？因此，在這種情況下，鏈中將有一個節點的鍵爲「abra ka dabra」，另一個節點的鍵在同一鏈中右鍵爲「揮手」。 – user2938723

@ user2938723：是的，基本上每個數組插槽將包含一個鍵值對的「鏈」。 –

您的示例中沒有碰撞。您使用相同的密鑰，因此舊值將被替換爲新值。現在，如果您使用兩個映射到相同哈希代碼的密鑰，那麼您就會碰撞。但即使在這種情況下，HashMap也會取代你的價值！如果您希望在發生碰撞時將這些值鏈接起來，您必須自己動手，例如通過使用列表作爲值。

來源

2013-10-30 19:20:53 Macondo2Seattle

什麼是HashTable？如果你在談論java.util.Hashtable，它實現的是同樣的Map接口，並且具有相同的行爲 – iluxa

你是對的，我會糾正。 – Macondo2Seattle

它沒有被定義爲這樣做。爲了實現這一功能，你需要創建一個映射鍵映射到值的列表：

Map<Foo, List<Bar>> myMap;

或者，你可以使用the Multimap from google collections/guava libraries

來源

2013-10-30 19:20:57 yamafontes

它可能已經形成一個鏈表，確實如此。這只是Map合同要求它來代替條目：

V put(K key, V value)

將指定值與此映射（可選操作）指定的鍵。如果映射先前包含關鍵字的映射，則舊值由指定值替換。（A地圖m是據說含有一個密鑰k的映射當且僅當m.containsKey（K）將返回true。）

http://docs.oracle.com/javase/6/docs/api/java/util/Map.html

對於地圖存儲值列表，它需要是一個Multimap。下面是谷歌的：http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

類似的地圖收藏，但它可以與單個鍵關聯多個值。如果您使用相同的密鑰（不同的值）調用put（K，V）兩次，則multimap包含從密鑰到值的映射。

編輯：衝突解決

這是一個有點不同。當兩個不同的密鑰恰好具有相同的哈希碼時，或者具有不同哈希碼的兩個密鑰碰巧映射到底層數組中的相同存儲桶時，會發生衝突。

考慮HashMap的源（去掉邊角料）：

public V put(K key, V value) { 
    int hash = hash(key.hashCode()); 
    int i = indexFor(hash, table.length); 
    // i is the index where we want to insert the new element 
    addEntry(hash, key, value, i); 
    return null; 
} 

void addEntry(int hash, K key, V value, int bucketIndex) { 
    // take the entry that's already in that bucket 
    Entry<K,V> e = table[bucketIndex]; 
    // and create a new one that points to the old one = linked list 
    table[bucketIndex] = new Entry<>(hash, key, value, e); 
}

對於那些誰是好奇Entry類HashMap如何來表現得像一個列表，事實證明，HashMap定義了它自己的靜態Entry類實現Map.Entry。您可以通過查看源代碼看到自己：

GrepCode for HashMap

來源

2013-10-30 19:21:41 iluxa

「或具有不同哈希碼的兩個密鑰碰巧映射到底層陣列中的同一個存儲桶中。這將如何發生？我認爲不同的哈希=不同的桶。不是嗎？ –

在HashMap關鍵是一個對象，包含hashCode()和equals(Object)方法。

當您插入在地圖上的新條目，它會檢查是否hashCode是已知的。然後，它會通過這個哈希碼的所有對象進行迭代，並與.equals()測試他們的平等。如果發現等於對象，新值取代舊的。如果不是，它會在地圖上創建一個新條目。

通常，在談論地圖時，您使用碰撞當兩個物體有相同的hashCode但它們是不同的。它們在內部存儲在一個列表中。

來源

2013-10-30 19:22:26

首先，你必須散列一點點錯誤的概念，它已被桑傑先生糾正。

是的，確實的Java實現衝突解決方法。當兩個密鑰獲得散列到相同的值（用作內部數組是有限的尺寸並且在某個點的哈希碼（）方法將用於兩個不同的密鑰返回相同的散列值），此時，在剷鬥形成鏈表所有信息都作爲包含鍵值對的Map.Entry對象輸入的位置。通過密鑰訪問一個對象在最壞的情況下需要O（n），如果該條目存在於這樣的列表中。您在這種列表中使用每個鍵傳遞的鍵之間的比較將由equals（）方法完成。

雖然，從Java 8中，鏈表被樹木所取代（O（log n）的）

來源

2015-09-26 13:48:30

有衝突和重複之間的差異。衝突意味着哈希碼和桶相同，但是重複的情況下，它將是相同的哈希碼，相同的桶，但這裏等於方法進來的圖片。

檢測到碰撞，您可以在現有的鍵上添加元素。但在重複的情況下，它將取代新的價值。

來源

2017-01-04 21:54:28

Java中的衝突解析HashMap

回答

相關問題