Czy Java ma HashMap z wyszukiwaniem wstecznym?

Mam dane zorganizowane w rodzaju „klucz-klucz”, a nie „klucz-wartość”. To jest jak HashMap, ale będę potrzebować wyszukiwania O (1) w obu kierunkach. Czy istnieje nazwa tego typu struktury danych i czy coś takiego jest zawarte w standardowych bibliotekach Javy? (a może Apache Commons?)

Mógłbym napisać własną klasę, która zasadniczo używa dwóch lustrzanych map, ale wolałbym nie wymyślać koła na nowo (jeśli to już istnieje, ale po prostu nie szukam odpowiedniego terminu).

W Java API nie ma takiej klasy. Klasa Apache Commons, którą chcesz, będzie jedną z implementacji BidiMap .

Jako matematyk nazwałbym ten rodzaj struktury bijecją.

Oprócz Apache Commons, Guava ma również BiMap .

Oto prosta klasa, której użyłem, aby to zrobić (nie chciałem mieć kolejnej zależności od strony trzeciej). Nie oferuje wszystkich funkcji dostępnych w Mapach, ale to dobry początek.

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

Jeśli nie wystąpią żadne kolizje, zawsze możesz dodać oba kierunki do tej samej HashMap :-)

Tutaj moje 2 centy.

Lub możesz użyć prostej metody z rodzajami. Bułka z masłem.

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

Oczywiście musisz mieć mapę z unikalnymi wartościami. W przeciwnym razie jeden z nich zostanie wymieniony.

Zainspirowany odpowiedzią GETah, zdecydowałem się napisać coś podobnego z kilkoma ulepszeniami:

• Klasa implementuje Map<K,V> -Interface
• Dwukierunkowość jest naprawdę gwarantowana, dbając o to podczas zmiany wartości o put(przynajmniej mam nadzieję, że to tutaj gwarantuję)

Użycie jest jak normalna mapa, aby uzyskać odwrotny widok wywołania mapowania getReverseView() . Treść nie jest kopiowana, zwracany jest tylko widok.

Nie jestem pewien, czy jest to całkowicie niezawodne (w rzeczywistości prawdopodobnie nie jest), więc nie krępuj się komentować, jeśli zauważysz jakiekolwiek wady, a zaktualizuję odpowiedź.

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

}

Dość stare pytanie, ale jeśli ktoś inny ma blokadę mózgu, tak jak ja, i natknie się na to, mam nadzieję, że to pomoże.

Ja też szukałem dwukierunkowej HashMapy, czasami jest to najprostsza z odpowiedzi, która jest najbardziej przydatna.

Jeśli nie chcesz ponownie wymyślać koła i wolisz nie dodawać innych bibliotek lub projektów do swojego projektu, co powiesz na prostą implementację tablic równoległych (lub ArrayLists, jeśli wymaga tego projekt).

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

Gdy tylko poznasz indeks jednego z dwóch kluczy, możesz łatwo zażądać drugiego. Twoje metody wyszukiwania mogą więc wyglądać następująco:

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

Zakłada się, że używasz odpowiednich struktur zorientowanych obiektowo, w których tylko metody modyfikują te tablice / ArrayLists, bardzo łatwo byłoby zachować ich równoległość. Jeszcze łatwiejsze dla ArrayList, ponieważ nie musiałbyś przebudowywać, jeśli rozmiar tablic ulegnie zmianie, o ile dodasz / usuniesz w tandemie.