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

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.

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

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 :

• Code source de HashMap Mauvais
• Code source HashMap Bon

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.

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.

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.

if(map.get(key) != null || (map.get(key) == null && map.containsKey(key)))

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! 👍

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

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.

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.