Vérification de l'existence des clés dans HashMap

309

La vérification de l'existence de clés dans HashMap est-elle toujours nécessaire?

J'ai un HashMap avec disons 1000 entrées et je cherche à améliorer l'efficacité. Si le HashMap est utilisé très fréquemment, la vérification de l'existence de la clé à chaque accès entraînera une surcharge importante. Au lieu de cela, si la clé n'est pas présente et qu'une exception se produit, je peux intercepter l'exception. (quand je sais que cela arrivera rarement). Cela réduira de moitié les accès au HashMap.

Ce n'est peut-être pas une bonne pratique de programmation, mais cela m'aidera à réduire le nombre d'accès. Ou est-ce que je manque quelque chose ici?

[ Mise à jour ] Je n'ai pas de valeurs nulles dans le HashMap.

athena
la source
8
"d'où et l'exception se produit" - quelle exception? Ce ne sera pas de java.util.HashMap ...
serg10

Réponses:

513

Avez-vous déjà enregistré une valeur nulle? Sinon, vous pouvez simplement faire:

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

Sinon, vous pouvez simplement vérifier l'existence si vous obtenez une valeur nulle retournée:

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
la source
1
@Samuel: Uniquement lorsque null est une valeur possible. Si vous n'avez certainement pas de valeurs nulles dans la carte, tout getva bien et évite de faire deux recherches lorsque vous en avez également besoin.
Jon Skeet
Bien que cela soit probablement plus clair à titre d'exemple, vous pouvez également écrire if(value!=null || map.containsKey(key))pour la deuxième partie. Au moins si vous voulez faire la même chose de toute façon - pas de code répété. Cela fonctionnera en raison d'un court-circuit .
Cullub
66

Vous ne gagnerez rien en vérifiant que la clé existe. C'est le code 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;
}

Vérifiez simplement si la valeur de retour de get()est différente de null.

Il s'agit du code source HashMap.


Ressources :

Colin Hebert
la source
2
Quel est l'intérêt de montrer une mise en œuvre spécifique de ces méthodes?
jarnbjo
2
Pour expliquer que dans la plupart des cas, la vérification de l'existence de la clé prendra environ le même temps que l'obtention de la valeur. Il n'optimisera donc rien pour vérifier que la clé existe réellement avant d'obtenir la valeur. Je sais que c'est une généralisation mais cela peut aider à comprendre.
Colin Hebert
Un bon lien est grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… (OpenJDK est très fortement dérivé du code Sun) et il semble que je me trompe. Je comparais la version pour Java5 avec Java6; ils fonctionnent différemment dans ce domaine (mais les deux sont corrects, tout comme les extraits que vous avez publiés).
Donal Fellows
2
Comme indiqué dans la réponse acceptée, ce snawer a tout à fait tort. Bien sûr, vous gagnez quelque chose en vérifiant l'existence de clés ou en comparant les valeurs - vous pouvez différencier les clés non existantes des clés qui existent mais sont mappées à null en tant que valeur.
Johannes
43

La meilleure façon est d'utiliser la containsKeyméthode de HashMap. Demain, quelqu'un ajoutera null à la carte. Vous devez faire la différence entre la présence de clé et la clé a une valeur nulle.

Programmeur mort
la source
Ouais. Ou sous-classer le HashMap pour éviter de les stocker tous nullensemble.
RobAu
1
1+ pour les types primitifs car une
conversion
Il est également plus fluide d'écrire .containsKey () que de rechercher null. Nous devons nous préoccuper davantage d'être facile à lire, ce qui fait gagner du temps aux développeurs, que de quelques optimisations mineures, dans la plupart des cas. Du moins pas optimiser avant qu'il ne devienne nécessaire.
Max
23

Voulez-vous dire que vous avez du code comme

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

partout ? Ensuite, vous devez simplement vérifier si map.get(key)renvoyé null et c'est tout. Soit dit en passant, HashMap ne lève pas d'exceptions pour les clés manquantes, il renvoie à la place null. Le seul cas où cela containsKeyest nécessaire est lorsque vous stockez des valeurs nulles, pour faire la distinction entre une valeur nulle et une valeur manquante, mais cela est généralement considéré comme une mauvaise pratique.

jkff
la source
8

Utilisez simplement containsKey()pour plus de clarté. C'est rapide et maintient le code propre et lisible. L'intérêt de HashMaps est que la recherche de clé est rapide, assurez-vous simplement que le hashCode()et equals()sont correctement implémentés.

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

Vous pouvez également utiliser la computeIfAbsent()méthode dans la HashMapclasse.

Dans l'exemple suivant, mapstocke une liste de transactions (entiers) qui sont appliquées à la clé (le nom du compte bancaire). Pour ajouter 2 transactions de 100et 200à checking_accountvous pouvez écrire:

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

De cette façon, vous n'avez pas à vérifier si la clé checking_accountexiste ou non.

  • S'il n'existe pas, un sera créé et renvoyé par l'expression lambda.
  • S'il existe, la valeur de la clé sera renvoyée par computeIfAbsent().

Vraiment élégant! 👍

nazmul idris
la source
0

J'utilise habituellement l'idiome

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

Cela signifie que vous n'appuyez sur la carte que deux fois si la clé est manquante

Jon Freedman
la source
0
  1. Si la classe de clé est la vôtre, assurez-vous que les méthodes hashCode () et equals () sont implémentées.
  2. Fondamentalement, l'accès à HashMap doit être O (1) mais avec une implémentation de méthode hashCode incorrecte, il devient O (n), car la valeur avec la même clé de hachage sera stockée en tant que liste liée.
Boris
la source
0

La réponse de Jon Skeet aborde bien les deux scénarios (carte avec nullvaleur et non nullvaleur) de manière efficace.

Concernant les entrées de nombres et le souci d'efficacité, je voudrais ajouter quelque chose.

J'ai un HashMap avec disons 1.000 entrées et je cherche à améliorer l'efficacité. Si le HashMap est utilisé très fréquemment, la vérification de l'existence de la clé à chaque accès entraînera une surcharge importante.

Une carte avec 1.000 entrées n'est pas une carte énorme.
Ainsi qu'une carte avec 5.000 ou 10.000 entrées.
Mapsont conçus pour permettre une récupération rapide avec de telles dimensions.

Maintenant, il suppose que hashCode()les clés de carte fournissent une bonne distribution.

Si vous pouvez utiliser un Integertype de clé as, faites-le.
Sa hashCode()méthode est très efficace car les collisions ne sont pas possibles pour des intvaleurs uniques :

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

Si pour la clé, vous devez utiliser un autre type intégré comme Stringpar exemple qui est souvent utilisé dans Map, vous pouvez avoir des collisions mais de 1 000 à quelques milliers d'objets dans le Map, vous devriez en avoir très peu comme String.hashCode()méthode fournit une bonne distribution.

Si vous utilisez un type personnalisé, remplacez hashCode()-le equals()correctement et assurez- hashCode()vous que l'ensemble fournit une distribution équitable.
Vous pouvez vous référer au point 9 de la Java Effectiveréfère.
Voici un article qui détaille le chemin.

davidxxx
la source