Ha Java ha un HashMap con ricerca inversa?

Question

Non ho i dati che sono organizzati in una sorta di formato "chiave in mano", piuttosto che "chiave-valore". E 'come un HashMap, ma avrà bisogno di O (1) ricerca in entrambe le direzioni. C'è un nome per questo tipo di struttura dati, ed è nulla di simile incluso nel librerie standard di Java? (O forse Apache Commons?)

ho potuto scrivere la mia classe che utilizza fondamentalmente due mappe a specchio, ma preferisco non reinventare la ruota (se questo esiste già, ma io non sto solo cercando il termine giusto).

Answer 1

Non esiste una classe nell'API Java. La classe Apache Commons si desidera sta per essere una delle implementazioni di BidiMap .

Come matematico, che definirei questo tipo di struttura una biiezione.

Answer 2

Oltre a Apache Commons, Guava ha anche un BiMap .

Answer 3

Ecco una semplice classe che ho usato per ottenere questo fatto (non ho voglia di avere ancora un altro terzo delle dipendenze parti). Non offre tutte le funzionalità disponibili in Maps, ma è un buon inizio.

    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

Se non si verificano le collisioni, è sempre possibile aggiungere entrambe le direzioni per lo stesso HashMap: -)

Answer 5

Ecco i miei 2 centesimi.

In alternativa è possibile utilizzare un metodo semplice con i generici. Pezzo di torta.

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

Naturalmente è necessario disporre di una mappa con valori univoci. In caso contrario, sarà sostituito uno di loro.

Answer 6

Piuttosto una vecchia questione qui, ma se qualcuno ha altro blocco cervello come ho appena fatto e si imbatte in questo, speriamo che questo sarà di aiuto.

Anche io cercavo un HashMap bi-direzionale, a volte è la più semplice delle risposte che sono più utili.

Se non si desidera re-inventare la ruota e preferisce non aggiungere altre librerie o progetti al progetto, come su di una semplice implementazione di array paralleli (o ArrayLists se il progetto lo richiede).

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

Non appena si conosce l'indice 1 dei due tasti si può facilmente chiedere all'altra. Così i vostri metodi di ricerca potrebbe sembra qualcosa di simile:

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

Ciò presuppone usi strutture oggetto proprio orientate, dove solo metodi modificano queste matrici / ArrayLists, sarebbe molto semplice per tenerli parallelo. Ancora più facile per un ArrayList dal momento che non avrebbe dovuto ricostruire se la dimensione del cambiamento array, a patto che si aggiunge / rimuovere in tandem.

Answer 7

risposta di getah ho deciso di scrivere qualcosa di simile da me con alcuni miglioramenti:

• La classe sta attuando la Map<K,V>-Interface
• La bidirezionalità è davvero garantita da prendersi cura di esso quando si cambia un valore da un put (almeno lo spero per garantire che la presente)

L'utilizzo è proprio come una mappa normale, per avere una visione inversa sul getReverseView() chiamata mappatura. Il contenuto non viene copiato, viene restituita solo una visione.

Non sono sicuro che questo è del tutto (in realtà, non è probabilmente) infallibile, quindi sentitevi liberi di commentare, se si nota la presenza di difetti e io aggiornare la risposta.

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

}