IdentityHashMap是否會引起衝突？

作爲每IdentityHashMap的Javadocs，它說IdentityHashMap是否會引起衝突？

此類實現Map接口利用哈希表，比較鍵（和值）時使用引用相等代替對象相等的。換句話說，在IdentityHashMap中，當且僅當(k1==k2)時，兩個密鑰k1和 k2被認爲是相等的。（在正常Map 實現（像HashMap）兩個鍵K1和K2被認爲是相等當且僅當(k1==null ? k2==null : k1.equals(k2))。）

據我所知，指向不同的存儲位置的兩個不同的對象仍可以具有相同的散列碼，因此object1.equals(object2)可以返回true。但是，指向不同存儲位置的兩個不同對象永遠不會爲object1 == object2返回true。

問題1 - 當IdentityHashMap嚴格依賴於參考平等，這是否意味着碰撞永遠不會發生？

問題2 - 調試下面的代碼顯示了我的6個桶，其中key和value都存儲在單獨的桶中。但HashMap的情況並非如此，其中密鑰和值存儲在同一個存儲桶中。因爲它的名字中有一個'哈希'單詞，所以它必須是哈希鍵，那麼它爲什麼單獨存儲鍵和值，以及它如何檢索給定鍵的值？

String A = "abc"; 
String B = "def"; 
String C = new String("abc"); 
Map<String, String> map1 = new IdentityHashMap<String, String>(); 
map1.put(A, "123"); 
map1.put(B, "345"); 
map1.put(C, "567");

來源

2012-10-08 Arham

這裏有很多困惑的想法。 1.所有的哈希系統必須處理碰撞。 2.具有相同的哈希碼並不意味着equals（）返回true。 3.在類名稱中存在「散列」與單獨存儲鍵和值無關，這是由於其名稱中存在「映射」這個詞而產生的。 – EJP

碰撞發生時，兩個不同的項目有相同的散列碼，所以很明顯IdentityHashMap必須處理衝突。唯一不同的是，「常規」哈希映射使用equals，對於不同的對象可以使用true，而IdentityHashMap使用==，對於不同的對象不能使用true。

「常規」散列映射具有鍵和值獨立變量的原因是IdentityHashMap的實現細節：它的實現使用linear probing，以解決衝突，而且還存儲鍵和值在同一個表：關鍵是放置在table[hash]，而價值被放置在table[hash+1]。常規的HashMap定義了一個Entry類，它將鍵和它的值組合在同一個對象中，並將條目存儲在桶中。

來源

2012-10-08 09:51:09 dasblinkenlight

這個詞是「線性探測」...解決了我所有的困惑。我被困在Linkedlist鏈接的世界裏。 :) – Arham

時IdentityHashMap嚴格依賴於引用相等
，是否意味着衝突不會發生？

碰撞幾乎和沒有碰撞一樣。系統散列碼並不是唯一的，即使它們是集合也不是2 ^^ 32的大小，所以只有hashCode必須被減少到少量的位。

它如何檢索給定密鑰的值？

我會閱讀代碼來找出答案。

public V get(Object key) { 
    Object k = maskNull(key); 
    Object[] tab = table; 
    int len = tab.length; 
    int i = hash(k, len); 
    while (true) { 
     Object item = tab[i]; 
     if (item == k) 
      return (V) tab[i + 1]; 
     if (item == null) 
      return null; 
     i = nextKeyIndex(i, len); 
    } 
}

來源

2012-10-08 09:50:51

謝謝彼得。所以，這意味着該值始終存儲在鍵旁邊的索引中。我證實，在IDE上進行調試時，爲什麼JDK開發人員不使用在一個存儲桶中一起存儲密鑰和值的通用設計。當然，它使用了一個叫做System.identityHashCode的東西，那麼是什麼？正因爲如此，它最終會導致桶的數量增加，並最終佔用比一般HashMap更多的空間，這帶來了另一個問題，即真實世界的用例是否需要這樣的Map？ – Arham

實際上，IHM使用更少的內存，因此「bucket」只有兩個引用（8字節），而Map.Entry在內存中隨機位置的長度爲16-24個字節。我懷疑代碼編寫時的不同之處在於，版本1.4爲IHM，版本1.2爲HM。 –

IdentityHashMap不使用密鑰的hashCode，而是使用它們的System.identityHashCode。雖然如果你有很大的內存，這些身份哈希碼的衝突是可能的，但它們很少。這當然不會阻止兩個密鑰在同一個桶中結束，因爲桶的數量通常遠小於2^32 - 1.

來源

2012-10-08 09:51:18

謝謝JB。但是當我使用引用相等的時候，我仍然無法想象在同一個桶中結束的兩個密鑰。你能提供一個例子或某種方式來執行此操作嗎？ – Arham

@Arham爲了映射到相同的哈希桶，它不是必須相同的對象 - 它們的身份哈希碼必須相同。 – dasblinkenlight

確切地說，它們的身份哈希碼必須相同，或者在應用該映射的哈希算法時導致相同的存儲桶索引。 –

IdentityHashMap是否會引起衝突？

回答

相關問題