處理Hashmap中的關鍵衝突

code我發現Hashmap的put(K key, V value)。如果碰撞發生，此方法會替換值，但不會將Entry添加到存儲區的LinkedList。
我在這裏失蹤了什麼？處理Hashmap中的關鍵衝突

2013-11-20 Himanshu Yadav

我認爲您正在將碰撞（相同的哈希碼）與equals（實際上等效）混合在一起。 –

可能。我想看看java如何處理碰撞。 –

你爲什麼這麼想？相關線路如下：在內部表

計算指數：

390 int i = indexFor(hash, table.length);

遍歷鏈表在table[i]和搜索如果該鍵已經包含：

391 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
392  Object k; 
393  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

重點已經包含=>替換值...

394   V oldValue = e.value; 
395   e.value = value; 
396   e.recordAccess(this);

...並返回ol d值

397   return oldValue; 
398  }

否則繼續循環

399 }

我們在鏈表的結束，我們還沒有找到關鍵的是，所以它不是已經包含。因此，讓我們添加一個新條目：

402 addEntry(hash, key, value, i);

來源

2013-11-20 18:30:53 isnot2bad

線'394-396'是我的問題。它爲什麼取代舊價值？ –

參見map＃put的規範：「（...）如果映射先前包含該鍵的映射，則舊值由指定值替換（...）。這不是」碰撞「，因爲其他如果兩個鍵具有相同的散列碼但不相等，則在這種情況下，替換不會發生！（見第402行） – isnot2bad

如果您需要爲每個鍵保留多個值，請考慮使用List作爲值或提供MultiMap的第三方庫（例如http://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/MultiMap.html ） – isnot2bad

您不能在HashMap中多次使用相同的密鑰。這就是爲什麼價值被取代，而不是隻是創造一個新的Map.Entry<K,V>

來源

2013-11-20 18:25:21

你是不是錯過了一件事。 Java的Map的總體合同是每個密鑰具有單個值。如果你想保存每個鍵的多個值，你必須使用類似Apache Commons' MultiMap的東西，或者通過擁有Map<K, List<V>>來自己實現類似的東西。

來源

2013-11-20 18:26:58 Mureinik

或番石榴multimap – Cruncher

你是說Java HashMap不處理碰撞情況。它只是取代了價值。是這樣嗎？ –

@HimanshuYadav是的。 JDK中的其他地圖也是如此。 – Mureinik

處理Hashmap中的關鍵衝突

回答

相關問題