Czy Java ma HashMap z odwrotnym wyszukiwaniem?

Question

Mam dane uporządkowane według rodzaju "klucza", a nie "klucz-wartość". To jest jak HashMap, ale będę potrzebował wyszukiwania O (1) w obu kierunkach. Czy istnieje nazwa dla tego typu struktury danych i jest podobna do tej zawartej w standardowych bibliotekach Java? (a może Apache Commons?)

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

Answer 1

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

Jako matematyk nazwałabym ten rodzaj struktury biempionem.

Answer 2

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

Answer 3

Jeśli nie występują kolizje, zawsze można dodać oba kierunki do tej samej HashMap :-)

Answer 4

Oto prosty klasa użyłem, aby to zrobić (nie chcę mieć kolejną zależność osoby trzeciej) . Nie oferuje wszystkich funkcji dostępnych w Mapach, ale jest dobrym początkiem.

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

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.

Answer 6

Dość stare pytanie, ale jeśli ktoś inny ma blok mózgowy, tak jak właśnie to zrobiłem i mam nadzieję, że to pomoże.

Ja też szukałem dwukierunkowej HashMap, 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 projektu, może to być prosta implementacja równoległych tablic (lub ArrayLists, jeśli wymaga tego twoja konstrukcja).

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

Po poznaniu indeksu 1 z dwóch kluczy można łatwo zażądać drugiego. Więc wasze metody lookup mógłby wyglądać tak:

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

to zakładając używasz struktury właściwym przedmiotem zorientowany gdzie tylko metody modyfikacji tych baterii/ArrayLists, byłoby bardzo proste, aby utrzymać je równolegle. Jeszcze łatwiej dla ArrayList, ponieważ nie trzeba będzie odbudowywać, jeśli rozmiar tablic ulegnie zmianie, o ile dodasz/usuniesz w tandemie.

Answer 7

Zainspirowany GETah's answer postanowiłem napisać coś podobnego przez mnie z niektórych ulepszeń:

• Klasa realizuje Map<K,V> -Interface
• dwukierunkowość jest naprawdę gwarantowane przez dbanie o niego, gdy zmienia się wartość przez put (przynajmniej mam nadzieję, że to zagwarantuję)

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

Nie jestem pewien, czy jest to całkowicie niepoprawne (właściwie to prawdopodobnie nie jest), więc zachęcamy do komentowania, jeśli zauważysz jakieś błędy, a ja 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; 
     } 
    } 

}