How can I get a metric on the number of collisions

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's no builtin way to determine if a collision occurred. You will have to investigate how the collection (HashMap) distributes hashCode values to buckets and mirror the process yourself, monitoring your inserts to keep track of collisions.

Answer 2

you could write some reflective code to gain access to the internal buckets of the HashMap and inspect them yourself.

Answer 3

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