Est-ce que Java a une table de hachage avec recherche inversée?

Question

J'ai données organisées en nature d'un format « clé clé », plutôt que « clé-valeur ». Il est comme un HashMap, mais je aurai besoin O (1) recherche dans les deux sens. Y at-il un nom pour ce type de structure de données, et est tout comme celui-ci inclus dans les bibliothèques standard de Java? (Ou peut-être Apache Commons?)

Je pourrais écrire ma propre classe qui utilise essentiellement deux cartes en miroir, mais je préfère ne pas réinventer la roue (si cela existe déjà, mais je ne suis pas la recherche du terme à droite).

Answer 1

Il n'y a pas de classe dans l'API Java. La classe Apache Commons que vous voulez va être l'une des implémentations de BidiMap .

En tant que mathématicien, je qualifierais ce type de structure une bijection.

Answer 2

En plus de Apache Commons, Goyave a également BiMap .

Answer 3

Voici une classe simple que je l'habitude d'obtenir ce fait (je ne voulais pas avoir encore une autre dépendance de tiers). Il ne propose pas toutes les fonctionnalités disponibles dans Maps, mais il est un bon début.

    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

Si aucune collision se produit, vous pouvez toujours ajouter les deux directions à la même HashMap: -)

Answer 5

Voici mes 2 cents.

Vous pouvez aussi utiliser une méthode simple avec les génériques. Morceau de gâteau.

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

Bien sûr, vous devez avoir une carte avec des valeurs uniques. Dans le cas contraire, l'un d'entre eux seront remplacés.

Answer 6

Tout à fait une vieille question, mais si quelqu'un d'autre bloc de cerveau comme je viens de le faire et bute sur ce, nous espérons que cela vous aidera.

Moi aussi, je cherchais un HashMap bidirectionnel, il est parfois le plus simple des réponses qui sont les plus utiles.

Si vous ne souhaitez pas réinventer la roue et préfèrent ne pas ajouter d'autres bibliothèques ou des projets à votre projet, que diriez-vous d'une simple mise en œuvre de réseaux parallèles (ou ArrayLists si votre conception exige).

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

Dès que vous connaissez l'indice de 1 des deux touches, vous pouvez demander facilement l'autre. Ainsi, vos méthodes de consultation pourrait ressemble à quelque chose comme:

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

Ceci suppose que vous utilisez des structures orientées objet proprement dit, où seules les méthodes modifient ces tableaux / ArrayLists, il serait très simple de les garder en parallèle. Encore plus facile pour un ArrayList puisque vous n'auriez pas à reconstruire si la taille du changement de tableaux, tant que vous ajoutez / supprimez en tandem.

Answer 7

Inspiré par réponse de getah j'ai décidé d'écrire quelque chose de similaire par moi-même avec quelques améliorations:

• La classe met en œuvre la Map<K,V>-Interface
• Le bidirectionnalité est vraiment garantie en prenant soin lors de la modification d'une valeur par un put (au moins je l'espère pour garantir par la présente)

L'utilisation est comme une carte normale, pour obtenir une vue inverse sur le getReverseView() d'appel de cartographie. Le contenu n'est pas copié, seule vue est renvoyée.

Je ne suis pas sûr que ce soit tout à fait infaillible (en fait, il est probablement pas), alors ne hésitez pas à commenter si vous remarquez des défauts et je vais mettre à jour la réponse.

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

}