Java Academy · Leçon

Fonctionnement de HashMap

Seaux, hachage et collisions

Fonctionnement de HashMap est une leçon Java Academy gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Java Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Java Academy comprend 4 leçons au total.

Ce que stocke HashMap

Une HashMap stocke des paires clé-valeur et fournit en moyenne des opérations de recherche, d’insertion et de suppression en O(1).

En interne, elle conserve un tableau appelé le tableau. Chaque emplacement de ce tableau s’appelle un compartiment.

La clé détermine dans quel compartiment une entrée est placée.
La valeur est ce que vous récupérez lorsque vous recherchez la clé.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

Hacher la clé

Lorsque vous appelez put(key, value), la table appelle key.hashCode() pour obtenir un int.

HashMap répartit ensuite ces bits à l’aide d’une fonction interne afin que même de mauvais codes de hachage se distribuent entre les compartiments.

Le nombre final est réduit avec hash & (table.length - 1) pour obtenir l’indice d’un compartiment.
La longueur du tableau est toujours une puissance de deux, de sorte que le masque fonctionne.

public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

Les compartiments en action

Chaque compartiment peut contenir plusieurs entrées. Lorsque deux clés correspondent au même compartiment, il s’agit d’une collision.

Les collisions sont normales et attendues. HashMap les gère en chaînant les entrées dans le compartiment.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

Collisions et chaînage

Avant Java 8, toutes les entrées en collision résidaient dans une liste simplement chaînée à l’intérieur du compartiment.

La recherche parcourt la liste en appelant equals() jusqu’à trouver la clé correspondante.

Peu de collisions : les performances restent effectivement en O(1).
De nombreuses collisions dans un même compartiment : les performances se dégradent vers O(n) pour ce compartiment.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

Pourquoi FB et Ea entrent en collision

Les chaînes "FB" et "Ea" ont le même hashCode() en Java. C’est un exemple classique de collision.

Même avec des codes de hachage identiques, la table les conserve séparément, car equals() permet de les distinguer dans le compartiment.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

Facteur de charge

Le facteur de charge contrôle le niveau de remplissage du tableau avant son agrandissement. La valeur par défaut est 0.75.

Avec une capacité de 16 et un facteur de charge de 0,75, le redimensionnement se déclenche à 12 entrées.
Un facteur de charge plus faible gaspille de la mémoire, mais réduit les collisions.
Un facteur de charge plus élevé économise de la mémoire, mais augmente les collisions.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

Redimensionner le tableau

Lorsque le nombre d’entrées dépasse capacity * loadFactor, le tableau double de taille.

Chaque entrée existante est rehachée dans le nouveau tableau plus grand. Cette opération est coûteuse, il est donc important de préallouer la capacité pour les grandes tables.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

Préallouer pour de meilleures performances

Si vous connaissez approximativement le nombre d’entrées à stocker, indiquez une capacité initiale pour éviter les redimensionnements répétés.

Règle générale : capacité initiale = expectedSize / 0.75 + 1.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

Clés et valeurs nulles

HashMap autorise une seule clé null et plusieurs valeurs null.

La clé null va toujours dans le compartiment 0 (son hachage est considéré comme égal à 0).
Utilisez getOrDefault pour éviter toute ambiguïté entre une clé absente et une valeur null.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

L’ordre d’itération n’est pas garanti

HashMap ne fait aucune promesse concernant l’ordre d’itération. Cet ordre dépend des codes de hachage et de la disposition des compartiments.

Si vous avez besoin d’un ordre prévisible, utilisez LinkedHashMap (ordre d’insertion) ou TreeMap (ordre trié).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

Résumé du chemin de get()

Une recherche suit ces étapes :

Calculez hashCode() et répartissez les bits.
Appliquez un masque pour trouver l’indice du compartiment.
Parcourez le compartiment en comparant les clés avec equals().
Retournez la valeur correspondante ou null.

Un hashCode efficace associé à un equals correct rend chaque étape rapide.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

Vérification rapide

Vérifiez votre compréhension de la façon dont HashMap trouve un compartiment.

Récapitulatif

Vous avez appris comment HashMap fonctionne en interne :

Les clés sont hachées et associées à des compartiments.
Les collisions sont gérées en chaînant les entrées dans un compartiment.
Le facteur de charge (0.75) déclenche un doublement et un nouveau hachage.
Le dimensionnement initial évite les redimensionnements coûteux, et l’ordre d’itération n’est pas garanti.

Ensuite, nous verrons pourquoi hashCode seul ne suffit pas sans un equals correct.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

Questions Fréquemment Posées

La leçon « Fonctionnement de HashMap » est-elle gratuite ?

Oui — le texte complet de « Fonctionnement de HashMap » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Java Academy, passe à CoddyKit PRO. Le cours Java Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Fonctionnement de HashMap » ?

Seaux, hachage et collisions Tu pratiques Java Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Java Academy ?

Aucune expérience préalable n'est requise. Java Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.

Combien de temps prend la leçon « Fonctionnement de HashMap » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Java Academy ?

Oui. Chaque leçon Java Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

← Retour à Java Academy