Comment fonctionnent les HashMaps en Java – Mécanismes internes expliqués

Une `HashMap` est l’une des structures de données les plus couramment utilisées en Java, et elle est connue pour sa performance. Les données dans une `HashMap` sont stockées sous la forme de paires clé-valeur.

Dans cet article, je vous ferai connaître les `HashMap` en Java. Nous explorerons les opérations courantes de la `HashMap` et ensuite nous plongerons dans son fonctionnement interne. Vous aurez une idée de la fonction de hachage et comment la calcul d’index se produit. Finalement, nous verrons les complexités temporelles des opérations et touchons brièvement le comportement dans un environnement concurrent.

Qu’est-ce qu’une `HashMap` en Java ?

Une `HashMap` implémente l’interface `Map`, qui fait partie du framework de collections Java. Elle est basée sur la conception du hachage.

Le hachage est une technique qui transforme un input d’une taille arbitraire en une sortie de taille fixe en utilisant une fonction de hachage. L’output généré est appelé le code de hachage et est représenté par une valeur entière en Java. Les codes de hachage sont utilisés pour les opérations de recherche et d’enregistrement efficaces dans une `HashMap`.

Opérations Communes

Comme nous l’avons discuté plus haut, les données dans une `HashMap` sont stockées sous la forme de paires clé-valeur. La clé est un identificateur unique, et chaque clé est associée à une valeur.

Voici quelques opérations courantes supportées par une `HashMap`. Expliquons ce que ces méthodes font avec quelques exemples de code simples :

Insertion

Cette méthode insère une nouvelle paire clé-valeur dans la `HashMap`.
L’ordre d’insertion des couples clé-valeur n’est pas conservé.
Lors de l’insertion, si la clé est déjà présente, la valeur existante sera remplacée par la nouvelle valeur fournie.
Vous ne pouvez insérer qu’une seule clé nulle dans le HashMap, mais vous pouvez avoir plusieurs valeurs nulles.

La signature de la méthode pour cette opération est donnée ci-dessous, suivie d’un exemple :

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

Dans le code ci-dessus, nous avons un exemple de HashMap où nous ajoutons une clé de type String et une valeur de type Integer.

Récupération :

Récupère la valeur associée à une clé donnée.
Retourne null si la clé n’existe pas dans le HashMap.

La signature de la méthode pour cette opération est donnée ci-dessous, suivie d’un exemple :

public V get(Object key)

Integer value = map.get("apple"); // retourne 1

Dans le code ci-dessus, nous récupérons la valeur associée à la clé apple.

D’autres opérations courantes incluent :

supprimer : Supprime le couple clé-valeur pour la clé spécifiée. Il retourne null si la clé n’est pas trouvée.
containsKey : Vérifie si une clé spécifique est présente dans le HashMap.
containsValue : Vérifie si la valeur spécifiée est présente dans le HashMap.

Structure interne d’un `HashMap`

Internement, un HashMap utilise un tableau d’emplacements ou de cases. Chaque case est une liste chainée de type Node, utilisée pour représenter le couple clé-valeur du HashMap.

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

Au-dessus, vous pouvez voir la structure de la classe Node qui est utilisée pour stocker les couples clé-valeur du HashMap.

La classe Node possède les champs suivants :

hash : Se réfère au hashCode de la clé.
key : Se réfère à la clé du couple clé-valeur.
value : Se réfère à la valeur associée à la clé.
next : Agit comme une référence vers le noeud suivant.

Le HashMap est fondamentalement basé sur une implémentation de tableau de hachage, et son efficacité dépend de deux paramètres clés : la capacité initiale et le facteur de charge. Les original javadocs de la classe de tableau de hachage définissent ces deux paramètres comme suit :

La capacité est le nombre de cases dans le tableau de hachage, et la capacité initiale est simplement la capacité à laquelle le tableau de hachage est créé.
Le facteur de charge est une mesure de combien le tableau de hachage peut être rempli avant que sa capacité ne soit automatiquement augmentée.

Voyons maintenant comment les opérations de base, put et get, fonctionnent dans un HashMap.

Fonction de hachage

Lors de l’insertion (put) d’un couple clé-valeur, le HashMap calcule d’abord le code hash de la clé. Ensuite, la fonction de hachage calcule un entier pour la clé. Les classes peuvent utiliser la méthode hashCode de la classe Object ou la surcharger et fournir leur propre implémentation. (Lisez sur le contrat du code hash ici). Le code hash est ensuite soumis à une opération XOR (eXclusive OR) avec ses 16 bits supérieurs (h >>> 16) pour obtenir une distribution plus uniforme.

L’opération XOR est une opération bit à bit qui compare deux bits, aboutissant à 1 si les bits sont différents et 0 si ils sont les mêmes. Dans ce contexte, effectuer une opération bitwise XOR entre le code hash et ses 16 bits supérieurs (obtenus en utilisant l’opérateur de décalage droit non signé >>>) aide à mélanger les bits, ce qui conduit à un code hash plus uniformément réparti.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Au-dessus, vous pouvez voir la méthode statique de hachage de la classe HashMap.

L’idée est d’avoir un code hash unique pour chaque clé, mais la fonction de hachage pourrait produire le même code hash pour des clés différentes. Cela mène à une situation connue sous le nom de collision. Nous verrons comment gérer les collisions dans la prochaine section.

Calcul de l’index

Une fois que le code hash de la clé est généré, le HashMap calcule un index dans le tableau des tas pour déterminer où sera stocké le couple clé-valeur. Cela est fait en utilisant une opération ET bit à bit, qui est une manière efficace de calculer le modulo lorsque la longueur de l’array est un puissance de deux.

int index = (n - 1) & hash;

Ici, nous calculons l’index où n est la longueur du tableau de cases.

Une fois l’index calculé, la clé est ensuite stockée à cet index dans le tableau de cases. Cependant, si plusieurs clés se retrouvent avec le même index, ça cause une collision. Dans ce scénario, le HashMap traite les choses de deux façons :

Chaining/Linking : Chaque case du tableau est une liste chainée de nœuds. Si une clé existe déjà à un index particulier et une autre clé se hash en même temps à cet index, elle est ajoutée à la fin de la liste.
Treeify : Si le nombre de nœuds dépasse une certaine seuil, la liste chainée est convertie en arbre (Cela a été introduit dans Java 8).

static final int TREEIFY_THRESHOLD = 8;

C’est ce seuil qui détermine la treeification.

Par conséquent, il est essentiel d’avoir une bonne fonction de hachage qui distribue uniformément les clés dans les cases et minimise les chances de collision.

Les opérations de récupération (get) et de suppression (remove) fonctionnent de manière similaire à l’opération d’insertion (put). Voici comment ça marche :

Récupération (get) : Calcule le code de hachage en utilisant la fonction de hachage -> calcule l’index en utilisant le code de hachage -> parcourt la liste chainée ou l’arbre pour trouver le nœud avec la clé correspondante.
Suppression (remove) : Calcule le code de hachage en utilisant la fonction de hachage -> calcule l’index en utilisant le code de hachage -> supprime le noeud de la liste chainée ou de l’arbre.

Complexité temporelle

Les opérations de base d’un HashMap, telles que put, get et remove, offrent généralement une performance en temps constant de O(1), en supposant que les clés sont distribuées de manière uniforme. Dans les cas où la distribution des clés est mauvaise et que de nombreuses collisions surviennent, ces opérations peuvent se dégrader à une complexité temporelle linéaire de O(n).

Au cours de la transformation en arbre, lorsque de longues chaînes de collisions sont converties en arbres équilibrés, les opérations de recherche peuvent améliorer leur efficacité pour une complexité temporelle logarithmique de O(log n).

Synchronisation

L’implémentation de HashMap n’est pas synchronisée. Si plusieurs threads accèdent simultanément à une instance de HashMap et parcourent le map, et si l’un d’eux effectue une modification structurelle (telle que l’ajout ou la suppression d’une entrée clé-valeur) sur le map, cela entraîne une exception de type ConcurrentModificationException.

Pour éviter cela, vous pouvez créer une instance sécurisée pour la concurrence en utilisant la méthode Collections.synchronizedMap.

Conclusion

En résumé, comprendre les détails internes d’une HashMap est essentiel pour que les développeurs puissent prendre des décisions éclairées. Connaître la manière dont une clé est mappée, comment les collisions se produisent et comment éviter celles-ci permet d’utiliser la HashMap de manière efficiente et efficace.