如何获得Java Hashmap上碰撞次数的度量标准？ [英] How can I get a metric on the number of collisions on a 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（8，8）; 
 
 map.dumpBuckets（）; 
 
 
 
 
 $ b  SubHashMap： strong> 
  class SubHashMap< K，V>扩展HashMap< K，V> {
 
 public void dumpBuckets（）抛出异常{
 
 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; 
 
字段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（）; 
} 
} 
} 
  
 输出： 
 分段0：
分段1：两个
分段2：
分段3：七五五
第四桶：
第五桶：
第六桶：
第七桶：一桶
桶8：三桶
桶9：
桶10：
桶11：四桶
桶12：零
桶13：
桶14：八桶$ b桶15：六桶
  
 
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?
解决方案
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 


                        
这篇关于如何获得Java Hashmap上碰撞次数的度量标准？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！