如何在HashMap中查看键的分布？

Question

使用哈希映射时,将密钥均匀分布在存储桶上非常重要.

如果所有密钥都在同一个存储桶中,那么您最终会得到一个列表.

有没有办法在Java中"审核"HashMap以查看密钥的分发情况？

我尝试对它进行子类型化并迭代Entry<K,V>[] table,但它不可见.

Answer 1

我尝试对它进行子类型化并迭代Entry []表,但它不可见

使用Reflection API!

public class Main {
    //This is to simulate instances which are not equal but go to the same bucket.
    static class A {
            @Override
            public boolean equals(Object obj) { return false;}

            @Override
            public int hashCode() {return 42; }
        }

    public static void main(String[] args) {
            //Test data  
            HashMap<A, String> map = new HashMap<A, String>(4);
            map.put(new A(), "abc");
            map.put(new A(), "def");

            //Access to the internal table  
            Class clazz = map.getClass();
            Field table = clazz.getDeclaredField("table");
            table.setAccessible(true);
            Map.Entry<Integer, String>[] realTable = (Map.Entry<Integer, String>[]) table.get(map);

            //Iterate and do pretty printing
            for (int i = 0; i < realTable.length; i++) {
                System.out.println(String.format("Bucket : %d, Entry: %s", i, bucketToString(realTable[i])));
            }
    }

    private static String bucketToString(Map.Entry<Integer, String> entry) throws Exception {
            if (entry == null) return null;
            StringBuilder sb = new StringBuilder();

            //Access to the "next" filed of HashMap$Node
            Class clazz = entry.getClass();
            Field next = clazz.getDeclaredField("next");
            next.setAccessible(true); 

            //going through the bucket
            while (entry != null) {
                sb.append(entry);
                entry = (Map.Entry<Integer, String>) next.get(entry);
                if (null != entry) sb.append(" -> ");
            }
            return sb.toString();
        }
}

最后你会在STDOUT中看到类似的东西:

 Bucket : 0, Entry: null 
 Bucket : 1, Entry: null 
 Bucket : 2, Entry: Main$A@2a=abc -> Main$A@2a=def 
 Bucket : 3, Entry: null

Answer 2

HashMap使用hashCode()密钥对象的方法产生的密钥,所以我猜你真的在问这些哈希代码值是如何均匀分布的.您可以使用获取关键对象Map.keySet().

现在,OpenJDK和Oracle的实现HashMap不直接使用密钥哈希码,而是在将它们分配到桶之前对提供的哈希值应用另一个哈希函数.但是你不应该依赖或使用这个实现细节.所以你应该忽略它.因此,您应该确保hashCode()键值的方法分布均匀.

检查某些示例键值对象的实际哈希码不太可能告诉您任何有用的内容,除非您的哈希值方法非常差.您最好对哈希码方法进行基本的理论分析.这并不像听起来那么可怕.您可能(实际上别无选择)假设所提供的Java类的哈希代码方法分布均匀.然后,您只需要检查用于组合数据成员的哈希码的方法是否适合数据成员的预期值.只有当您的数据成员具有以特殊方式高度相关的值时,这可能是一个问题.