Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Apprendre Utilisation de HashMap en Java | Maîtriser Map en Java
Structures de Données Java

bookUtilisation de HashMap en Java

Examinons maintenant de plus près la classe qui implémente l’interface Map — HashMap.

Cette classe est couramment utilisée lorsqu’on parle de maps. Vous avez déjà eu l’occasion de travailler avec cette classe et d’étudier ses méthodes. Mais découvrons comment cette classe fonctionne réellement.

Tout d’abord, il est nécessaire de comprendre ce qu’est un code de hachage, car il est utilisé en interne dans une HashMap.

Code de hachage

Chaque objet possède son propre code de hachage, qui peut être obtenu à l’aide de la méthode Object de la classe hashCode(). Examinons un exemple :

Main.java

Main.java

copy

              
123456789

            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

Comme vous pouvez le constater, l’objet String contenant les données "Hello World!" possède un code de hachage de "-969099747". La méthode qui détermine précisément quel code de hachage sera redéfini dans la classe String est la suivante :

Main.java

Main.java

copy

              
1234567

            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

L'objet String est converti en un tableau d'octets à l'aide de la méthode getBytes(), après quoi chaque octet est traité et ajouté au code de hachage. De cette manière, le code de hachage devient maximalement unique, ce qui aide le programme à identifier cet objet.

Pour les objets de classes personnalisées, il est également possible de surcharger le code de hachage en définissant une méthode unique permettant aux objets d'obtenir ce nombre. Créons une classe de test User et redéfinissons la méthode hash code pour celle-ci.

Main.java

Main.java

copy

              
12345678910111213141516171819202122232425262728293031

            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

Dans la classe User, il y a 2 attributs que j'ai utilisés dans la méthode hashCode(). J'ai choisi des opérations aléatoires dans la méthode hashCode() afin d'obtenir un nombre aussi aléatoire que possible, le rendant unique pour chaque objet User.

C'est précisément cela, le code de hachage. Découvrons maintenant comment il est utilisé dans une HashMap.

HashMap

Un HashMap peut être visualisé comme un tableau de compartiments. Un compartiment est une liste où un élément est stocké. Initialement, le HashMap possède 16 compartiments, ce qui correspond à la valeur de DEFAULT_INITIAL_CAPACITY.

Lorsque vous ajoutez un élément dans le HashMap à l'aide de la méthode put(), le HashMap doit déterminer dans quel compartiment spécifique placer cet élément. Il utilise pour cela une formule simple : keyValue.hashCode() & (n - 1), où n est la taille du tableau de compartiments dans le HashMap. '&' est une opération binaire AND, qui relève également de la programmation bas niveau, donc nous n'entrerons pas dans les détails.

Il est important de comprendre que le HashMap utilise le code de hachage de la valeur de la clé pour trouver le compartiment approprié. Par conséquent, il est essentiel de créer un code de hachage aussi unique que possible afin d'éviter les collisions.

Collision

Peu importe à quel point un code de hachage est unique, il peut toujours arriver que le HashMap calcule le même compartiment pour deux éléments. Dans ce cas, une collision se produit. En termes simples, une collision est une situation où deux éléments ou plus se retrouvent dans le même compartiment. Ils y sont stockés sous forme de SinglyLinkedList, que vous avez déjà implémentée.

Voici une illustration :

Une collision n'est pas souhaitable car elle affecte l'optimisation. Si vous consultez ce tableau, vous verrez que dans le meilleur des cas, le HashMap présente une complexité algorithmique constante, tandis que dans le pire des cas, elle est linéaire. Cette complexité algorithmique linéaire résulte de collisions importantes. Par conséquent, il est conseillé par les programmeurs d'utiliser des clés avec des codes de hachage aussi uniques que possible afin d'éviter les collisions.

Comment HashMap gère-t-il les collisions ?

HashMap gère également les collisions grâce au redimensionnement constant du tableau de buckets. Lorsque le nombre d’éléments atteint 75 % de la taille du tableau de buckets, HashMap déclenche un redimensionnement en doublant la taille du tableau de buckets. Ensuite, il redistribue les éléments dans les nouveaux buckets en utilisant la nouvelle valeur de n dans la formule.

Ainsi, HashMap est une structure de données hautement optimisée et est souvent utilisée comme implémentation principale de l’interface Map.

Pourquoi est-il important de connaître tout cela ?

Il s’agit d’une théorie de programmation de bas niveau importante car, lors du traitement de grands ensembles de données, les structures de données peuvent avoir un impact significatif sur les performances de l’application. Cela se produit lorsque ces structures de données sont mal utilisées.

La mauvaise utilisation des structures de données survient parce que les programmeurs ne comprennent pas comment ces structures fonctionnent. Après tout, vous souhaitez devenir un bon programmeur, n’est-ce pas ?

De plus, des questions sur les structures de données sont souvent posées lors des entretiens.

Si vous souhaitez approfondir le fonctionnement interne de HashMap, vous pouvez consulter la documentation Java dans IntelliJ IDEA.

Dans IntelliJ IDEA, maintenez Ctrl (Windows/Linux) ou Command (macOS) enfoncé et cliquez sur le nom de la classe pour accéder à sa définition et voir toutes les méthodes disponibles.

1. Laquelle des implémentations suivantes utilise une table de hachage pour stocker des paires clé-valeur ?

2. Dans un HashMap, que se passe-t-il si deux clés ont le même code de hachage ?

question mark

Laquelle des implémentations suivantes utilise une table de hachage pour stocker des paires clé-valeur ?

Select the correct answer

question mark

Dans un HashMap, que se passe-t-il si deux clés ont le même code de hachage ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 2

Demandez à l'IA

expand

Demandez à l'IA

ChatGPT

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

bookUtilisation de HashMap en Java

Glissez pour afficher le menu

Examinons maintenant de plus près la classe qui implémente l’interface Map — HashMap.

Cette classe est couramment utilisée lorsqu’on parle de maps. Vous avez déjà eu l’occasion de travailler avec cette classe et d’étudier ses méthodes. Mais découvrons comment cette classe fonctionne réellement.

Tout d’abord, il est nécessaire de comprendre ce qu’est un code de hachage, car il est utilisé en interne dans une HashMap.

Code de hachage

Chaque objet possède son propre code de hachage, qui peut être obtenu à l’aide de la méthode Object de la classe hashCode(). Examinons un exemple :

Main.java

Main.java

copy

              
123456789

            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

Comme vous pouvez le constater, l’objet String contenant les données "Hello World!" possède un code de hachage de "-969099747". La méthode qui détermine précisément quel code de hachage sera redéfini dans la classe String est la suivante :

Main.java

Main.java

copy

              
1234567

            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

L'objet String est converti en un tableau d'octets à l'aide de la méthode getBytes(), après quoi chaque octet est traité et ajouté au code de hachage. De cette manière, le code de hachage devient maximalement unique, ce qui aide le programme à identifier cet objet.

Pour les objets de classes personnalisées, il est également possible de surcharger le code de hachage en définissant une méthode unique permettant aux objets d'obtenir ce nombre. Créons une classe de test User et redéfinissons la méthode hash code pour celle-ci.

Main.java

Main.java

copy

              
12345678910111213141516171819202122232425262728293031

            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

Dans la classe User, il y a 2 attributs que j'ai utilisés dans la méthode hashCode(). J'ai choisi des opérations aléatoires dans la méthode hashCode() afin d'obtenir un nombre aussi aléatoire que possible, le rendant unique pour chaque objet User.

C'est précisément cela, le code de hachage. Découvrons maintenant comment il est utilisé dans une HashMap.

HashMap

Un HashMap peut être visualisé comme un tableau de compartiments. Un compartiment est une liste où un élément est stocké. Initialement, le HashMap possède 16 compartiments, ce qui correspond à la valeur de DEFAULT_INITIAL_CAPACITY.

Lorsque vous ajoutez un élément dans le HashMap à l'aide de la méthode put(), le HashMap doit déterminer dans quel compartiment spécifique placer cet élément. Il utilise pour cela une formule simple : keyValue.hashCode() & (n - 1), où n est la taille du tableau de compartiments dans le HashMap. '&' est une opération binaire AND, qui relève également de la programmation bas niveau, donc nous n'entrerons pas dans les détails.

Il est important de comprendre que le HashMap utilise le code de hachage de la valeur de la clé pour trouver le compartiment approprié. Par conséquent, il est essentiel de créer un code de hachage aussi unique que possible afin d'éviter les collisions.

Collision

Peu importe à quel point un code de hachage est unique, il peut toujours arriver que le HashMap calcule le même compartiment pour deux éléments. Dans ce cas, une collision se produit. En termes simples, une collision est une situation où deux éléments ou plus se retrouvent dans le même compartiment. Ils y sont stockés sous forme de SinglyLinkedList, que vous avez déjà implémentée.

Voici une illustration :

Une collision n'est pas souhaitable car elle affecte l'optimisation. Si vous consultez ce tableau, vous verrez que dans le meilleur des cas, le HashMap présente une complexité algorithmique constante, tandis que dans le pire des cas, elle est linéaire. Cette complexité algorithmique linéaire résulte de collisions importantes. Par conséquent, il est conseillé par les programmeurs d'utiliser des clés avec des codes de hachage aussi uniques que possible afin d'éviter les collisions.

Comment HashMap gère-t-il les collisions ?

HashMap gère également les collisions grâce au redimensionnement constant du tableau de buckets. Lorsque le nombre d’éléments atteint 75 % de la taille du tableau de buckets, HashMap déclenche un redimensionnement en doublant la taille du tableau de buckets. Ensuite, il redistribue les éléments dans les nouveaux buckets en utilisant la nouvelle valeur de n dans la formule.

Ainsi, HashMap est une structure de données hautement optimisée et est souvent utilisée comme implémentation principale de l’interface Map.

Pourquoi est-il important de connaître tout cela ?

Il s’agit d’une théorie de programmation de bas niveau importante car, lors du traitement de grands ensembles de données, les structures de données peuvent avoir un impact significatif sur les performances de l’application. Cela se produit lorsque ces structures de données sont mal utilisées.

La mauvaise utilisation des structures de données survient parce que les programmeurs ne comprennent pas comment ces structures fonctionnent. Après tout, vous souhaitez devenir un bon programmeur, n’est-ce pas ?

De plus, des questions sur les structures de données sont souvent posées lors des entretiens.

Si vous souhaitez approfondir le fonctionnement interne de HashMap, vous pouvez consulter la documentation Java dans IntelliJ IDEA.

Dans IntelliJ IDEA, maintenez Ctrl (Windows/Linux) ou Command (macOS) enfoncé et cliquez sur le nom de la classe pour accéder à sa définition et voir toutes les méthodes disponibles.

1. Laquelle des implémentations suivantes utilise une table de hachage pour stocker des paires clé-valeur ?

2. Dans un HashMap, que se passe-t-il si deux clés ont le même code de hachage ?

question mark

Laquelle des implémentations suivantes utilise une table de hachage pour stocker des paires clé-valeur ?

Select the correct answer

question mark

Dans un HashMap, que se passe-t-il si deux clés ont le même code de hachage ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 2
some-alt