java - 如何获得有关 Java Hashmap 上冲突次数的指标？

我正在实现一个自定义散列函数，如果我在 HashMap 存储桶中发生了多次冲突，我怎么知道存储桶中存储了多少元素？

最佳答案

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

关于java - 如何获得有关 Java Hashmap 上冲突次数的指标？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5600991/