How can I get a metric on the number of collisions on a Java Hashmap?

Question

I'm implementing a custom hash function, If I get a number of collisions into a HashMap bucket, how can I know how many elements are stored in the bucket?

Answer 1

There is no direct support for this in the API. The member variable table, used for storing the buckets, is not even public, so extending the class won't get you far.

Assuming you're evaluating hash functions and not doing this in production code, you can get passed these constraints using reflection.

I managed to print the content of the buckets. To analyze the distribution metrics shouldn't be hard from this point. Here's the code:

Test driver:

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