O Java tem um HashMap com pesquisa reversa?

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

Eu poderia escrever minha própria aula 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).

Essa classe não existe na API Java. A classe Apache Commons que você deseja será uma das implementações do BidiMap .

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

Além do Apache Commons, o Guava também possui um BiMap .

Aqui está uma classe simples que usei para fazer isso (eu não queria ter outra dependência de terceiros). Ele não oferece todos os recursos disponíveis no Maps, 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);
        }
    }

Se nenhuma colisão ocorrer, você sempre pode adicionar ambas as direções ao mesmo HashMap :-)

Aqui estão 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 únicos. Caso contrário, um deles será substituído.

Inspirado pela resposta de GETah, decidi escrever algo semelhante sozinho com algumas melhorias:

• A classe está implementando a Map<K,V>-Interface
• A bidirecionalidade é realmente garantida cuidando dela ao alterar um valor por um put(pelo menos espero garantir aqui)

O uso é como um mapa normal, para obter uma visão reversa da 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 é), então fique à vontade para comentar se notar alguma falha e 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;
        }
    }

}

Uma pergunta bem antiga aqui, mas se outra pessoa tem bloqueio cerebral como eu acabei de fazer e tropeçar nisso, espero que isso ajude.

Eu também estava procurando por um HashMap bidirecional, às vezes as respostas mais simples são as mais úteis.

Se você não deseja reinventar a roda e prefere não adicionar outras bibliotecas ou projetos ao seu projeto, que tal uma implementação simples de arrays paralelos (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 uma das duas chaves, poderá facilmente solicitar a outra. Portanto, seus métodos de pesquisa podem ser parecidos com:

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

Isso pressupõe que você está usando estruturas orientadas a objetos adequadas, onde apenas métodos estão modificando esses arrays / ArrayLists, seria muito simples mantê-los paralelos. Ainda mais fácil para um ArrayList, pois você não teria que reconstruir se o tamanho dos arrays mudasse, contanto que você adicionasse / remova em conjunto.