为什么我的HashMap实现比JDK慢10倍？

Question

我想知道是什么改变了我在编写代码时应该知道什么。

• 使用相同的参数和方法put()，get()而不打印
• 用于System.NanoTime()测试运行时
• 我具有1-10 INT键试图将其与10个值测试 时，所以每一个单个散列返回独特的索引，这是最优化的场景
• 基于此的HashSet实现几乎与JDK的一样快速

这里是我的简单的实现：

---

public MyHashMap(int s) { 

    this.TABLE_SIZE=s; 
    table = new HashEntry[s]; 

} 

class HashEntry { 

    int key; 
    String value; 

    public HashEntry(int k, String v) { 
     this.key=k; 
     this.value=v; 
    } 

    public int getKey() { 
     return key; 
    } 

} 



int TABLE_SIZE; 

HashEntry[] table; 

public void put(int key, String value) { 

    int hash = key % TABLE_SIZE; 

    while(table[hash] != null && table[hash].getKey() != key) 
     hash = (hash +1) % TABLE_SIZE; 

     table[hash] = new HashEntry(key, value); 
} 


public String get(int key) { 

    int hash = key % TABLE_SIZE; 

     while(table[hash] != null && table[hash].key != key) 
      hash = (hash+1) % TABLE_SIZE; 

      if(table[hash] == null) 
       return null; 
      else 
       return table[hash].value; 

} 

---

这里的风向标：

public static void main(String[] args) { 


    long start = System.nanoTime(); 

    MyHashMap map = new MyHashMap(11); 

    map.put(1,"A"); 
    map.put(2,"B"); 
    map.put(3,"C"); 
    map.put(4,"D"); 
    map.put(5,"E"); 
    map.put(6,"F"); 
    map.put(7,"G"); 
    map.put(8,"H"); 
    map.put(9,"I"); 
    map.put(10,"J"); 


    map.get(1); 
    map.get(2); 
    map.get(3); 
    map.get(4); 
    map.get(5); 
    map.get(6); 
    map.get(7); 
    map.get(8); 
    map.get(9); 
    map.get(10); 

    long end = System.nanoTime(); 

    System.out.println(end-start+" ns"); 


} 

Answer 1

如果您在HashMap类read the documentation，你看，它实现了一个散列基于的表执行的钥匙。如果映射包含不平凡数量的条目，假设在对其进行排序的“桶”之间进行合理的密钥分配，这比蛮力搜索更有效。

也就是说，基准JVM是non-trivial and easy to get wrong，如果你看到与少量条目有很大差异，它可能很容易成为基准测试错误而不是代码。

Answer 2

当它达到性能，从来没有承担一些东西。

您的假设是“基于此的我的HashSet实现几乎和JDK一样快”。不，显然不是。

这是执行性能工作时很棘手的部分：除非您已经非常准确地进行了测量，否则一切都会怀疑。更糟糕的是，你甚至测量过，并且测量结果告诉你，你的实施比较慢;而不是检查你的来源，以及你测量的东西的来源;您决定测量过程必须是错误的......