¿Java tiene un hashmap con búsqueda inversa?

Question

Tengo datos organizados en una especie de formato de "clave clave", en lugar de "valor clave". Es como un hashmap, pero necesitaré una búsqueda o (1) en ambas direcciones. ¿Hay un nombre para este tipo de estructura de datos y se incluye algo como esto en las bibliotecas estándar de Java? (¿O tal vez Apache Commons?)

Podría escribir mi propia clase que básicamente usa dos mapas reflejados, pero prefiero no reinventar la rueda (si esto ya existe, pero no estoy buscando el término correcto).

Answer 1

No existe tal clase en la API de Java. La clase Apache Commons que desea será una de las implementaciones de Bidimap.

Como matemático, llamaría a este tipo de estructura una biyección.

Answer 2

Además de Apache Commons, Guayaba también tiene un Bimap.

Answer 3

Aquí hay una clase simple que solía hacer esto (no quería tener otra dependencia de terceros). No ofrece todas las funciones disponibles en mapas, pero es un buen comienzo.

    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 no se producen colisiones, siempre puede agregar ambas instrucciones al mismo hashmap :-)

Answer 5

Aquí mis 2 centavos.

O puede usar un método simple con genéricos. Pedazo de pastel.

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

Por supuesto, debe tener un mapa con valores únicos. De lo contrario, uno de ellos será reemplazado.

Answer 6

Una pregunta bastante antigua aquí, pero si alguien más tiene un bloqueo cerebral como lo hice y tropieza con esto, espero que esto ayude.

Yo también estaba buscando un hashmap bidireccional, a veces son las respuestas más simples las más útiles.

Si no desea reinventar la rueda y prefiere no agregar otras bibliotecas o proyectos a su proyecto, ¿qué tal una implementación simple de matrices paralelas (o listas de matrices si su diseño lo exige)?

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

Tan pronto como conozca el índice de 1 de las dos claves, puede solicitar fácilmente la otra. Entonces, tus métodos de búsqueda podrían parecerse:

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

Esto supone que está utilizando estructuras orientadas a objetos adecuadas, donde solo los métodos están modificando estas matrices/listas de matrices, sería muy simple mantenerlas paralelas. Incluso más fácil para una lista de matrices, ya que no tendría que reconstruir si el tamaño de las matrices cambia, siempre que agregue/elimine en tándem.

Answer 7

Inspirado por Respuesta de Getah Decidí escribir algo similar solo con algunas mejoras:

• La clase está implementando el Map<K,V>-Interfaz
• La bidireccionalidad está realmente garantizada al cuidarla al cambiar un valor por parte de un put (al menos espero garantizarlo por la presente)

El uso es como un mapa normal, para obtener una vista inversa de la llamada de mapeo getReverseView(). El contenido no se copia, solo se devuelve una vista.

No estoy seguro de que esto sea totalmente infalible (en realidad, probablemente no lo sea), así que siéntase libre de comentar si nota algún defecto y actualizaré la respuesta.

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

}