如何评估哈希表实现？(使用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评论后更新:

至少哈希表作为"整体"是没有意义的

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

每个数据结构都是不同方法的权衡

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

您需要确定您对验证感兴趣的功能

1)put(key,value);
2)得到(关键,价值);
3)containsKey(key);
4)当哈希表中有许多条目时,以上所有内容

Answer 1

我只是做了与此类似的事情，最后我使用了Netbeans IDE中的内置分析器。您可以获得有关 CPU 和内存使用情况的真正详细信息。我最初是在 Eclipse 中编写所有代码的，但是 Netbeans 有一个导入功能，可以引入 Eclipse 项目，并且它设置一切都没有问题，如果这也可能是您的情况。

对于计时，您还可以查看Apache Commons 中的StopWatch类。这是一种更直观的跟踪目标操作时间的方法，例如：

StopWatch myMapTimer = new StopWatch();
HashMap<Integer, Integer> hashMap = new HashMap<>();

myMapTimer.start();
for (int i = 0; i < numElements; i++)
    hashMap.put(i, i);
myMapTimer.stop();

System.out.println(myMapTimer.getTime()); // time will be in milliseconds