Java: chiave composta in hashmap

Question

Vorrei memorizzare un gruppo di oggetti in una mappa di hash, in cui la chiave deve essere composta da due valori di stringa. c'è un modo per ottenere questo?

Posso semplicemente concatenare le due stringhe, ma sono sicuro che c'è un modo migliore per farlo.

Answer 1

si potrebbe avere un oggetto personalizzato contenente le due stringhe:

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

Il problema è che è necessario determinare il test di uguaglianza e il codice hash per due tali oggetti.

uguaglianza potrebbe essere la partita di entrambe le stringhe e il codice hash potrebbe essere il codice hash dei membri concatenati (questo è discutibile):

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(); 
    } 
} 

Answer 2

Perché non creare un oggetto (per esempio) Pair che contiene le due stringhe come membri e quindi utilizzarlo come chiave?

ad es.

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

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

Non dimenticare equals() e hashCode(). Vedi this blog entry per ulteriori informazioni su HashMaps e chiavi, incluso uno sfondo sui requisiti di immutabilità. Se la tua chiave non è immutabile, puoi cambiare i suoi componenti e una ricerca successiva non riuscirà a individuarla (questo è il motivo per cui oggetti immutabili come String sono buoni candidati per una chiave)

Hai ragione che la concatenazione non è è l'ideale Per alcune circostanze funzionerà, ma spesso è una soluzione inaffidabile e fragile (ad esempio è AB/C una chiave diversa da A/BC?).

Answer 3

Ho un caso simile. Tutto ciò che faccio è concatenare le due stringhe separate da una tilde (~).

Così, quando il client chiama la funzione di servizio per ottenere l'oggetto dalla mappa, sembra che questo:

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

E 'semplice, ma funziona.

Answer 4

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

Answer 5

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

questo sembra essere un modo terribile per generare il hashCode: creazione di una nuova istanza di stringa ogni volta che il codice hash viene calcolato è terribile! (Anche generare l'istanza di stringa di una volta e la memorizzazione nella cache il risultato è pratica poveri.)

Ci sono un sacco di suggerimenti qui:

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; 
} 

Per un paio di stringhe, che diventa:

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

Questa è un'implementazione molto semplice. Un sacco di consigli attraverso il link per suggerire strategie meglio sintonizzate.

Answer 6

Vedo che molte persone utilizzano mappe nidificate. Vale a dire, per mappare Key1 -> Key2 -> Value (io uso la notazione di haskell informatico/alias per la mappatura (Key1 x Key2) -> Value che ha due argomenti e produce un valore), prima fornisci la prima chiave - questo ti restituisce uno (partial) mapKey2 -> Value, che si dispiega nel passo successivo.

Per esempio,

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) 
} 

non sono sicuro che sia meglio o non oltre la piana di costruzione chiave composita. Puoi commentare su questo.

Answer 7

Leggere sullo stack di spaguetti/cactus Mi è venuta una variante che potrebbe servire a questo scopo, inclusa la possibilità di mappare le chiavi in ​​qualsiasi ordine in modo che map.lookup ("a", "b") e mappa .lookup ("b", "a") restituisce lo stesso elemento. Funziona anche con qualsiasi numero di chiavi, non solo due.

Io lo uso come una pila per sperimentare con la programmazione del flusso di dati, ma qui è una versione veloce e sporca che funziona come una mappa multi chiave (dovrebbe essere migliorata: set invece di array per evitare la ricerca di occorrenze duplicate di una chiave)

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 
    } 
} 

Answer 8

Non è necessario reinventare la ruota. È sufficiente utilizzare l'implementazione HashBasedTable<R,C,V> diper l'interfaccia Guava, in base alle proprie esigenze. Ecco un esempio

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 

Felice codifica!