Java：hashmaps中的複合鍵

37

你可以有一個包含兩個字符串的自定義對象：

class StringKey { 
    private String str1; 
    private String str2; 
}

問題是，你需要確定平等試驗和兩個這樣的對象的哈希碼。

平等可能是兩個字符串匹配和哈希碼可級聯成員的哈希碼（這是有爭議的）：

class StringKey { 
    private String str1; 
    private String str2; 

    @Override 
    public boolean equals(Object obj) { 
     if(obj != null && obj instanceof StringKey) { 
      StringKey s = (StringKey)obj; 
      return str1.equals(s.str1) && str2.equals(s.str2); 
     } 
     return false; 
    } 

    @Override 
    public int hashCode() { 
     return (str1 + str2).hashCode(); 
    } 
}

來源

2012-07-28 11:38:01 Tudor

+1

由於ABC，D和AB，CD的哈希碼相同，是否有任何問題？或者平等是不同的決心呢？ – 2013-02-21 16:55:56

+1

@smackfu：這取決於。如果你有很多這樣的字符串對，這隻會是一個問題，因爲它們會散列到表中的同一個插槽，並使查找效率降低。 – Tudor 2013-02-21 18:52:17

+0

@Tudor你能想到這個解決方案比EdgeCase提供的解決方案有什麼優點嗎？它基本上只是將由代字符分隔的兩個字符串連接起來？ – Zak 2013-05-22 10:09:09

7

爲什麼不創建一個（說）Pair對象，其中包含兩個字符串作爲成員，然後使用這個作爲關鍵？

例如

public class Pair { 
    private final String str1; 
    private final String str2; 

    // this object should be immutable to reliably perform subsequent lookups 
}

不要忘了equals()和hashCode()。有關HashMap和密鑰的更多信息，請參閱this blog entry，其中包括不變性要求的背景。如果您的密鑰不是不可變的，那麼您可以更改其組件，並且隨後的查找將無法找到它（這就是爲什麼不可變對象，例如String是一個密鑰的好候選）

串聯isn不理想。在某些情況下，它會起作用，但它往往是一種不可靠和脆弱的解決方案（例如，與A/BC？不同的關鍵是AB/C？）。

來源

2012-07-28 11:36:59

+0

如果我們有很多條目（〜77,500），我們可以發現自己有散列衝突嗎？ – lolo 2017-08-29 11:38:10

4

我也有類似的情況。我所做的只是連接由波浪號（〜）分隔的兩個字符串。

因此，當客戶端調用服務功能從地圖獲取對象，它看起來像這樣：

MyObject getMyObject(String key1, String key2) { 
    String cacheKey = key1 + "~" + key2; 
    return map.get(cachekey); 
}

這很簡單，但很有效。

來源

2012-07-28 12:06:25 EdgeCase

1

public static String fakeMapKey(final String... arrayKey) { 
    String[] keys = arrayKey; 

    if (keys == null || keys.length == 0) 
     return null; 

    if (keys.length == 1) 
     return keys[0]; 

    String key = ""; 
    for (int i = 0; i < keys.length; i++) 
     key += "{" + i + "}" + (i == keys.length - 1 ? "" : "{" + keys.length + "}"); 

    keys = Arrays.copyOf(keys, keys.length + 1); 

    keys[keys.length - 1] = FAKE_KEY_SEPARATOR; 

    return MessageFormat.format(key, (Object[]) keys);}

public static string FAKE_KEY_SEPARATOR = "~"; 

 
INPUT: 
fakeMapKey("keyPart1","keyPart2","keyPart3"); 

 
OUTPUT: keyPart1~keyPart2~keyPart3

來源

2013-03-15 15:10:51

9

public int hashCode() { 
    return (str1 + str2).hashCode(); 
}

這似乎是生成的hashCode一個可怕的方式：創建一個新的字符串實例的每個哈希碼的計算時間是可怕的！（即使生成字符串實例一次和緩存結果是不良的做法。）

有很多的建議在這裏：

How do I calculate a good hash code for a list of strings?

public int hashCode() { 
    final int prime = 31; 
    int result = 1; 
    for (String s : strings) { 
     result = result * prime + s.hashCode(); 
    } 
    return result; 
}

對於一對字符串，變成：

return string1.hashCode() * 31 + string2.hashCode();

這是一個非常基本的實現。通過鏈接建議更好的調整策略提供了許多建議。

來源

2013-08-02 18:37:46

+0

「每次計算哈希代碼時都會創建一個新的字符串實例」 - hahaha，很好的發現！ – 2016-12-10 14:22:02

2

我看到很多人使用嵌套地圖。也就是說，要映射Key1 -> Key2 -> Value（我使用計算機科學/別名haskell曲線符號(Key1 x Key2) -> Value映射，它有兩個參數併產生一個值），首先提供第一個鍵 - 這將返回一個(partial) mapKey2 -> Value，您將展開下一步。

例如，

Map<File, Map<Integer, String>> table = new HashMap(); // maps (File, Int) -> Distance 

add(k1, k2, value) { 
    table2 = table1.get(k1); 
    if (table2 == null) table2 = table1.add(k1, new HashMap()) 
    table2.add(k2, value) 
} 

get(k1, k2) { 
    table2 = table1.get(k1); 
    return table2.get(k2) 
}

我不能肯定它比普通複合重點建設好是壞。您可以對此發表評論。

來源

2014-02-03 16:11:38 Val

2

閱讀關於spaguetti/cactus堆棧我想出了一個可用於此目的的變體，包括以任意順序映射鍵的可能性，以便map.lookup（「a」，「b」）和map .lookup（「b」，「a」）返回相同的元素。它也適用於任何數量的鍵，而不僅僅是兩個。

我使用它作爲數據流編程實驗的堆棧，但這裏是一個快速而髒的版本，它可以作爲多鍵映射使用（應該改進：應該使用集合而不是陣列來避免重複出現一個鍵）

public class MultiKeyMap <K,E> { 
    class Mapping { 
     E element; 
     int numKeys; 
     public Mapping(E element,int numKeys){ 
      this.element = element; 
      this.numKeys = numKeys; 
     } 
    } 
    class KeySlot{ 
     Mapping parent; 
     public KeySlot(Mapping mapping) { 
      parent = mapping; 
     } 
    } 
    class KeySlotList extends LinkedList<KeySlot>{} 
    class MultiMap extends HashMap<K,KeySlotList>{} 
    class MappingTrackMap extends HashMap<Mapping,Integer>{} 

    MultiMap map = new MultiMap(); 

    public void put(E element, K ...keys){ 
     Mapping mapping = new Mapping(element,keys.length); 
     for(int i=0;i<keys.length;i++){ 
      KeySlot k = new KeySlot(mapping); 
      KeySlotList l = map.get(keys[i]); 
      if(l==null){ 
       l = new KeySlotList(); 
       map.put(keys[i], l); 
      } 
      l.add(k); 
     } 
    } 
    public E lookup(K ...keys){ 
     MappingTrackMap tmp = new MappingTrackMap(); 
     for(K key:keys){ 
      KeySlotList l = map.get(key); 
      if(l==null)return null; 
      for(KeySlot keySlot:l){ 
       Mapping parent = keySlot.parent; 
       Integer count = tmp.get(parent); 
       if(parent.numKeys!=keys.length)continue; 
       if(count == null){ 
        count = parent.numKeys-1; 
       }else{ 
        count--; 
       } 
       if(count == 0){ 
        return parent.element; 
       }else{ 
        tmp.put(parent, count); 
       }    
      } 
     } 
     return null; 
    } 
    public static void main(String[] args) { 
     MultiKeyMap<String,String> m = new MultiKeyMap<String,String>(); 
     m.put("brazil", "yellow", "green"); 
     m.put("canada", "red", "white"); 
     m.put("USA", "red" ,"white" ,"blue"); 
     m.put("argentina", "white","blue"); 

     System.out.println(m.lookup("red","white")); // canada 
     System.out.println(m.lookup("white","red")); // canada 
     System.out.println(m.lookup("white","red","blue")); // USA 
    } 
}

來源

2014-06-04 17:14:43

2

你不需要重新發明輪子。只需使用Guava的HashBasedTable<R,C,V>執行Table<R,C,V>接口，即可滿足您的需求。這裏是一個例子

Table<String, String, Integer> table = HashBasedTable.create(); 

table.put("key-1", "lock-1", 50); 
table.put("lock-1", "key-1", 100); 

System.out.println(table.get("key-1", "lock-1")); //prints 50 
System.out.println(table.get("lock-1", "key-1")); //prints 100 

table.put("key-1", "lock-1", 150); //replaces 50 with 150

快樂的編碼！

來源

2016-07-07 10:24:30 TMtech

Java：hashmaps中的複合鍵

回答

相關問題