webentwicklung-frage-antwort-db.com.de

Hat Java eine HashMap mit umgekehrter Suche?

Ich habe Daten, die in Form eines "Key-Key" -Formats organisiert sind und nicht als "Schlüsselwert". Es ist wie eine HashMap, aber ich werde nach O(1) in beiden Richtungen suchen müssen. Gibt es einen Namen für diese Art von Datenstruktur und ist so etwas in Javas Standardbibliotheken enthalten? (oder vielleicht Apache Commons?)

Ich könnte meine eigene Klasse schreiben, die im Grunde zwei gespiegelte Maps verwendet, aber ich möchte das Rad nicht neu erfinden (wenn dies bereits vorhanden ist, aber ich suche nicht nach dem richtigen Begriff).

93
Kip

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 "Bi-Schnitt" bezeichnen.

103
uckelman

Guave hat zusätzlich zu Apache Commons auch eine BiMap .

72
ColinD

Hier ist eine einfache Klasse, die ich verwendet habe, um das zu erledigen (ich wollte keine weitere Abhängigkeit von Dritten 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);
        }
    }
19
GETah

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

11
rsp

Hier meine 2 Cent.

Oder Sie können eine einfache Methode mit Generics 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. Ansonsten wird einer von ihnen ersetzt.

3
Fulvius

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

  • Die Klasse implementiert das Map<K,V>- Interface
  • Die Bidirektionalität ist wirklich garantiert, wenn Sie darauf achten, wenn Sie einen Wert durch eine put ändern (zumindest hoffe ich, dies hiermit zu garantieren).

Die Verwendung ist wie bei einer normalen Karte, um eine umgekehrte Ansicht des Mapping-Aufrufs getReverseView() zu erhalten. Der Inhalt wird nicht kopiert, es wird nur eine Ansicht zurückgegeben.

Ich bin mir nicht sicher, ob das absolut narrensicher ist (eigentlich ist es wahrscheinlich nicht), also kommentieren Sie bitte, wenn Sie irgendwelche Mängel feststellen, 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;
        }
    }

}
0
Qw3ry

Eine ziemlich alte Frage hier, aber wenn jemand anderes eine Gehirnblockade hat, wie ich es gerade getan habe und darüber stolpert, wird dies hoffentlich helfen.

Ich habe auch nach einer bidirektionalen HashMap gesucht, manchmal sind es die einfachsten Antworten, die am nützlichsten sind.

Wenn Sie das Rad nicht neu erfinden möchten 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 Entwurf dies erfordert)?.

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 den anderen leicht anfordern. Ihre Suchmethoden könnten 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 bei einer Änderung der Größe der Arrays nicht neu erstellen müssten, solange Sie sie parallel hinzufügen oder entfernen.

0
ThatOneGuy