How can I get an indicator of the number of collisions in Java Hashmap?

Question

I am implementing a custom hash function. If I get a few collisions in a HashMap bucket, how can I find out how many items are stored in the bucket?

Answer 1

There is no direct support in the API. The member variable table used to store the buckets is not even public, so extending the class will not take you far.

Assuming you evaluate the hash functions and not do it in the production code, you can get these restrictions using reflection.

I managed to print the contents of the buckets. Analyzing distribution metrics should not be difficult from now on. Here is the code:

Test Drive:

 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(); } } } 

Output:

 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

There is no built-in way to determine if a collision has occurred. You will need to explore how the collection (HashMap) propagates hashCode values ​​in buckets and mirrors the process on its own, tracking your inserts to track conflicts.

Answer 3

You can write some reflective code to access the internal HashMap buckets and test them yourself.