Java的HashMap的碰撞檢測

Question

有沒有一種方法來檢測Java的哈希地圖碰撞？任何人都可以指出某種情況下可能發生很多碰撞事件。當然，如果你重寫一個對象的哈希碼，並簡單地返回一個常數值，肯定會發生衝突。我不是在談論那個。我想知道在前面提到的其他情況下會發生大量碰撞的情況而無需修改默認的哈希碼實現。

Answer 1

我創建了一個項目，這些基準樣的事情：http://code.google.com/p/hashingbench/（對於鏈接哈希表，開放尋址和布隆過濾器）。

除的hashCode關鍵的（），你需要知道「抹黑」（或「擾」，我把它在該項目）的哈希表的功能。從this list，HashMap中的拖尾功能是等價的：

public int scramble(int h) { 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

所以對於發生HashMap中的碰撞，必要和足夠條件如下：scramble(k1.hashCode()) == scramble(k2.hashCode())。 這始終是真，如果k1.hashCode() == k2.hashCode()（否則，塗抹/加擾功能不會是功能），所以這是一個足夠，但不是必要條件爲發生碰撞。

編輯：實際上，上述的充分必要條件應該已經compress(scramble(k1.hashCode())) == compress(scramble(k2.hashCode())) - 的compress函數取的整數，並將其映射到{0, ..., N-1}，其中N是桶的數量，因此，它基本上選擇一個桶。通常情況下，這根本是實現爲hash % N，或者在哈希表大小爲二的冪（這實際上是對具有電源的兩散列表的大小動機），爲hash & N（快）。 （「壓縮」是Goodrich和Tamassia用於描述這一步驟的名稱，在Data Structures and Algorithms in Java中）。感謝ILMTitan發現我的sl iness。其他散列表實現（ConcurrentHashMap，IdentityHashMap等）有其他需求並使用另一個拖尾/加擾函數，所以你需要知道你在談論哪一個。 （例如，HashMap的拖尾函數已經設置好了，因爲人們使用HashMap和hashCode（）的最壞類型的對象來實現HashMap的舊的，兩次冪的實現，而不會拖尾 - 不同的對象一點點，或者根本沒有，用於選擇一個桶的低位 - 例如new Integer(1 * 1024),new Integer(2 * 1024) *等等。正如你所看到的，HashMap的拖尾函數儘量讓所有位影響低位）。

儘管如此，它們都可以在常見情況下正常工作 - 特殊情況是繼承系統的hashCode（）的對象。 PS：其實，提示執行者插入拖尾函數的絕對醜陋的情況是Floats/Doubles的hashCode（），以及用作值的鍵的用法：1.0,2.0,3.0,4.0 ...，它們都具有相同的（零）低位。這是有關老的bug報告：http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4669519

Answer 2

簡單的例子：一個散列Long。顯然，有64位輸入，只有32位輸出。的Long哈希值記錄爲：

(int)(this.longValue()^(this.longValue()>>>32)) 

即想象它的下堅持兩個彼此int值和XOR他們。

因此，所有的這些都將有0的散列碼：

0 
1L | (1L << 32) 
2L | (2L << 32) 
3L | (3L << 32) 

等

我不知道這是否算作是「衝突的數量龐大」，但它是一個例子，其中碰撞是容易製造。

顯然任何散列結果，其中有超過2 可能值會有衝突，但在許多情況下，他們難以產生。例如，儘管我只使用ASCII值在String上看到了散列衝突，但它們的生產難度要高於上述。

Answer 3

另外兩個答案，我看到一個很好的IMO，但我只是想和大家分享，最好的方式來測試你的hashCode()的行爲在HashMap是如何實際生成的一個大數目來自你班級的對象，將它們放在特定的HashMap實現中作爲密鑰並測試CPU和內存負載。 1或200萬個條目是一個很好的數字，但如果您使用預期的地圖大小進行測試，則可以獲得最佳結果。

我只是看着一個我懷疑它的哈希函數的類。所以我決定用這種類型的隨機對象和測試碰撞次數填充一個HashMap。我測試了正在調查的類的兩個hashCode（）實現。所以我在groovy中寫下了你在底部看到的擴展了HashMap的openjdk實現的類來計算進入HashMap的衝突數量（見countCollidingEntries()）。請注意，這些不是整個散列的實際衝突，而是包含條目的數組中的衝突。數組索引計算爲hash & (length-1)，這意味着此數組的大小越短，您獲得的衝突就越多。這個數組的大小取決於initialCapacity和loadFactor的HashMap（它可以增加當put()更多的數據）。

儘管我認爲看着這些數字沒什麼意義。由於HashMap速度較慢，而且方法較差，這意味着只需通過對來自Map的數據的插入和檢索進行基準測試，就可以有效地瞭解哪個實施更好。

public class TestHashMap extends HashMap { 

    public TestHashMap(int size) { 
     super(size); 
    } 

    public TestHashMap() { 
     super(); 
    } 

    public int countCollidingEntries() { 
     def fs = this.getClass().getSuperclass().getDeclaredFields(); 
     def table; 
     def count =0 ; 
     for (java.lang.reflect.Field field: fs) { 
     if (field.getName() == "table") { 
      field.setAccessible(true); 
      table = field.get(super); 
      break; 
     } 
     } 
     for(Object e: table) { 
     if (e != null) { 
      while (e.next != null) { 
       count++ 
       e = e.next; 
      } 
     } 
     } 
     return count; 
    } 
}