Java tem um hashmap com pesquisa reversa?

Question

Eu tenho dados organizados em um formato "chave-chave", em vez de "valor-chave". É como um hashmap, mas vou precisar da pesquisa O (1) em ambas as direções. Existe um nome para esse tipo de estrutura de dados e é algo assim incluído nas bibliotecas padrão do Java? (Ou talvez Apache Commons?)

Eu poderia escrever minha própria classe que basicamente usa dois mapas espelhados, mas prefiro não reinventar a roda (se isso já existir, mas não estou procurando o termo certo).

Answer 1

Não existe essa classe na API Java. A classe Apache Commons que você deseja será uma das implementações de Bidimap.

Como matemático, eu chamaria esse tipo de estrutura de bijeção.

Answer 2

Além do Apache Commons, Goiaba também tem um Bimap.

Answer 3

Aqui está uma aula simples que eu costumava fazer isso (eu não queria ter mais uma dependência de terceiros). Ele não oferece todos os recursos disponíveis nos mapas, mas é um bom começo.

    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 não ocorrerem colisões, você sempre poderá adicionar as duas direções ao mesmo hashmap :-)

Answer 5

Aqui meus 2 centavos.

Ou você pode usar um método simples com genéricos. Pedaco de bolo.

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

Claro que você deve ter um mapa com valores exclusivos. Caso contrário, um deles será substituído.

Answer 6

Uma pergunta bastante antiga aqui, mas se alguém tiver o Brain Block como eu acabei de fazer e tropeça nisso, espero que isso ajude.

Eu também estava procurando um hashmap bidirecional, às vezes é a mais simples das respostas que são as mais úteis.

Se você não deseja reinventar a roda e preferir não adicionar outras bibliotecas ou projetos ao seu projeto, que tal uma simples implementação de matrizes paralelas (ou Arraylists, se o seu design exigir).

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

Assim que você souber o índice de 1 das duas teclas, você pode solicitar facilmente o outro. Portanto, seus métodos de pesquisa podem se parecer com a mesma forma:

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

Isso supõe que você esteja usando estruturas adequadas orientadas a objetos, onde apenas métodos estão modificando essas matrizes/Arraylists, seria muito simples mantê -las paralelas. Ainda mais fácil para um Arraylist, pois você não precisaria reconstruir se o tamanho das matrizes mudar, desde que você adicione/remova em conjunto.

Answer 7

Inspirado por Resposta de Getah Decidi escrever algo semelhante sozinho com algumas melhorias:

• A classe está implementando o Map<K,V>-Interface
• A bidirecionalidade é realmente garantida, cuidando dela ao alterar um valor por um put (Pelo menos espero garantir isso por meio deste)

O uso é como um mapa normal, para obter uma visão reversa na chamada de mapeamento getReverseView(). O conteúdo não é copiado, apenas uma visualização é retornada.

Não tenho certeza se isso é totalmente à prova de idiotas (na verdade, provavelmente não é); portanto, fique à vontade para comentar se você notar alguma falha e eu atualizarei a resposta.

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

}