Java a-t-il un HashMap avec recherche inversée?

J'ai des données qui sont organisées dans une sorte de format "clé-clé", plutôt que "clé-valeur". C'est comme un HashMap, mais j'aurai besoin D'une recherche O(1) dans les deux sens. Existe-t-il un nom pour ce type de structure de données, et est-ce quelque chose comme ça inclus dans les bibliothèques standard de Java? (ou peut-être d'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 cherche pas le bon terme).

92
demandé sur Jonik 2009-11-03 23:46:40

7 réponses

Il N'y a pas une telle classe dans L'API Java. La classe Apache Commons que vous voulez sera l'une des implémentations de BidiMap .

En tant que mathématicien, j'appellerais ce genre de structure une bijection.

102
répondu uckelman 2014-02-06 13:05:57

Outre Apache Commons, Goyave a également un BiMap.

71
répondu ColinD 2011-04-15 22:02:36

Voici une classe simple que j'avais l'habitude de faire (Je ne voulais pas avoir encore une autre dépendance tierce). Il n'offre pas toutes les fonctionnalités disponibles dans les Cartes, mais c'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);
        }
    }
19
répondu GETah 2011-10-20 09:52:20

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

10
répondu rsp 2009-11-03 21:11:46

Voici mes 2 cents.

, Ou vous pouvez utiliser une méthode simple avec des 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. Sinon, l'un d'eux sera remplacé.

3
répondu Fulvius 2014-10-08 08:53:57

Une question assez ancienne ici, mais si quelqu'un d'autre a un bloc cérébral comme je viens de le faire et trébuche sur cela, j'espère que cela aidera.

Moi aussi je cherchais un HashMap bidirectionnel, parfois c'est la réponse la plus simple qui soit la plus utile.

Si vous ne souhaitez pas réinventer la roue et préférez ne pas ajouter d'autres bibliothèques ou projets à votre projet, que diriez-vous d'une simple implémentation de tableaux parallèles (ou ArrayLists si votre conception l'exige).

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

Comme dès que vous connaissez l'index de 1 des deux clés, vous pouvez facilement demander l'autre. Donc, vos méthodes de recherche pourraient ressembler à quelque chose comme:

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

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

0
répondu ThatOneGuy 2015-01-31 22:21:13

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

  • la classe implémente l'InterfaceMap<K,V>
  • la bidirectionnalité est vraiment garantie en en prenant soin lors de la modification d'une valeur par un put (au moins j'espère la garantir par la présente)

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

Je ne suis pas bien sûr, c'est totalement infaillible (en fait, ce n'est probablement pas le cas), alors n'hésitez pas à commenter si vous remarquez des défauts et je mettrai à 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;
        }
    }

}
0
répondu Qw3ry 2017-05-23 11:33:16