HashMap : salles secrètes, magie et collisions

Imaginons une HashMap comme un château avec des pièces secrètes (seaux), où chaque pièce est précédée de portes magiques - fonctions de hachage. Comment fonctionne ce mécanisme magique et que se passe-t-il lorsque deux entités magiques entrent en collision au même endroit ? Plongeons dans le monde secret de HashMap. Tout d’abord, regardons en quoi consiste une HashMap.

Composants de base d'un HashMap

tableau de tables : ce tableau est le principal stockage de données. Chaque cellule (ou compartiment) du tableau contient un index unique, où peuvent être stockées des chaînes de valeurs ou même un arbre binaire dans le cas d'un grand nombre d'éléments.

LoadFactor : LoadFactor spécifie la quantité de remplissage d'un HashMap avant de le développer. Le facteur de charge par défaut est de 0,75, ce qui établit un équilibre entre les économies de mémoire et la vitesse d'accès. Lorsque le HashMap est plein à 75 %, il double la taille de la table et redistribue les éléments pour maintenir l'efficacité.

Seuil : le seuil est le point auquel le HashMap décide d'étendre la table. Calculé comme (capacité * loadFactor). Par exemple, si la capacité est de 16 et que loadFactor est de 0,75, alors le seuil sera de 12. Lorsque le HashMap atteint 12 éléments, il augmente sa taille.

La taille garde une trace du nombre actuel de paires clé-valeur dans le HashMap.

Chaque paire clé-valeur dans un HashMap est stockée dans une structure appelée Node contenant :

clé - clé de la paire,
valeur : la valeur de la paire,
hash - hachage calculé en fonction de la clé hashCode(),
next - un lien vers l'élément suivant de la chaîne en cas de collisions.

static class Node<K, V> implements Map.Entry<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;
    }

    ....
}

Chaque nœud est connecté au suivant dans le même compartiment en cas de collision, créant ainsi une liste chaînée. Ces listes se transforment automatiquement en un arbre binaire équilibré si plus de huit éléments s'accumulent dans le bucket.

Fonction de hachage : comment les clés trouvent leurs pièces

Imaginez que HashMap soit un immense château avec de nombreuses pièces. Chaque pièce a un numéro unique, mais comment les clés décident-elles dans quelle pièce se rendre ? C'est la tâche de la fonction de hachage, un outil magique qui permet de déterminer dans quel seau (pièce) une clé particulière sera placée.

Lorsque nous ajoutons une clé, la méthode putVal appelle la méthode hashCode() de la clé pour créer un hachage, qui est ensuite affiné pour être réparti uniformément dans les buckets.
Calcul de l'index : en utilisant la formule int index = hashCode & (length- 1) , HashMap calcule l'index qui pointe vers le bucket dans le tableau.

Ici hashCode est le code unique que la clé reçoit via la fonction de hachage. Nous effectuons ensuite une opération AND au niveau du bit sur la longueur - 1. Cela équivaut à calculer le reste du code de hachage divisé par le nombre de buckets, et nous déterminons ainsi l'index dans le tableau de buckets.

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

En conséquence, chaque clé passe par une fonction de hachage et se retrouve dans sa propre salle unique, dont l'index est calculé à l'aide du AND au niveau du bit.

Contrôle de collision : si le compartiment est vide, une nouvelle paire clé-valeur est ajoutée. Sinon, putVal vérifie si la clé correspond :

Correspondances * : la valeur est mise à jour.
*Ne correspond pas - un conflit survient - plus d'informations sur eux plus loin.

Collisions : des pièces secrètes qui s'ouvrent les unes sur les autres

Que se passe-t-il si deux clés se retrouvent dans la même pièce (plusieurs clés mènent à un seul seau) ? Dans HashMap, cela s'appelle une collision. C'est lorsque deux clés ont le même code de hachage et tentent d'accéder au même compartiment. Quand est-ce possible ? Par exemple, nous avons remplacé par erreur le code de hachage.

static class Node<K, V> implements Map.Entry<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;
    }

    ....
}

Dans cet exemple, la classe KeyWithSameHash a une méthode hashCode() remplacée qui renvoie la même valeur pour toutes les instances, ce qui fait que toutes les clés se retrouvent dans la même cellule du tableau :

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

Pour toutes les clés, la valeur hashCode() sera de 42, donc chaque fois qu'une clé est ajoutée, l'index du compartiment dans la table sera le même.

Mais au lieu de se cogner les têtes, les clés ouvrent des portes supplémentaires, transformant la pièce en un couloir magique qui mène à de nouvelles pièces. Ces nouvelles salles sont essentiellement des moyens de résoudre les collisions.

Listes liées : lorsque deux clés avec les mêmes codes de hachage se retrouvent dans le même compartiment, HashMap crée une liste chaînée dans ce compartiment. Les clés continuent d'être stockées dans cette liste, et si nécessaire, une vérification est effectuée à l'aide de la méthode equals() pour s'assurer que les clés sont bien les mêmes.

Arbres rouge-noir : lorsque le nombre de collisions dans un compartiment devient trop élevé (le couloir devient trop long), HashMap le convertit en arbre rouge-noir. Cela permet d'accélérer les recherches et d'éviter les ralentissements sous de lourdes charges.

Comment fonctionnent equals() et hashCode()

Pour que la magie HashMap fonctionne correctement, il est important que deux clés identiques avec la même valeur renvoient les mêmes codes de hachage et soient également comparées correctement à l'aide de la méthode equals(). C'est comme un sort qui vérifie si deux objets sont identiques, même s'ils peuvent être représentés de différentes manières.

hashCode() : Chaque objet doit avoir son propre code de hachage unique. Cela permet au HashMap de trouver efficacement le compartiment dans lequel la clé doit être placée.
equals() : Si deux objets ont le même code de hachage, la méthode equals() vérifie si les objets sont réellement identiques.
Si cette vérification n'était pas présente, HashMap pourrait confondre deux clés différentes, ce qui entraînerait un comportement incorrect du programme.

Conclusion

Le monde de HashMap est un monde magique où les fonctions de hachage et les collisions aident les clés à trouver leurs chambres et à garder le château en ordre. Chaque clé possède son propre chemin menant à un index unique, grâce à une fonction de hachage. Et lorsque deux clés s'entrechoquent dans le même seau, la magie continue d'opérer, ouvrant de nouvelles portes sous forme de listes chaînées ou d'arbres rouge-noir pour trouver le bon chemin.

Ainsi, grâce à hashCode(), equals() et aux couloirs de collision magiques, HashMap continue d'être l'un des outils les plus puissants de l'arsenal d'un développeur Java, garantissant efficacité et précision même dans les situations les plus confuses.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!