O Java tem um HashMap com pesquisa reversa?

98

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).

Kip
fonte

Respostas:

106

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.

uckelman
fonte
83
como um não matemático, eu chamaria esse tipo de estrutura de "um mapa que permite que você procure valores por chave ou
vice
4
Pena que não tem suporte para genéricos, parece que a Guava tem.
Eran Medan
2
github.com/megamattron/collections-generic tem BidiMap com suporte genérico
Kenston Choi
1
@Don "Bidi" -> "Bi-direcional"
ryvantage 02 de
3
@ Dónal Sim, mas toda a TI é baseada na matemática
Alex
75

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

ColinD
fonte
Obrigado pela informação! estou mantendo o apache por enquanto (a menos que haja alguns bons motivos para não fazê-lo?)
Kip
Não posso oferecer uma boa comparação com as coleções do Apache, mas as coleções do Google têm muitas coisas boas que acho que valem a pena dar uma olhada.
ColinD
16
Uma vantagem do Google Collections é que ele contém genéricos, ao contrário do Commons Collections.
Marcos
3
Para comparação das duas libs, consulte as citações nesta resposta: stackoverflow.com/questions/787446/… (e a entrevista original). Isso é tendencioso para o Google, por razões óbvias, mas mesmo assim acho que é seguro dizer que você está melhor com as coleções do Google hoje em dia.
Jonik
1
O link BiMap está quebrado. Por favor, use este .
Mahsa2 de
20

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);
        }
    }
GETah
fonte
5
Você irá melhorar significativamente o desempenho de containsValue () alterando-o para retornar valueToKeyMap.containsKey (value)
JT.
Eu não usaria este mapa como está atualmente, porque a bidirecionalidade quebra se uma chave (ou valor) for readicionada com um valor (ou chave) diferente, o que seria um uso válido para atualizar uma chave IMO.
Qw3ry
11

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

rsp
fonte
6
@Kip: Por quê? Em alguns contextos, esta é uma solução perfeitamente legítima. Então, seria ter dois mapas hash.
Lawrence Dol
7
não, é um hack feio e frágil. requer a manutenção da propriedade bidirecional em cada get () e put (), e pode ser passado para outros métodos que modificam o mapa sem nem mesmo saber sobre a propriedade bidirecional. talvez estivesse tudo bem como uma variável local dentro de um método que não é passado em nenhum lugar, ou se foi tornado não modificável imediatamente após a criação. mas mesmo assim, é frágil (alguém chega e ajusta essa função e quebra a bidirecionalidade de uma forma que nem sempre se mostrará imediatamente um problema)
Kip
1
@Kip, concordo que tal uso deve ser mantido interno à classe que usa aquele mapa, mas sua última observação só é verdadeira se os testes JUnit correspondentes forem desleixados :-)
rsp
Se eu puder propor um uso muito válido de tal implementação, imagine a necessidade de um mapa para decodificar / codificar opcodes de instruções em assembly aqui, você nunca mudará o estado do mapa também, em uma direção as chaves são strings de instruções de outros valores binários. Portanto, você nunca deve ter conflitos.
MK de
Para fins de pesquisa em pequena escala, esse hack resolve meu problema.
milkersarac de
5

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.

Fulvius
fonte
1

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

}
Qw3ry
fonte
note que assim como BiMap e BidiMap, esta é uma bijeção que não permite ter várias chaves com o mesmo valor. (getReverseView (). get (v) sempre retornará apenas uma chave).
Donatello,
Verdade, mas OTOH isso é exatamente o que o OP pediu
Qw3ry
Não tenho certeza se ele expressou que seus dados correspondam a essa restrição, mas de qualquer maneira, poderia ajudar alguém a entender melhor!
Donatello,
0

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.

ThatOneGuy
fonte
3
Você está perdendo um recurso importante dos HashMaps, a saber, pesquisa O (1). Uma implementação como essa exigiria a varredura em uma das matrizes até encontrar o índice do item que está procurando, que é O (n)
Kip
Sim, isso é verdade e é uma grande desvantagem. No entanto, na minha situação pessoal, eu estava lidando com a necessidade de uma lista de chaves tri-direcional e sempre saberia pelo menos uma das chaves com antecedência, então, para mim pessoalmente, isso não era um problema. Obrigado por apontar isso, porém, parece que pulei esse fato importante em meu post original.
ThatOneGuy