Verificação de existência de chave no HashMap

309

A verificação da existência de chaves no HashMap é sempre necessária?

Eu tenho um HashMap com, digamos, 1000 entradas e estou procurando melhorar a eficiência. Se o HashMap estiver sendo acessado com muita frequência, verificar a existência da chave em todos os acessos resultará em uma grande sobrecarga. Em vez disso, se a chave não estiver presente e, portanto, ocorrer uma exceção, eu posso capturar a exceção. (quando eu sei que isso acontecerá raramente). Isso reduzirá os acessos ao HashMap pela metade.

Isso pode não ser uma boa prática de programação, mas me ajudará a reduzir o número de acessos. Ou estou faltando alguma coisa aqui?

[ Update ] Não tenho valores nulos no HashMap.

athena
fonte
8
"daí e ocorre exceção" - que exceção? Esta não será a partir java.util.HashMap ...
serg10

Respostas:

513

Você já armazena um valor nulo? Caso contrário, você pode simplesmente fazer:

Foo value = map.get(key);
if (value != null) {
    ...
} else {
    // No such key
}

Caso contrário, você poderá verificar a existência se receber um valor nulo retornado:

Foo value = map.get(key);
if (value != null) {
    ...
} else {
    // Key might be present...
    if (map.containsKey(key)) {
       // Okay, there's a key but the value is null
    } else {
       // Definitely no such key
    }
}
Jon Skeet
fonte
1
@ Samuel: Somente quando nulo é um valor possível. Se você definitivamente não possui valores nulos no mapa, tudo getbem e evita fazer duas pesquisas quando você precisar do valor também.
Jon Skeet
Embora isso seja provavelmente mais claro como exemplo, você também pode escrever if(value!=null || map.containsKey(key))para a segunda parte. Pelo menos se você quiser fazer a mesma coisa de qualquer maneira - nenhum código repetido. Funcionará devido a curto-circuito .
Cullub
66

Você não ganhará nada verificando se a chave existe. Este é o código de HashMap:

@Override
public boolean containsKey(Object key) {
    Entry<K, V> m = getEntry(key);
    return m != null;
}

@Override
public V get(Object key) {
    Entry<K, V> m = getEntry(key);
    if (m != null) {
        return m.value;
    }
    return null;
}

Basta verificar se o valor de retorno para get()é diferente de null.

Este é o código fonte do HashMap.


Recursos :

Colin Hebert
fonte
2
Qual é o sentido de mostrar uma implementação específica desses métodos?
jarnbjo
2
Para explicar isso, na maioria dos casos, verificar a existência da chave levará o mesmo tempo que obter o valor. Portanto, não otimizará nada para verificar se a chave realmente existe antes de obter o valor. Eu sei que é uma generalização, mas pode ajudar a entender.
Colin Hebert
Um bom link é grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… (o OpenJDK é muito fortemente derivado do código Sun) e parece que estou errado. Eu estava comparando a versão para Java5 com Java6; eles funcionam de maneira diferente nessa área (mas ambos estão corretos, assim como os trechos que você postou).
Donal Fellows
2
Como apontado na resposta aceita, esse snawer está completamente errado. É claro que você ganha algo verificando a existência de chaves e comparando valores - é possível diferenciar chaves inexistentes de chaves que existem, mas são mapeadas para nulas como um valor.
Johannes H.
43

Melhor maneira é usar o containsKeymétodo de HashMap. Amanhã alguém adicionará nulo ao mapa. Você deve diferenciar entre presença de chave e chave com valor nulo.

Programador morto
fonte
Sim. Ou subclasse o HashMap para evitar o armazenamento nulltotal.
Robau
1
1+ para tipos primitivos como valor elenco desnecessário não é necessária usando esta resposta
Prashant Bhanarkar
Também é mais fluente escrever .containsKey () do que procurar null. Deveríamos nos preocupar mais em ser de fácil leitura, o que economiza tempo dos desenvolvedores, do que em algumas otimizações menores, na maioria dos casos. Pelo menos não otimize antes que se torne necessário.
Max
23

Você quer dizer que você tem código como

if(map.containsKey(key)) doSomethingWith(map.get(key))

por todo o lugar ? Então você deve simplesmente verificar se map.get(key)retornou nulo e é isso. A propósito, o HashMap não lança exceções para chaves ausentes, mas retorna nulo. O único caso em que containsKeyé necessário é quando você está armazenando valores nulos, para distinguir entre um valor nulo e um valor ausente, mas isso geralmente é considerado uma má prática.

jkff
fonte
8

Basta usar containsKey()para maior clareza. É rápido e mantém o código limpo e legível. O ponto principal de HashMaps é que a pesquisa de chave é rápida, apenas certifique-se de que hashCode()e equals()esteja corretamente implementada.

Mikko Wilkman
fonte
4
if(map.get(key) != null || (map.get(key) == null && map.containsKey(key)))
Erlan
fonte
3

Você também pode usar o computeIfAbsent()método na HashMapclasse

No exemplo a seguir, maparmazena uma lista de transações (números inteiros) aplicadas à chave (o nome da conta bancária). Para adicionar 2 transações de 100e 200para checking_accountvocê, escreva:

HashMap<String, ArrayList<Integer>> map = new HashMap<>();
map.computeIfAbsent("checking_account", key -> new ArrayList<>())
   .add(100)
   .add(200);

Dessa forma, você não precisa verificar se a chave checking_accountexiste ou não.

  • Se não existir, um será criado e retornado pela expressão lambda.
  • Se existir, o valor da chave será retornado por computeIfAbsent().

Realmente elegante! 👍

nazmul idris
fonte
0

Eu costumo usar o idioma

Object value = map.get(key);
if (value == null) {
    value = createValue(key);
    map.put(key, value);
}

Isso significa que você só bate no mapa duas vezes se a chave estiver faltando

Jon Freedman
fonte
0
  1. Se a classe-chave for sua, verifique se os métodos hashCode () e equals () foram implementados.
  2. Basicamente, o acesso ao HashMap deve ser O (1), mas com a implementação incorreta do método hashCode, ele se torna O (n), porque o valor com a mesma chave de hash será armazenado como lista vinculada.
Boris
fonte
0

A resposta de Jon Skeet aborda bem os dois cenários (mapa com nullvalor e não nullvalor) de maneira eficiente.

Sobre as entradas de número e a preocupação com eficiência, gostaria de acrescentar algo.

Eu tenho um HashMap com 1.000 entradas e estou procurando melhorar a eficiência. Se o HashMap estiver sendo acessado com muita frequência, verificar a existência da chave em todos os acessos resultará em uma grande sobrecarga.

Um mapa com 1.000 entradas não é um mapa enorme.
Bem como um mapa com 5.000 ou 10.000 entradas.
Mapsão projetados para fazer uma recuperação rápida com essas dimensões.

Agora, assume que hashCode()as chaves do mapa fornecem uma boa distribuição.

Se você pode usar um Integertipo de chave, faça-o.
Seu hashCode()método é muito eficiente, pois as colisões não são possíveis para intvalores únicos :

public final class Integer extends Number implements Comparable<Integer> {
    ...
    @Override
    public int hashCode() {
        return Integer.hashCode(value);
    }

    public static int hashCode(int value) {
        return value;
    }
    ...
}

Se, para a chave, você precisar usar outro tipo interno, como Stringpor exemplo, frequentemente usado Map, poderá haver algumas colisões, mas de mil a alguns milhares de objetos no Map, você deve ter muito poucos como String.hashCode()método fornece uma boa distribuição.

Se você usar um tipo personalizado, substitua hashCode()e equals()corrija e garanta que, no geral, hashCode()forneça uma distribuição justa.
Você pode consultar o item 9 do Java Effectivereferente.
Aqui está um post que detalha o caminho.

davidxxx
fonte