有兩個鍵的Java Map - 解決方案的速度比較

Question

在我的程序中，我想使用兩個鍵（整數）的Map。我的第一個想法是加入到整數以某種方式的字符串，如：

String key = k1.toString()+"-"+k2.toString(); 

這個解決方案沒有看對我好：1）醜; 2）慢（處理數字作爲文本）。

我在這裏發現了其他方法在stackoverflow。它們基於將整數封裝在一個類中 - 一個目的類（MyKey）或更通用的類（Pair）。

我試圖運行一些速度測試，我的虛擬解決方案似乎是最快的。第一次拍攝後，我嘗試將轉換整數字符串封裝到一個新類（MyString）中，並針對此解決方案運行測試。

的地圖定義是：

Map<Pair<Integer,Integer>,String> map1 = new HashMap<>(); 
Map<MyKey,String> map2 = new HashMap<>(); 
Map<String,String> map3 = new HashMap<>(); 
Map<MyString,String> map4 = new HashMap<>(); 

的測試結果（跑了多次，顯得穩重）：

map: put+get=total 
    1: 52+154=206 
    2: 29+77=106 
    3: 23+49=72 
    3: 17+55=72 

用繩子解決方案更快。搜索時，字符串鍵的直接連接更快，輸入時更慢。

我的問題是：

1）爲什麼使用String的解決方案更快？ （一次調用hashCode（）？）

2）有沒有什麼理由不應該用String來解決問題？

---

其他信息：

在地圖記錄數是約6000

測試試圖獲得也爲許多unexisting鍵的值。它能改變測試結果嗎？

在我的程序中，我生成布爾[N]的排列，其中M值爲真。有一次，我得到某個N，M的結果;我想存儲它們以備再次使用。

而這就是在我的例子中使用的類的完整代碼：

class Pair<L,R> { 

    private final L left; 
    private final R right; 

    public Pair(L left, R right) { 
     this.left = left; 
     this.right = right; 
    } 

    public L getLeft() { return left; } 
    public R getRight() { return right; } 

    @Override 
    public int hashCode() { return left.hashCode()^right.hashCode(); } 

    @Override 
    public boolean equals(Object o) { 
     if (o == null) return false; 
     if (!(o instanceof Pair)) return false; 
     Pair pairo = (Pair) o; 
     return this.left.equals(pairo.getLeft()) && 
      this.right.equals(pairo.getRight()); 
    } 
    } 

    class MyKey { 
     public Integer k1; 
     public Integer k2; 

     public MyKey(Integer k1, Integer k2) { 
      this.k1 = k1; 
      this.k2 = k2; 
     } 

     @Override 
     public int hashCode() { 
      return k1.hashCode() + 17 * k2.hashCode(); 
     } 

     @Override 
     public boolean equals(Object o) { 
      if (o == this) { 
       return true; 
      } 
      if (o == null || !(o instanceof MyKey)) { 
       return false; 
      } 
      MyKey cp = MyKey.class.cast(o); 
      return k1.equals(cp.k1) && k2.equals(cp.k2); 
     } 
    } 

    class MyString { 
     private String value; 

     public MyString(Integer k1, Integer k2) { 
      value=k1+"-"+k2; 
     } 

     @Override 
     public int hashCode() { 
      return value.hashCode(); 
     } 

     @Override 
     public boolean equals(Object o) { 
      return o.equals(value); 
     } 
    } 

Answer 1

您遇到的最大問題是構建字符串或創建對象以執行查找。

解決此問題的方法是獲取Map或Map值。由於你的密鑰是原始的，你最好使用庫文件庫。 TObjectIntHashMap和TIntIntHashMap

例如

TObjectIntHashMap<TIntIntHashMap> map = ... 
int val = map.get(k1).get(k2); 

使用此方法不需要任何對象來創建鍵或值。

如果您要配對的鑰匙，你可以使用遵循

TLongIntHashMap map = ... 
int val = map.get(((long) k1 << 32) | k2); 

例如

long key = ((long) k1 << 32) | k2; 
map.adjustOrPut(key, 1, 1); // a counter for this key. 

Answer 2

這應該是最高效的雙整數鍵：

class MyKey { 
    public final int k1, k2; 
    MyKey(int k1, int k2) { this.k1 = k1; this.k2 = k2; } 
    public int hashCode() { return k1^k2; } 
    public boolean equals(Object o) { 
    MyKey that; 
    return o instanceof MyKey && (that = (MyKey)o).k1 == k1 && that.k2 == k2; 
    } 

至於你的測試結果，你應該非常小心地使用微基準。你確定你做過所有的咒語，比如熱身，GC，仔細寫出JIT無法編譯出來的代碼等等。如果不是，我熱烈推薦Google Caliper，而不是重新發明輪子。

Answer 3

2）有什麼理由不應該用String來解決問題嗎？

如果你問給定的方法：

String key = k1.toString()+"-"+k2.toString(); 

的問題是：

k1 = "a-b" 
k2 = "c" 

和

k1 = "a" 
k2 = "b-c" 

（以及類似）

具有相同的密鑰。

如果你問有關使用類：

若要解決這一問題是更加清潔的一類。因爲那時你的課關心的是實現，而不是調用者。 這意味着，如果使用「 - 」或「。」，則不必考慮。或「＃」或其他什麼是正確的，如果你想改變它，你可以在課堂上改變它。不在分散在源代碼周圍的不同位置。

哈希碼實現的正確方法取決於您的數據。 Eclipse建議採取一般方法：

@Override 
public int hashCode() { 
    final int prime = 31; 
    int result = 1; 
    result = prime * result + ((k1 == null) ? 0 : k1.hashCode()); 
    result = prime * result + ((k2 == null) ? 0 : k2.hashCode()); 
    return result; 
} 

這對我來說看起來不錯。

問題1有點複雜。這在很大程度上取決於輸入數據。

一般建議：只要您不必關心性能，就不要關心性能。這意味着，只有當解決方案太慢時，才能開始分析並改進最重要的部分。除此之外，可讀性和可維護性始終是第一個目標。