爲什麼我的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一樣快」。不，顯然不是。

這是執行性能工作時很棘手的部分：除非您已經非常準確地進行了測量，否則一切都會懷疑。更糟糕的是，你甚至測量過，並且測量結果告訴你，你的實施比較慢;而不是檢查你的來源，以及你測量的東西的來源;您決定測量過程必須是錯誤的......