Как я могу получить показатель количества коллизий в 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 и проверить их самостоятельно.