Hat Java eine HashMap mit Reverse Lookup?

98

Ich habe Daten, die eher in einer Art "Schlüssel-Schlüssel" -Format als in einem "Schlüssel-Wert" organisiert sind. Es ist wie eine HashMap, aber ich brauche eine O (1) -Suche 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 Karten verwendet, aber ich würde das Rad lieber nicht neu erfinden (wenn dies bereits existiert, ich aber einfach nicht nach dem richtigen Begriff suche).

Pennen
quelle

Antworten:

106

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

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

uckelman
quelle
82
Als Nicht-Mathematiker würde ich diese Art von Struktur "eine Karte nennen, mit der Sie Werte nach Schlüssel oder umgekehrt nachschlagen können"
Dónal
4
Schade, dass es keine Unterstützung für Generika gibt, scheint Guava zu tun.
Eran Medan
2
github.com/megamattron/collections-generic hat BidiMap mit generischer Unterstützung
Kenston Choi
1
@ Don "Bidi" -> "Bidirektional"
Ryvantage
3
@ Dónal Ja, aber die gesamte IT basiert auf Mathematik
Alex
75

Neben Apache Commons verfügt Guava auch über eine BiMap .

ColinD
quelle
Danke für die Information! Ich bleibe jedoch vorerst bei Apache (es sei denn, es gibt gute Gründe, dies nicht zu
tun
Ich kann keinen guten Vergleich zu Apache-Sammlungen anbieten, aber Google-Sammlungen enthalten viele nette Dinge, die meiner Meinung nach einen Blick wert wären.
ColinD
16
Ein Vorteil von Google Collections ist, dass es über Generika verfügt, Commons Collections jedoch nicht.
Mark
3
Zum Vergleich der beiden Bibliotheken siehe die Zitate in dieser Antwort: stackoverflow.com/questions/787446/… (und das Originalinterview). Das ist aus offensichtlichen Gründen voreingenommen gegenüber Google, aber trotzdem kann man mit Sicherheit sagen, dass Sie mit Google Collections heutzutage besser dran sind.
Jonik
1
Die BiMap-Verbindung ist unterbrochen. Bitte benutzen Sie diesen .
Mahsa2
20

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 Maps verfügbaren Funktionen, ist aber 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);
        }
    }
GETah
quelle
5
Sie können die Leistung von includesValue () erheblich verbessern, indem Sie sie in valueToKeyMap.containsKey (value)
JT
Ich würde diese Karte nicht so verwenden, wie sie derzeit ist, da die Bidirektionalität unterbrochen wird, wenn ein Schlüssel (oder Wert) mit einem anderen Wert (oder Schlüssel) erneut hinzugefügt wird. Dies wäre eine gültige Verwendung zum Aktualisieren einer Schlüssel-IMO.
Qw3ry
11

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

rsp
quelle
6
@ Kip: Warum? In einigen Kontexten ist dies eine absolut legitime Lösung. Hätte also zwei Hash-Maps.
Lawrence Dol
7
Nein, es ist ein hässlicher, zerbrechlicher Hack. Es erfordert die Pflege der bidirektionalen Eigenschaft bei jedem get () und put () und kann an andere Methoden übergeben werden, die die Karte ändern, ohne die bidirektionale Eigenschaft zu kennen. Vielleicht wäre es als lokale Variable in einer Methode in Ordnung, die nirgendwo übergeben wird, oder wenn sie unmittelbar nach der Erstellung nicht geändert werden kann. Aber selbst dann ist es fragil (jemand kommt vorbei und optimiert diese Funktion und bricht die Bidirektionalität auf eine Weise, die sich nicht immer sofort als Problem
herausstellt
1
@Kip, ich stimme zu, dass eine solche Verwendung innerhalb der Klasse unter Verwendung dieser Karte beibehalten werden sollte, aber Ihre letzte Bemerkung gilt nur, wenn die entsprechenden JUnit-Tests schlampig sind :-)
rsp
Wenn ich eine sehr gültige Verwendung einer solchen Implementierung darstellen darf, stellen Sie sich vor, Sie benötigen hier eine Map zum Decodieren / Codieren von Opcodes von Assembler-Anweisungen. Sie werden auch niemals den Status der Map ändern. In einer Richtung sind die Schlüssel Anweisungen, die die anderen Binärwerte verfolgen. Sie sollten also niemals Konflikte haben.
MK
Für einen kleinen Suchzweck löst dieser Hack mein Problem.
Milkersarac
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.

Fulvius
quelle
1

Inspiriert von GETahs Antwort habe ich beschlossen, selbst etwas Ähnliches mit einigen Verbesserungen zu schreiben:

  • Die Klasse implementiert das Map<K,V> -Interface
  • Die Bidirektionalität wird wirklich garantiert, indem man sich darum kümmert, wenn man einen Wert um a ändert put(zumindest hoffe ich, dies hiermit zu garantieren).

Die Verwendung erfolgt wie bei einer normalen Karte, um eine umgekehrte Ansicht des Zuordnungsaufrufs zu erhalten getReverseView() . Der Inhalt wird nicht kopiert, sondern nur eine Ansicht zurückgegeben.

Ich bin mir nicht sicher, ob dies absolut narrensicher ist (wahrscheinlich auch nicht). Sie können also gerne einen Kommentar abgeben, 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;
        }
    }

}
Qw3ry
quelle
Beachten Sie, dass dies genau wie bei BiMap und BidiMap eine Bijektion ist, bei der nicht mehrere Schlüssel mit demselben Wert zulässig sind. (getReverseView (). get (v) gibt immer nur einen Schlüssel zurück).
Donatello
Stimmt, aber OTOH ist genau das, wonach das OP gefragt hat
Qw3ry
Ich bin nicht sicher, ob er zum Ausdruck gebracht hat, dass seine Daten dieser Einschränkung entsprechen, aber es könnte trotzdem jemand anderem helfen, besser zu verstehen!
Donatello
0

Eine ziemlich alte Frage hier, aber wenn jemand anderes wie ich eine Gehirnblockade hat und darüber stolpert, hilft dies hoffentlich.

Auch ich suchte nach einer bidirektionalen HashMap, manchmal ist es die einfachste Antwort, die am nützlichsten ist.

Wenn Sie das Rad nicht neu erfinden möchten und Ihrem Projekt keine anderen Bibliotheken oder Projekte hinzufügen möchten, können Sie eine einfache Implementierung paralleler Arrays (oder ArrayLists, wenn Ihr Design dies erfordert) durchführen.

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

Sobald Sie den Index von einem der beiden Schlüssel kennen, können Sie den anderen einfach anfordern. Ihre Suchmethoden könnten also ungefähr so ​​aussehen:

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

Dies setzt voraus, dass Sie geeignete objektorientierte Strukturen verwenden, bei denen nur Methoden diese Arrays / ArrayLists ändern. Es wäre sehr einfach, sie parallel zu halten. Noch einfacher für eine ArrayList, da Sie nicht neu erstellen müssten, wenn sich die Größe der Arrays ändert, solange Sie sie gleichzeitig hinzufügen / entfernen.

ThatOneGuy
quelle
3
Sie verlieren eine wichtige Funktion von HashMaps, nämlich die O (1) -Suche. Eine Implementierung wie diese würde das Durchsuchen eines der Arrays erfordern, bis Sie den Index des gesuchten Elements finden, nämlich O (n)
Kip
Ja, das ist sehr wahr und ein ziemlich großer Nachteil. In meiner persönlichen Situation hatte ich es jedoch tatsächlich mit der Notwendigkeit einer dreidirektionalen Schlüsselliste zu tun, und ich würde immer mindestens einen der Schlüssel im Voraus kennen, sodass dies für mich persönlich kein Problem war. Vielen Dank, dass Sie darauf hingewiesen haben. Ich habe diese wichtige Tatsache anscheinend in meinem ursprünglichen Beitrag übersprungen.
ThatOneGuy