Hat Java eine Hashmap mit umgekehrter Suche?

Question

Ich habe Daten, die in einer Art "Schlüsselschlüssel" -Format organisiert sind und nicht in einem "Schlüsselwert". Es ist wie ein Hashmap, aber ich werde O (1) in beide Richtungen suchen. Gibt es einen Namen für diese Art von Datenstruktur und ist so etwas wie diese in den Standardbibliotheken von Java enthalten? (oder vielleicht Apache Commons?)

Ich könnte meine eigene Klasse schreiben, die im Grunde genommen zwei gespiegelte Karten verwendet, aber ich würde das Rad lieber nicht neu erfinden (wenn dies bereits existiert, aber ich suche einfach 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 sein Bidimap.

Als Mathematiker würde ich diese Art von Struktur als Bijection bezeichnen.

Answer 2

Zusätzlich zu Apache Commons, Guave hat auch a Bimap.

Answer 3

Hier ist eine einfache Klasse, mit der ich dies erledigt habe (ich wollte keine weitere Abhängigkeit von Drittanbietern haben). Es bietet nicht alle in Karten erhältlichen Funktionen, ist jedoch 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 4

Wenn keine Kollisionen auftreten, können Sie immer beide Richtungen zu demselben HashMap hinzufügen :-)

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 anderes einen Gehirnblock hat, wie ich es gerade getan habe und darüber stolpert, wird dies hoffentlich helfen.

Auch ich suchte nach einer bidirektionalen Hashmap, manchmal ist es die einfachste Antworten, die am nützlichsten sind.

Wenn Sie das Rad nicht neu erfinden möchten und es vorziehen möchten, andere Bibliotheken oder Projekte zu Ihrem Projekt hinzuzufügen, wie wäre es mit einer einfachen Implementierung paralleler Arrays (oder Arraylisten, wenn Ihr Design es verlangt).

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

Sobald Sie den Index von 1 der beiden Schlüssel kennen, können Sie leicht den anderen anfordern. Ihre Lookup -Methoden könnten also aussehen wie:

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

Dies setzt voraus, dass Sie ordnungsgemäße objektorientierte Strukturen verwenden. Wenn nur Methoden diese Arrays/Arraylisten ändern, wäre es sehr einfach, sie parallel zu halten. Noch einfacher für eine ArrayList, da Sie nicht wieder aufbauen müssen, wenn sich die Größe der Arrays ändert, solange Sie das Tandem hinzufügen/entfernen.

Answer 7

Inspiriert von Getahs Antwort Ich beschloss, mit einigen Verbesserungen etwas Ähnliches zu schreiben:

• Die Klasse implementiert die Map<K,V>-Schnittstelle
• Die Bidirektionalität wird wirklich garantiert, indem sie sich darum kümmert, wenn ein Wert durch a geändert wird put (Zumindest hoffe ich, es hiermit zu garantieren)

Die Verwendung ist genau wie eine normale Karte, um eine umgekehrte Ansicht auf den Mapping -Anruf zu erhalten getReverseView(). Der Inhalt wird nicht kopiert, nur eine Ansicht wird zurückgegeben.

Ich bin mir nicht sicher, ob dies total narrensicher ist (eigentlich ist es wahrscheinlich nicht). Sie können also gerne kommentieren, wenn Sie 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;
        }
    }

}