如何查看HashMap中键的分布？

Question

使用哈希映射时，将键均匀分布在桶上很重要。

如果所有键都在同一个存储桶中，那么您最终会得到一个列表。

有没有办法 "audit" 在 Java 中创建一个 HashMap 以查看键的分布情况？

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

Answer 1

您可以使用反射来访问隐藏字段：

HashMap map = ...;

// get the HashMap#table field
Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);

Object[] table = (Object[]) tableField.get(map);
int[] counts = new int[table.length];

// get the HashMap.Node#next field
Class<?> entryClass = table.getClass().getComponentType();
Field nextField = entryClass.getDeclaredField("next");
nextField.setAccessible(true);

for (int i = 0; i < table.length; i++) {
    Object e = table[i];
    int count = 0;
    if (e != null) {
        do {
            count++;
        } while ((e = nextField.get(e)) != null);
    }
    counts[i] = count;
}

现在您有了每个存储桶的条目计数数组。

Answer 2

HashMap 使用键对象的 hashCode() 方法生成的键，所以我想您实际上是在问这些哈希码值的分布有多均匀。您可以使用 Map.keySet().

获取关键对象

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

检查一些示例键值对象的实际哈希码不太可能告诉您任何有用的信息，除非您的哈希计算方法非常很差。您最好对哈希码方法进行基本的理论分析。这并不像听起来那么可怕。您可以（实际上，别无选择，只能这样做）假设所提供的 Java 类的哈希码方法分布良好。然后，您只需要检查您用于组合数据成员的哈希码的方式对于数据成员的预期值是否表现良好。只有当您的数据成员具有以特殊方式高度相关的值时，这才可能成为问题。

Answer 3

Client.java

public class Client{
        public static void main(String[] args) {

            Map<Example, Number> m = new HashMap<>();
            Example e1  = new Example(100);  //point 1
            Example e2  = new Example(200);  //point2
            Example e3  = new Example(300);  //point3
            m.put(e1, 10);
            m.put(e2, 20);
            m.put(e3, 30);
            System.out.println(m);//point4
        }
    }

Example.java

public class Example {
    int s;
    Example(int s) {
        this.s =s;
    }
    @Override
    public int hashCode() {
        // TODO Auto-generated method stub
        return 5;
    }
}

现在在Client.java中的第1点、第2点和第3点，我们在hashmap m中插入了3个Example类型的键。由于 hashcode() 在 Example.java 中被覆盖，所有三个键 e1、e2、e3 都将 return 相同的哈希码，因此在 hashmap 中具有相同的桶。

现在的问题是如何查看key的分布情况

方法：

在 Client.java 的 point4 处插入一个调试点。
调试 java 应用程序。
检查 m.
在 m 中，您会发现 table 类型为 HashMap$Node 且大小为 16 的数组。
这就是字面上的散列table。每个索引都包含一个 linked 的 Entry 对象列表，这些对象被插入到 hashmap 中。每个非空索引都有一个哈希变量，对应于Hashmap的hash()方法return得到的哈希值。然后将此哈希值发送到 HashMap 的 indexFor() 方法以找出 table 数组的索引，其中将插入 Entry 对象。（请参阅@Rahul 的 link 评论中的问题以了解 hash 和 indexFor 的概念）。
对于上面的例子，如果我们检查 table，你会发现除了一个键之外的所有键都是空的。
我们插入了三个键，但我们只能看到一个，即所有三个键都已插入到同一个桶中，即 table 的相同索引。
查看table数组元素（本例为5），key对应e1，value对应10（point1）
next 这里的变量指向链表的下一个节点，即下一个条目对象，在我们的例子中是 (e2, 200)。

因此您可以通过这种方式检查哈希图。

此外，我建议您通过 hashmap 的内部实现来深入了解 HashMap。

希望对您有所帮助..

Answer 4

I tried subtyping it and iterating Entry[] table, but it's not visible

使用反射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

如何查看HashMap中键的分布？

How to see the distribution of keys in a HashMap?

java

hashmap