java - 我如何评估哈希表的实现？ (引用HashMap)

Question

问题:

• 我需要比较 2 个哈希表实现(基本上是 HashMap 与另一个实现)并得出合理的结论。

• 我对 100% 的准确率不感兴趣，只是在我的估计中朝着正确的方向前进。

• 我不仅对每个操作的差异感兴趣，而且主要对哈希表作为“整体”的差异感兴趣。

• 我对速度没有严格的要求，所以如果其他实现合理慢我可以接受，但我确实期望/要求内存使用更好(因为其中一个哈希表由原始表支持)。

到目前为止我做了什么:

最初，我创建了自己的自定义“基准测试”，其中包含循环和多次提示 gc 的调用以感受差异，但我在网上阅读到使用标准工具更可靠/合适。
我的方法示例(MapInterface 只是一个包装器，因此我可以在实现之间切换。):

int[] keys = new int[10000000];
String[] values = new String[10000000];  
for(int i = 0; i < keys.length; ++i) {  
   keys[i] = i;  
   values[i] = "" + i;
}

if(operation.equals("put", keys, values)) {  
   runPutOperation(map);  
}  

public static long[] runOperation(MapInterface map, Integer[] keys, String[] values) {  
    long min = Long.MAX_VALUE;  
    long max = Long.MIN_VALUE;  
    long run = 0;  
    for(int i = 0; i < 10; ++i) {  
       long start = System.currentTimeMillis();  
       for(int i = 0; i < keys.length; ++i) {          
            map.put(keys[i], values[i]);  
        }
        long total = System.currentTimeMillis() - start;  
        System.out.println(total/1000d + " seconds");    
        if(total < min) {
            min = time;
        }
        if(total > max) {
            max = time;
         }
         run += time;  
         map = null;  
         map = createNewHashMap();
         hintsToGC();    
   }  
  return new long[] {min, max, run};
 }     


public void hintsToGC() {  
    for(int i = 0; i < 20; ++i) {
            System.out.print(". ");
            System.gc();            
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {              
                e.printStackTrace();
          }           
       } 
}


private HashMapInterface<String> createNewHashMap() {  
    if(jdk) {  
        return new JDKHashMapWrapper<String>();  
    }  
    else {
        return new AlternativeHashMapWrapper<String>();   
    }  
 }  



public class JDKHashMapWrapper implements HashMapInterface<String>  {
    HashMap<Integer, String> hashMap;         
    JDKHashMapWrapper() {   
       hashMap = new HashMap<Integer, String>();  
    }  
    public String put(Integer key, String value)  {
       return hashMap.put(key, value);  
    }  
 //etc  
}

(我想测试put、get、contains和内存利用率)
我能否确定使用我的方法可以获得合理的测量值？
如果不是，什么是最合适的工具，如何使用？

更新:
- 我还使用 SecureRandom 测试随机数(也是 ~10M 随机数)。
- 当哈希表调整大小时，我打印哈希表的逻辑大小/实际表的大小以获得负载因子

更新:
对于我的具体情况，我也对整数感兴趣，我的方法有哪些陷阱？

@dimo414 评论后更新:

Well at a minimum the hashtable as a "whole" isn't meaningful

我的意思是哈希表在运行时和内存消耗方面的各种负载下的行为。

Every data structure is a tradeoff of different methods

我同意。 我的权衡是内存改进的可接受访问惩罚

You need to identify what features you're interested in verifying

1)放(键，值);
2) 获取(键, 值);
3) 包含键(键);
4) 当哈希表中有很多条目时，以上所有

Answer 1

使用哈希表的一些关键考虑因素是“桶”分配的大小、冲突解决策略和数据的形状。本质上，哈希表获取应用程序提供的键，然后将其哈希为小于或等于分配的桶数的值。当两个键值散列到同一个桶时，实现必须解决冲突并返回正确的值。例如，每个桶都可以有一个排序的链表，然后搜索该链表。

如果您的数据恰好有很多冲突，那么您的性能将会受到影响，因为哈希表实现将花费太多时间来解决冲突。另一方面，如果你有非常多的桶，你会以牺牲内存为代价来解决碰撞问题。此外，如果条目数超过一定数量，Java 的内置 HashMap 实现将“重新散列”——我想这是一个值得避免的昂贵操作。

因为你的关键数据是1到10M的正整数，所以你的测试数据看起来不错。我还将确保针对给定测试将不同的哈希表实现初始化为相同的存储桶大小，否则这不是一个公平的比较。最后，我会在相当大的范围内改变存储桶大小，然后重新运行测试以查看实现如何改变它们的行为。