如何獲得Java Hashmap上碰撞次數的度量？

Question

我正在實現一個自定義散列函數，如果我碰到一個HashMap存儲桶，我怎麼能知道存儲在存儲桶中有多少元素？

Answer 1

在API中沒有直接的支持。用於存儲桶的成員變量table甚至沒有公開，所以擴展該類不會讓你走得太遠。

假設你正在評估散列函數而不是在生產代碼中這樣做，你可以使用反射來傳遞這些約束。

我設法打印存儲桶的內容。從這一點來分析分配指標不應該很難。下面的代碼：

測試驅動程序：

import java.lang.reflect.Field; 
import java.util.*; 

class Test { 

    public static void main(String[] args) throws Exception { 

     SubHashMap<String, Integer> map = new SubHashMap<String, Integer>(); 

     map.put("zero", 0); map.put("one", 1); map.put("two", 2); 
     map.put("three", 3); map.put("four", 4); map.put("five", 5); 
     map.put("six", 6); map.put("seven", 7); map.put("eight", 8); 

     map.dumpBuckets(); 
    } 

} 

SubHashMap：

class SubHashMap<K, V> extends HashMap<K, V> { 

    public void dumpBuckets() throws Exception { 

     Field f = HashMap.class.getDeclaredField("table"); 
     f.setAccessible(true); 

     Map.Entry<K, V>[] table = (Map.Entry<K, V>[]) f.get(this); 

     Class<?> hashMapEntryClass = null; 
     for (Class<?> c : HashMap.class.getDeclaredClasses()) 
      if ("java.util.HashMap.Entry".equals(c.getCanonicalName())) 
       hashMapEntryClass = c; 

     Field nextField = hashMapEntryClass.getDeclaredField("next"); 
     nextField.setAccessible(true); 

     for (int i = 0; i < table.length; i++) { 

      System.out.print("Bucket " + i + ": "); 
      Map.Entry<K, V> entry = table[i]; 

      while (entry != null) { 
       System.out.print(entry.getKey() + " "); 
       entry = (Map.Entry<K, V>) nextField.get(entry); 
      } 

      System.out.println(); 
     } 
    } 
} 

輸出：

Bucket 0: 
Bucket 1: two 
Bucket 2: 
Bucket 3: seven five 
Bucket 4: 
Bucket 5: 
Bucket 6: 
Bucket 7: one 
Bucket 8: three 
Bucket 9: 
Bucket 10: 
Bucket 11: four 
Bucket 12: zero 
Bucket 13: 
Bucket 14: eight 
Bucket 15: six 

Answer 2

沒有內在的方法來確定是否發生碰撞。您將不得不調查集合（HashMap）如何將hashCode值分發給存儲桶並自己鏡像該過程，並監視插入以跟蹤衝突。

Answer 3

你可以編寫一些反射代碼來訪問HashMap的內部桶並自己檢查它們。