ti-enxame.com

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

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

Eu tenho um HashMap com digamos 1000 entradas e estou olhando para melhorar a eficiência. Se o HashMap está sendo acessado com muita freqüência, então verificar a existência da chave em cada acesso levará a uma grande sobrecarga. Em vez disso, se a chave não está presente e, portanto, ocorre uma exceção, eu posso pegar a exceção. (quando eu sei que isso vai acontecer raramente). Isso reduzirá os acessos ao HashMap pela metade.

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

[ Update ] Eu não tenho valores nulos no HashMap.

270
athena

Você já armazenou um valor nulo? Se não, você pode apenas fazer:

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

Caso contrário, você poderia apenas verificar existência se você obtiver 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
    }
}
466
Jon Skeet

Você não vai 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 :

63
Colin Hebert

Melhor maneira é usar o método containsKey do HashMap. Amanhã soembody adicionará null ao mapa, você deve diferenciar entre a chave lá e a chave tem valor nulo.

38
Dead Programmer

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 null e é isso. By the way, HashMap não lança exceções para as chaves em falta, ele retorna null em seu lugar. 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 prática ruim.

19
jkff

Apenas use 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() estejam adequadamente implementadas.

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

A resposta do Jon Skeet endereça bem os dois cenários (mapeie com o valor null e não o valor null) de forma eficiente.

Sobre as entradas numéricas e a preocupação com a eficiência, gostaria de acrescentar algo.

Eu tenho um HashMap com 1.000 entradas e estou olhando para melhorar A eficiência. Se o HashMap estiver sendo acessado com muita freqüência, então Verificando a existência da chave em cada acesso levará a uma sobrecarga grande .

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

Agora, presume-se que hashCode() das chaves do mapa fornece uma boa distribuição.

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

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ê tem que usar outro tipo embutido como String por exemplo, que é frequentemente usado em Map, você pode ter algumas colisões, mas de 1 mil a alguns milhares de objetos no Map, você deve ter muito poucas delas como o método String.hashCode() fornece uma boa distribuição.

Se você usar um tipo personalizado, substitua hashCode() e equals() corretamente e assegure que, em geral, hashCode() forneça uma distribuição justa.
Você pode se referir ao item 9 de Java Effective se refere a ele.
Aqui está um post que detalha o caminho.

0
davidxxx

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

0
Jon Freedman
  1. Se a classe chave é 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 errada do método hashCode, ele se torna O (n), porque o valor com a mesma chave hash será armazenado como lista Linked.
0
Boris

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

No exemplo a seguir, map armazena uma lista de transações (inteiros) que são aplicadas à chave (o nome da conta bancária). Para adicionar 2 transações de 100 e 200 a checking_account você pode escrever:

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

Desta forma, você não precisa verificar se a chave checking_account existe 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()

Muito elegante! ????

0
nazmul idris