La classe HashMap en Java est une structure de données fondamentale, largement utilisée pour stocker des paires clé-valeur. Elle offre une performance d'accès moyenne de O(1) pour la plupart des opérations. Pour comprendre son fonctionnement et ses performances, une exploration de son code source est essentielle.

Voici un exemple d'utilisation typique de HashMap :

import java.util.HashMap;

// Code applicatif
HashMap<String, Integer> dictionnaireElements = new HashMap<>();
for (int i = 0; i < 17; i++) {
    dictionnaireElements.put("element_" + i, i + 1);
}

La Méthode put

L'ajout d'une nouvelle paire clé-valeur à une HashMap se fait via la méthode put. Cette méthode est la porte d'entrée de la logique d'insertion et s'appuie sur plusieurs composants internes :

• Node<K,V>[] table : Le tableau sous-jacent qui stocke les éléments. Chaque postiion de ce tableau est souvent appelée un "compartiment" (bucket).
• int size : Le nombre actuel d'éléments dans la carte.
• int threshold : Le nombre maximal d'éléments que la carte peut contenir avant de devoir être redimensionnée.

public V put(K key, V value) {
    // Le calcul de hachage est une étape critique pour déterminer le compartiment.
    // La méthode interne putVal gère l'insertion réelle.
    return putVal(computeHash(key), key, value, false, true);
}

// Calcule la valeur de hachage de la clé. HashMap applique une transformation
// additionnelle au hashCode original pour améliorer la distribution des bits.
static final int computeHash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

La méthode putVal est l'implémentation principale de la logique d'insertion :

/**
 * Implémente la logique d'insertion pour Map.put et les méthodes associées.
 *
 * @param hachage          La valeur de hachage de la clé.
 * @param cle              La clé à insérer.
 * @param valeur           La valeur associée à la clé.
 * @param seulementSiAbsent Si vrai, ne modifie pas une valeur existante.
 * @param evicter          Indique si la table est en cours de création.
 * @return La valeur précédente associée à la clé, ou null si aucune.
 */
final V putVal(int hachage, K cle, V valeur, boolean seulementSiAbsent, boolean evicter) {
    Node<K,V>[] tableauInterne; // Référence au tableau principal
    Node<K,V> premierNoeudCompartiment; // Le premier nœud du compartiment cible
    int capacite, indiceCompartiment;

    // Étape 1: Initialisation ou vérification du tableau
    // Si le tableau est null ou vide (première insertion), il est initialisé via resize().
    if ((tableauInterne = table) == null || (capacite = tableauInterne.length) == 0) {
        capacite = (tableauInterne = resize()).length; // Initialise le tableau avec une capacité par défaut (16).
    }

    // Étape 2: Calcul de l'indice du compartiment
    // Détermine la position dans le tableau où la clé-valeur sera stockée.
    // L'opération (capacite - 1) & hachage garantit que l'indice est dans les limites du tableau.
    indiceCompartiment = (capacite - 1) & hachage;

    // Étape 3: Gestion des collisions ou insertion directe
    // Si le compartiment est vide, le nouveau nœud est inséré directement.
    if ((premierNoeudCompartiment = tableauInterne[indiceCompartiment]) == null) {
        tableauInterne[indiceCompartiment] = newNode(hachage, cle, valeur, null);
    } else {
        // Logique de collision (liste chaînée ou arbre rouge-noir)
        // ... (omise pour concision, mais gère les cas où plusieurs clés hachent au même indice)
    }

    // Incrémente le compteur d'opérations pour détecter les modifications concurrentes.
    ++modCount;

    // Étape 4: Vérification du redimensionnement
    // Si le nombre d'éléments dépasse le seuil, un redimensionnement est déclenché.
    if (++size > threshold) {
        resize();
    }
    // Méthode de rappel (non implémentée par défaut dans HashMap)
    afterNodeInsertion(evicter);
    return null; // Retourne null dans cet exemple simplifié de putVal
}

La première fois que la méthode put est appelée, le tableau interne (table) est null. Ceci déclenche un appel à la méthode resize() pour initialiser le tableau.

La Méthode resize()

La méthode resize() est responsable de l'initialisation de la table de hachage et de son redimensionnement lorsque la capacité est atteinte. Elle joue un rôle crucial dans la gestion de la performance de HashMap.

static final int CAPACITE_INITIALE_PAR_DEFAUT = 1 << 4; // 16
static final float FACTEUR_DE_CHARGE_PAR_DEFAUT = 0.75f;

final Node<K,V>[] resize() {
    Node<K,V>[] ancienneTable = table;
    int ancienneCapacite = (ancienneTable == null) ? 0 : ancienneTable.length;
    int ancienSeuil = threshold;
    int nouvelleCapacite = 0, nouveauSeuil = 0;

    // Cas 1: La table a déjà une capacité > 0 (redimensionnement ultérieur)
    if (ancienneCapacite > 0) {
        if (ancienneCapacite >= MAXIMUM_CAPACITY) { // La capacité maximale est atteinte
            threshold = Integer.MAX_VALUE;
            return ancienneTable;
        }
        // Double la capacité et le seuil si possible
        else if ((nouvelleCapacite = ancienneCapacite << 1) < MAXIMUM_CAPACITY &&
                 ancienneCapacite >= CAPACITE_INITIALE_PAR_DEFAUT) {
            nouveauSeuil = ancienSeuil << 1; // Double le seuil
        }
    }
    // Cas 2: La table n'a pas encore été initialisée, mais un seuil initial a été défini
    else if (ancienSeuil > 0) { // La capacité initiale était placée dans le seuil
        nouvelleCapacite = ancienSeuil;
    }
    // Cas 3: Première initialisation (aucune capacité ni seuil définis)
    else { // Utilise les valeurs par défaut
        nouvelleCapacite = CAPACITE_INITIALE_PAR_DEFAUT; // Nouvelle capacité = 16
        nouveauSeuil = (int)(FACTEUR_DE_CHARGE_PAR_DEFAUT * CAPACITE_INITIALE_PAR_DEFAUT); // Nouveau seuil = 12 (0.75 * 16)
    }

    // Calcule le nouveau seuil si non défini ci-dessus (par exemple, si la nouvelleCapacite a été initialisée à partir d'un ancienSeuil)
    if (nouveauSeuil == 0) {
        float seuilCalcul = (float)nouvelleCapacite * FACTEUR_DE_CHARGE_PAR_DEFAUT;
        nouveauSeuil = (nouvelleCapacite < MAXIMUM_CAPACITY && seuilCalcul < (float)MAXIMUM_CAPACITY ?
                        (int)seuilCalcul : Integer.MAX_VALUE);
    }
    threshold = nouveauSeuil; // Met à jour le seuil global

    // Crée le nouveau tableau avec la nouvelle capacité
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] nouvelleTable = (Node<K,V>[])new Node[nouvelleCapacite];
    table = nouvelleTable; // Assigne le nouveau tableau à l'instance de HashMap

    // Étape de migration des données si l'ancienne table n'était pas vide
    if (ancienneTable != null) {
        for (int j = 0; j < ancienneCapacite; ++j) {
            Node<K,V> noeudCourant;
            if ((noeudCourant = ancienneTable[j]) != null) {
                ancienneTable[j] = null; // Libère la référence dans l'ancienne table
                if (noeudCourant.next == null) { // Si c'est un nœud unique
                    nouvelleTable[noeudCourant.hash & (nouvelleCapacite - 1)] = noeudCourant;
                } else if (noeudCourant instanceof TreeNode) { // Si c'est une structure d'arbre
                    ((TreeNode<K,V>)noeudCourant).split(this, nouvelleTable, j, ancienneCapacite);
                } else { // Si c'est une liste chaînée
                    Node<K,V> teteBasse = null, queueBasse = null;
                    Node<K,V> teteHaute = null, queueHaute = null;
                    Node<K,V> suivant;

                    // Parcours la liste chaînée du compartiment j
                    do {
                        suivant = noeudCourant.next;
                        // Le bit (hash & ancienneCapacite) détermine la nouvelle position du nœud.
                        // Si ce bit est 0, le nœud reste à son ancien indice (j) dans la nouvelle table.
                        // Si ce bit est 1, le nœud se déplace à (j + ancienneCapacite).
                        if ((noeudCourant.hash & ancienneCapacite) == 0) {
                            if (queueBasse == null) teteBasse = noeudCourant;
                            else queueBasse.next = noeudCourant;
                            queueBasse = noeudCourant;
                        } else {
                            if (queueHaute == null) teteHaute = noeudCourant;
                            else queueHaute.next = noeudCourant;
                            queueHaute = noeudCourant;
                        }
                    } while ((noeudCourant = suivant) != null);

                    // Re-insère les listes chaînées dans la nouvelle table
                    if (queueBasse != null) {
                        queueBasse.next = null;
                        nouvelleTable[j] = teteBasse;
                    }
                    if (queueHaute != null) {
                        queueHaute.next = null;
                        nouvelleTable[j + ancienneCapacite] = teteHaute;
                    }
                }
            }
        }
    }
    return nouvelleTable;
}

La migration des données lors d'un redimensionnement est particulièrement intéressante. Pour les listes chaînées, les nœuds sont redistribués dans la nouvelle table de manière efficace. Chaque nœud est examiné : selon un bit spécifique de son hachage (déterminé par (noeudCourant.hash & ancienneCapacite)), il reste à son compartiment d'origine j ou est déplacé à un nouveau compartiment j + ancienneCapacite. Cela permet de diviser chaque liste chaînée en deux nouvelles listes, évitant de re-calculer le module pour chaque élément.

Conversion de Liste Chaînée en Arbre Rouge-Noir

Pour gérer les collisions extrêmes et maintenir de bonnes performances, HashMap peut convertir une liste chaînée en un arbre rouge-noir (Red-Black Tree) si sa longueur dépasse un certain seuil.

static final int SEUIL_DE_TREEIFICATION = 8; // La liste chaînée est convertie en arbre à partir de 8 nœuds

final V putVal(int hachage, K cle, V valeur, boolean seulementSiAbsent, boolean evicter) {
    // ... (début de putVal)
    else {
        Node<K,V> noeudActuel;
        // Parcours la liste chaînée pour trouver la position ou le doublon
        for (int compteurCompartiment = 0; ; ++compteurCompartiment) {
            if ((noeudActuel = premierNoeudCompartiment.next) == null) {
                // Si on atteint la fin de la liste, ajoute le nouveau nœud
                premierNoeudCompartiment.next = newNode(hachage, cle, valeur, null);
                // Si le nombre de nœuds dans la liste atteint le seuil, convertit en arbre
                if (compteurCompartiment >= SEUIL_DE_TREEIFICATION - 1) { // -1 car compteurCompartiment est basé sur 0
                    treeifyBin(tableauInterne, hachage);
                }
                break;
            }
            if (noeudActuel.hash == hachage &&
                ((k = noeudActuel.key) == cle || (cle != null && cle.equals(k)))) {
                // Clé existante trouvée
                break;
            }
            premierNoeudCompartiment = noeudActuel; // Passe au nœud suivant
        }
    }
    // ... (fin de putVal)
}

La constante SEUIL_DE_TREEIFICATION est définie à 8. Si un compratiment contient 8 nœuds (ou plus) après une insertion et que la table est suffisamment grande, la liste chaînée de ce compartiment est convertie en un arbre rouge-noir, améliorant ainsi la complexité des opérations de O(n) à O(log n) pour ce compartiment.

Il est important de noter que HashMap est conçue pour des environnements mono-thread. Elle ne contient aucune mécanisme de synchronisation interne, la rendant non-sûre pour les threads. De plus, une fois qu'un compartiment est converti en arbre rouge-noir, HashMap ne le reconvertit pas automatiquement en liste chaînée, même si le nombre d'éléments dans ce compartiment diminue sous le seuil de treiefication.