Hat Java eine HashMap mit Reverse Lookup?

Question

Ich habe Daten, die in Form eines "Schlüssel-Schlüssel" -Formats statt "Schlüssel-Wert" organisiert sind. Es ist wie eine HashMap, aber ich brauche O (1) Lookup in beide Richtungen. Gibt es einen Namen für diese Art von Datenstruktur und ist so etwas in den Standardbibliotheken von Java enthalten? (oder vielleicht Apache Commons?)

Ich könnte meine eigene Klasse schreiben, die im Grunde zwei gespiegelte Maps verwendet, aber ich würde das Rad lieber nicht neu erfinden (wenn das bereits existiert, aber ich suche nicht nach dem richtigen Begriff) .

Answer 1

Es gibt keine solche Klasse in der Java-API. Die von Ihnen gewünschte Apache Commons-Klasse wird eine der Implementierungen von BidiMap sein.

Als Mathematiker würde ich diese Art von Struktur eine Bijektion nennen.

Answer 2

Zusätzlich zu Apache Commons hat Guava auch eine BiMap.

Answer 3

Wenn keine Kollisionen auftreten, können Sie immer in beide Richtungen zum gleichen HashMap hinzufügen :-)

Answer 4

Hier ist eine einfache Klasse, ich verwendet, um dies getan haben (ich will noch nicht Abhängigkeit weiteren Dritten haben) . Es bietet nicht alle Funktionen, die in Maps verfügbar sind, aber es ist ein guter Anfang.

public class BidirectionalMap<KeyType, ValueType>{ 
     private Map<KeyType, ValueType> keyToValueMap = new ConcurrentHashMap<KeyType, ValueType>(); 
     private Map<ValueType, KeyType> valueToKeyMap = new ConcurrentHashMap<ValueType, KeyType>(); 

     synchronized public void put(KeyType key, ValueType value){ 
      keyToValueMap.put(key, value); 
      valueToKeyMap.put(value, key); 
     } 

     synchronized public ValueType removeByKey(KeyType key){ 
      ValueType removedValue = keyToValueMap.remove(key); 
      valueToKeyMap.remove(removedValue); 
      return removedValue; 
     } 

     synchronized public KeyType removeByValue(ValueType value){ 
      KeyType removedKey = valueToKeyMap.remove(value); 
      keyToValueMap.remove(removedKey); 
      return removedKey; 
     } 

     public boolean containsKey(KeyType key){ 
      return keyToValueMap.containsKey(key); 
     } 

     public boolean containsValue(ValueType value){ 
      return keyToValueMap.containsValue(value); 
     } 

     public KeyType getKey(ValueType value){ 
      return valueToKeyMap.get(value); 
     } 

     public ValueType get(KeyType key){ 
      return keyToValueMap.get(key); 
     } 
    } 

Answer 5

Hier meine 2 Cent.

Oder Sie können eine einfache Methode mit Generika verwenden. Stück Kuchen.

public static <K,V> Map<V, K> invertMap(Map<K, V> toInvert) { 
    Map<V, K> result = new HashMap<V, K>(); 
    for(K k: toInvert.keySet()){ 
     result.put(toInvert.get(k), k); 
    } 
    return result; 
} 

Natürlich müssen Sie eine Karte mit eindeutigen Werten haben. Andernfalls wird einer von ihnen ersetzt.

Answer 6

Eine ziemlich alte Frage hier, aber wenn jemand anders Gehirnblock hat, wie ich gerade getan habe und stolpert darüber, hoffentlich wird das helfen.

Ich war auch auf der Suche nach einer bidirektionalen HashMap, manchmal ist es die einfachste der Antworten, die am nützlichsten sind.

Wenn Sie das Rad nicht neu erfinden und keine anderen Bibliotheken oder Projekte zu Ihrem Projekt hinzufügen möchten, wie wäre es mit einer einfachen Implementierung von parallelen Arrays (oder ArrayLists, wenn Ihr Design dies erfordert).

SomeType[] keys1 = new SomeType[NUM_PAIRS]; 
OtherType[] keys2 = new OtherType[NUM_PAIRS]; 

Sobald Sie den Index von 1 der zwei Schlüssel kennen, können Sie leicht den anderen anfordern. So Ihre Lookup-Methoden könnten in etwa so aussehen:

SomeType getKey1(OtherType ot); 
SomeType getKey1ByIndex(int key2Idx); 
OtherType getKey2(SomeType st); 
OtherType getKey2ByIndex(int key2Idx); 

Dies wird vorausgesetzt, Sie richtige objektorientierte Strukturen verwenden, wo nur Methoden, um diese Arrays/Arraylisten modifizieren, wäre es sehr einfach sein, sie parallel zu halten. Noch einfacher für eine ArrayList, da Sie nicht neu erstellen müssen, wenn sich die Größe der Arrays ändert, solange Sie Tandem hinzufügen/entfernen.

Answer 7

Inspiriert von GETah's answer Ich beschloss, etwas ähnliches von mir mit einigen Verbesserungen zu schreiben:

• Die Klasse setzt die Map<K,V> -Interface
• Die Bidirektionalität wirklich durch die Pflege gewährleistet ist, wenn ein Wert zu ändern durch ein put (zumindest hoffe ich es zu garantieren hiermit)

Usage wie eine normale Karte ist, einen umgekehrten Blick auf die Zuordnung Aufruf zu erhalten getReverseView(). Der Inhalt wird nicht kopiert, es wird nur eine Ansicht zurückgegeben.

Ich bin mir nicht sicher, ob dies völlig narrensicher ist (eigentlich ist es wahrscheinlich nicht), so zögern Sie nicht, zu kommentieren, wenn Sie irgendwelche Fehler bemerken, und ich werde die Antwort aktualisieren.

public class BidirectionalMap<Key, Value> implements Map<Key, Value> { 

    private final Map<Key, Value> map; 
    private final Map<Value, Key> revMap; 

    public BidirectionalMap() { 
     this(16, 0.75f); 
    } 

    public BidirectionalMap(int initialCapacity) { 
     this(initialCapacity, 0.75f); 
    } 

    public BidirectionalMap(int initialCapacity, float loadFactor) { 
     this.map = new HashMap<>(initialCapacity, loadFactor); 
     this.revMap = new HashMap<>(initialCapacity, loadFactor); 
    } 

    private BidirectionalMap(Map<Key, Value> map, Map<Value, Key> reverseMap) { 
     this.map = map; 
     this.revMap = reverseMap; 
    } 

    @Override 
    public void clear() { 
     map.clear(); 
     revMap.clear(); 
    } 

    @Override 
    public boolean containsKey(Object key) { 
     return map.containsKey(key); 
    } 

    @Override 
    public boolean containsValue(Object value) { 
     return revMap.containsKey(value); 
    } 

    @Override 
    public Set<java.util.Map.Entry<Key, Value>> entrySet() { 
     return Collections.unmodifiableSet(map.entrySet()); 
    } 

    @Override 
    public boolean isEmpty() { 
     return map.isEmpty(); 
    } 

    @Override 
    public Set<Key> keySet() { 
     return Collections.unmodifiableSet(map.keySet()); 
    } 

    @Override 
    public void putAll(Map<? extends Key, ? extends Value> m) { 
     m.entrySet().forEach(e -> put(e.getKey(), e.getValue())); 
    } 

    @Override 
    public int size() { 
     return map.size(); 
    } 

    @Override 
    public Collection<Value> values() { 
     return Collections.unmodifiableCollection(map.values()); 
    } 

    @Override 
    public Value get(Object key) { 
     return map.get(key); 
    } 

    @Override 
    public Value put(Key key, Value value) { 
     Value v = remove(key); 
     getReverseView().remove(value); 
     map.put(key, value); 
     revMap.put(value, key); 
     return v; 
    } 

    public Map<Value, Key> getReverseView() { 
     return new BidirectionalMap<>(revMap, map); 
    } 

    @Override 
    public Value remove(Object key) { 
     if (containsKey(key)) { 
      Value v = map.remove(key); 
      revMap.remove(v); 
      return v; 
     } else { 
      return null; 
     } 
    } 

}