Introduction au fonctionnement des Maps en Java

La classe HashMap est une structure de données fondamentale en Java, omniprésente dans le développement d'applications pour la gestion des paires clé-valeur. À partir de JDK 1.8, des optimisations significatives ont été introduites dans son implémentation sous-jacente, notamment l'intégration des arbres rouges-noirs et une gestion améliorée de l'agrandissement. Cet article explore en détail les mécanismes de HashMap, en soulignant les différences clés entre JDK 1.7 et JDK 1.8.

L'interface java.util.Map définit le contrat pour les structures de mappage en Java. Parmi ses implémentations les plus courantes, on trouve HashMap, Hashtable, LinkedHashMap et TreeMap. Voici un aperçu de leurs spécificités:

• HashMap : Cette implémentation utilise les codes de hachage des clés pour stocker les données, permettant une récupération rapide dans la plupart des cas. L'ordre d'itération n'est pas garanti. HashMap autorise une seule clé null et plusieurs valeurs null. Elle n'est pas thread-safe, ce qui signifie que des accès concurrents en écriture peuvent entraîner des incohérences. Pour un usage sécurisé en environnement multithread, Collections.synchronizedMap() ou, de préférence, ConcurrentHashMap doivent être utilisés.
• Hashtable : Classe héritée, Hashtable offre des fonctionnalités similaires à HashMap mais est synchronisée et donc thread-safe. Sa performance en concurrence est inférieure à celle de ConcurrentHashMap, qui utilise un mécanisme de verrouillage plus granulaire. Hashtable ne permet pas de clés ou de valeurs null. Son utilisation est déconseillée dans les nouvelles applications au profit de HashMap pour des contextes non-thread-safe ou ConcurrentHashMap pour des contextes thread-safe.
• LinkedHashMap : Une sous-classe de HashMap qui maintient l'ordre d'insertion des éléments ou, optionnellement, l'ordre d'accès. Cela garantit que l'itération des éléments respecte l'ordre dans lequel ils ont été ajoutés ou accédés.
• TreeMap : Implémentant l'interface SortedMap, TreeMap stocke les éléments de manière ordonnée selon la clé. L'ordre peut être naturel (les clés doivent implémenter Comparable) ou défini par un Comparator personnalisé fourni lors de la construction. C'est le choix idéal pour les applications nécessitant un mappage trié.

Il est crucial que les clés utilisées dans toutes ces implémentations de Map soient des objets immuables, c'est-à-dire que leur code de hachage ne doit pas changer après leur création. Si un code de hachage de clé change, la Map pourrait ne plus être capable de localiser l'entrée correspondante.

Étant donné sa flexibilité et ses performances pour la majorité des cas d'usage, HashMap est l'implémentation de Map la plus fréquemment employée. Nous allons maintenant plonger dans son fonctionnement, en examinant sa structure interne, ses méthodes clés, son mécanisme d'agradnissement et les considérations de sécurité.

Implémentation Interne de HashMap

Pour comprendre HashMap, il est essentiel de connaître sa structure de stockage et les opérations qu'elle offre.

Structure de Stockage : Champs Clés

La structure de HashMap est une combinaison d'un tableau (array), de listes chaînées (linked lists) et, depuis JDK 1.8, d'arbres rouges-noirs (red-black trees). [Illustration: Diagramme conceptuel d'une HashMap montrant le tableau, les listes chaînées et les arbres rouges-noirs dans les "buckets"].

Deux questions importantes se posent : qu'est-ce qui est réellement stocké et quels sont les avantages de cette approche ?

1. Le champ le plus important de la classe HashMap est Node[] table, qui représente le tableau de "buckets" (compartiments). Chaque élément de ce tableau est un objet Node (ou EntreeNoeud dans notre réécriture), introduit avec JDK 1.8. Précédemment, JDK 1.7 utilisait des objets Entry.

static class EntreeNoeud<K, V> implements Map.Entry<K, V> {
    final int hachage; // Code de hachage pour localiser l'index dans le tableau
    final K cle;
    V valeur;
    EntreeNoeud<K, V> suivant; // Référence au nœud suivant dans la liste chaînée

    EntreeNoeud(int hachage, K cle, V valeur, EntreeNoeud<K, V> suivant) {
        this.hachage = hachage;
        this.cle = cle;
        this.valeur = valeur;
        this.suivant = suivant;
    }

    @Override
    public final K getKey() { return cle; }

    @Override
    public final V getValue() { return valeur; }

    @Override
    public final String toString() { return cle + "=" + valeur; }

    @Override
    public final int hashCode() {
        return Objects.hashCode(cle) ^ Objects.hashCode(valeur);
    }

    @Override
    public final V setValue(V nouvelleValeur) {
        V ancienneValeur = this.valeur;
        this.valeur = nouvelleValeur;
        return ancienneValeur;
    }

    @Override
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?, ?> e = (Map.Entry<?, ?>)o;
            if (Objects.equals(cle, e.getKey()) &&
                Objects.equals(valeur, e.getValue()))
                return true;
        }
        return false;
    }
}

Chaque EntreeNoeud est une paire clé-valeur et représente un élément dans la HashMap. Les points noirs dans le diagramme conceptuel sont des objets EntreeNoeud.

2. HashMap utilise une table de hachage avec un mécanisme de chaînage séparé pour résoudre les collisions. Cela signifie qu'à chaque indice du tableau est associée une liste chaînée. Lorsqu'une donnée est hachée et que son indice de tableau est déterminé, elle est ajoutée à la liste chaînée de ce compartiment. Par exemple, lorsque map.put("MaSociete", "Nom") est exécuté, le système calcule le code de hachage de la clé "MaSociete", puis utilise une série d'opérations (détaillées plus loin) pour trouver son emplacement dans le tableau. Si plusieurs clés hachent au même indice, il y a une collision, et les éléments sont ajoutés à la liste chaînée correspondante. Une bonne fonction de hachage miniimse les collisions, améliorant ainsi les performances.

L'efficacité d'une HashMap dépend de la distribution uniforme des codes de hachage. Si le tableau est grand, même un algorithme de hachage médiocre peut donner une distribution correcte. Inversement, un petit tableau peut entraîner de nombreuses collisions même avec un bon algorithme. Il est donc crucial d'équilibrer l'espace et le temps, ce qui est géré par la taille du tableau et un algorithme de hachage efficace. Les mécanismes clés pour y parvenir sont le bon algorithme de hachage et le processus d'agrandissement (resizing).

Avant d'aborder le hachage et l'agrandissement, examinons quelques champs importants de HashMap, généralement initialisés par le constructeur par défaut :

int seuil;             // Le nombre maximal d'entrées (clés-valeurs) avant l'agrandissement
final float facteurDeCharge; // Le facteur de charge (par défaut 0.75)
int compteurModifications; // Compteur des modifications structurelles
int taille;  // Nombre actuel d'entrées dans la HashMap

Le tableau Node[] table a une longueur initiale par défaut de 16. Le facteurDeCharge (loadFactor) par défaut est de 0.75. Le seuil (threshold) est le nombre maximal d'éléments que la HashMap peut contenir avant de se redimensionner, calculé comme seuil = longueurTableau * facteurDeCharge. Un facteur de charge plus élevé permet de stocker plus d'éléments dans la même capacité de tableau, mais augmente la probabilité de collisions et la longueur des listes chaînées. Le facteur de charge par défaut de 0.75 représente un compromis équilibré entre l'espace et le temps. Il est généralement recommandé de ne pas le modifier, sauf pour des besoins spécifiques. Diminuer le facteurDeCharge réduit les collisions au détriment de l'espace mémoire, tandis l'augmenter économise de l'espace mais augmente le risque de collisions.

Le champ taille (size) représente le nombre réel de paires clé-valeur stockées dans la HashMap, à ne pas confondre avec la longueur du tableau ou le seuil. Le compteurModifications (modCount) enregistre le nombre de modifications structurelles apportées à la HashMap, utilisé pour la détection rapide d'échecs (fail-fast) lors des itérations. Une modification structurelle signifie l'ajout ou la suppression d'une paire clé-valeur, mais pas la simple mise à jour d'une valeur existante.

La longueur du tableau des compartiments (table) doit toujours être une puissance de 2. Ce choix, bien que non conventionnel par rapport à l'utilisation de nombres premiers dans d'autres implémentations de hachage (comme Hashtable avec une taille initiale de 11), est une optimisation cruciale pour le calcul de l'indice de hachage et le processus d'agrandissement. Il permet également d'incorporer les bits de poids fort dans le calcul de hachage pour minimiser les collisions.

Malgré les optimisations de l'algorithme de hachage et du facteur de charge, des listes chaînées excessivement longues peuvent toujours apparaître, dégradant gravement les performances de HashMap (complexité O(N) pour la recherche). C'est pourquoi, à partir de JDK 1.8, une amélioration majeure a été introduite : lorsqu'une liste chaînée dépasse une certaine longueur (par défaut 8), elle est convertie en arbre rouge-noir. Cette structure permet des opérations d'insertion, de suppression et de recherche avec une complexité logarithmique (O(log N)), améliorant considérablement les performances dans les scénarios de collisions fréquentes.

Implémentation Fonctionnelle : Méthodes Clés

Nous allons nous concentrer sur trois aspects représentatifs des fonctionnalités internes de HashMap : le calcul de l'indice du tableau, l'exécution détaillée de la méthode put et le processus d'agrandissement.

1. Détermination de l'Indice du Tableau

L'étape initiale et cruciale pour toutes les opérations (ajout, suppression, recherche) est de localiser la position correcte dans le tableau des compartiments. Une distribution uniforme des éléments est essentielle pour l'efficacité, idéalement avec un seul élément par compartiment pour éviter de parcourir les listes chaînées. L'algorithme de hachage dans HashMap influence directement cette distribution.

Voici l'implémentation du calcul de hachage (méthode A et B) :

// Méthode A: Fonction de hachage pour JDK 1.8 et JDK 1.7
static final int calculerHachage(Object objetCle) {
    int valHachage;
    // 1ère étape: Obtenir le code de hachage de l'objet
    // 2ème étape: Mélanger les bits de poids fort (>>> 16) avec ceux de poids faible (^)
    return (objetCle == null) ? 0 : (valHachage = objetCle.hashCode()) ^ (valHachage >>> 16);
}

// Méthode B: Pour calculer l'index dans le tableau (conceptuellement identique en JDK 1.8)
static int determinerIndexTableau(int codeHachage, int tailleTableau) {
    // 3ème étape: Opération de modulo optimisée pour les tailles de tableau puissance de 2
    return codeHachage & (tailleTableau - 1);
}

L'algorithme de hachage se décompose en trois phases : obtenir le code de hachage de la clé, mélanger les bits de poids fort, et appliquer une opération de modulo (implicitement).

Pour un objet donné, si sa méthode hashCode() retourne toujours la même valeur, alors calculerHachage() produira toujours le même code de hachage. Normalement, on utiliserait l'opérateur modulo (%) pour distribuer les éléments, mais HashMap utilise l'opération bit à bit h & (longueurTableau - 1). Cette astuce est possible car la longueur du tableau est toujours une puissance de 2. L'opération & est plus efficace que %, et cette optimisation contribue à la vitesse de HashMap.

En JDK 1.8, le processus de mélange des bits de poids fort ((valHachage = objetCle.hashCode()) ^ (valHachage >>> 16)) a été optimisé. Il XORise les 16 bits de poids fort du code de hachage avec ses 16 bits de poids faible. Ceci assure qu'même avec un tableau de petite taille, les bits de poids fort contribuent au calcul de l'index, réduisant ainsi les collisions sans coût excessif. [Illustration: Exemple de calcul d'index montrant comment les bits de poids fort influencent l'index.]

2. Analyse de la Méthode put

Le processus de la méthode put dans HashMap peut être schématisé comme suit :

1. Vérifier si le tableau d'entrées (table) est null ou vide. Si oui, effectuer un resize() pour l'initialiser ou l'agrandir.
2. Calculer l'indice i dans le tableau pour la clé. Si table[i] est null, créer un nouveau nœud et l'ajouter directement, puis passer à l'étape 6. Sinon, passer à l'étape 3.
3. Comparer le premier élément de table[i] avec la clé fournie. Si les codes de hachage et les méthodes equals() correspondent, la valeur est mise à jour, et l'opération est terminée. Sinon, passer à l'étape 4.
4. Vérifier si table[i] est une instance de TreeNode (arbre rouge-noir). Si oui, insérer la paire clé-valeur dans l'arbre. Sinon, passer à l'étape 5.
5. Parcourir la liste chaînée à table[i]. Si la longueur de la liste dépasse 8 (seuil de conversion), la convertir en arbre rouge-noir et insérer la paire. Sinon, ajouter la nouvelle paire à la fin de la liste. Si la clé existe déjà dans la liste, sa valeur est mise à jour.
6. Après l'insertion réussie, incrémenter le compteur de taille. Si size dépasse le threshold (seuil), déclencher un resize().

Voici un extrait simplifié du code source de la méthode putVal de JDK 1.8 :

public V mettre(K cle, V valeur) {
    return putVal(calculerHachage(cle), cle, valeur, false, true);
}

final V putVal(int hachage, K cle, V valeur, boolean seulementSiAbsent, boolean evict) {
    EntreeNoeud<K, V>[] tableauEntrees; EntreeNoeud<K, V> noeudCourant; int tailleTableau, index;

    // Étape 1: Initialiser ou agrandir le tableau si nécessaire
    if ((tableauEntrees = table) == null || (tailleTableau = tableauEntrees.length) == 0)
        tailleTableau = (tableauEntrees = agrandir()).length;

    // Étape 2: Calculer l'index et ajouter si le compartiment est vide
    if ((noeudCourant = tableauEntrees[index = (tailleTableau - 1) & hachage]) == null)
        tableauEntrees[index] = new EntreeNoeud<>(hachage, cle, valeur, null);
    else {
        EntreeNoeud<K, V> elementTrouve; K cleExistante;
        // Étape 3: Clé déjà présente au premier élément du compartiment
        if (noeudCourant.hachage == hachage &&
            ((cleExistante = noeudCourant.cle) == cle || (cle != null && cle.equals(cleExistante))))
            elementTrouve = noeudCourant;
        // Étape 4: Le compartiment est une structure d'arbre rouge-noir
        else if (noeudCourant instanceof ArbreNoeud) // TreeNode
            elementTrouve = ((ArbreNoeud<K, V>) noeudCourant).insererArbreVal(this, tableauEntrees, hachage, cle, valeur);
        // Étape 5: Le compartiment est une liste chaînée
        else {
            for (int compteurListe = 0; ; ++compteurListe) {
                if ((elementTrouve = noeudCourant.suivant) == null) {
                    noeudCourant.suivant = new EntreeNoeud<>(hachage, cle, valeur, null);
                    // Si la liste devient trop longue, la convertir en arbre rouge-noir
                    if (compteurListe >= SEUIL_ARBRE_ROUGE_NOIR - 1) // TREEIFY_THRESHOLD (8)
                        convertirEnArbre(tableauEntrees, hachage);
                    break;
                }
                // Si la clé existe déjà dans la liste, la valeur est mise à jour
                if (elementTrouve.hachage == hachage &&
                    ((cleExistante = elementTrouve.cle) == cle || (cle != null && cle.equals(cleExistante))))
                    break;
                noeudCourant = elementTrouve;
            }
        }

        if (elementTrouve != null) { // Entrée existante pour la clé
            V ancienneValeur = elementTrouve.valeur;
            if (!seulementSiAbsent || ancienneValeur == null)
                elementTrouve.valeur = valeur;
            // afterNodeAccess(elementTrouve); // Méthode d'accroche (LinkedHashMap)
            return ancienneValeur;
        }
    }

    ++compteurModifications;
    // Étape 6: Agrandir si la taille dépasse le seuil
    if (++taille > seuil)
        agrandir();
    // afterNodeInsertion(evict); // Méthode d'accroche (LinkedHashMap)
    return null;
}

3. Mécanisme d'Agrandissement (Redimensionnement)

L'agrandissement est l'opération qui consiste à recalculer la capacité de la HashMap lorsque le nombre d'éléments dépasse son seuil maximal. Puisque les tableaux en Java ne peuvent pas être redimensionnés dynamiquement, HashMap crée un nouveau tableau de plus grande capacité (généralement le double de l'ancienne) et y copie tous les éléments existants.

Pour mieux comprendre le processus de redimensionnement, nous allons d'abord examiner l'implémentation de JDK 1.7, qui est plus simple avant l'introduction des arbres rouges-noirs, mais dont le principe reste fondamentalement le même.

void agrandir(int nouvelleCapacite) { // Nouvelle capacité désirée
    Entree<K, V>[] ancienTableau = table;    // Référence à l'ancien tableau d'entrées
    int ancienneCapacite = ancienTableau.length;
    if (ancienneCapacite == CAPACITE_MAXIMALE) { // Si la capacité max est atteinte (2^30)
        seuil = Integer.MAX_VALUE; // Le seuil est mis à la valeur max, plus d'agrandissement
        return;
    }

    Entree<K, V>[] nouveauTableau = (Entree<K, V>[]) new Entree[nouvelleCapacite]; // Nouveau tableau
    transferer(nouveauTableau);                         // Transfert des données
    table = nouveauTableau;                           // Référence le nouveau tableau
    seuil = (int)(nouvelleCapacite * facteurDeCharge); // Met à jour le seuil
}

La méthode transferer() est responsable de la copie des éléments de l'ancien tableau vers le nouveau :

void transferer(Entree<K, V>[] nouveauTableau) {
    Entree<K, V>[] sourceTableau = table;                   // L'ancien tableau
    int nouvelleCapacite = nouveauTableau.length;
    for (int j = 0; j < sourceTableau.length; j++) { // Parcourir l'ancien tableau
        Entree<K, V> element = sourceTableau[j];             // Chaque élément du compartiment
        if (element != null) {
            sourceTableau[j] = null; // Libérer la référence dans l'ancien tableau
            do {
                Entree<K, V> suivant = element.suivant;
                int i = determinerIndexTableau(element.hachage, nouvelleCapacite); // Recalculer la position
                element.suivant = nouveauTableau[i]; // Méthode d'insertion par la tête
                nouveauTableau[i] = element;      // Placer l'élément dans le nouveau tableau
                element = suivant;             // Passer à l'élément suivant de la liste
            } while (element != null);
        }
    }
}

Dans JDK 1.7, l'insertion dans le nouveau tableau se fait par la tête de la liste chaînée (element.suivant = nouveauTableau[i]), ce qui inverse l'ordre des éléments dans chaque liste. Les éléments d'une même liste dans l'ancien tableau peuvent se retrouver à des positions différentes dans le nouveau tableau après le recalcul d'index.

[Illustration: Exemple d'agrandissement avec un tableau de taille 2 à 4, montrant les collisions et le re-hachage des clés 3, 7, 5.]

Les optimisations de JDK 1.8 pour l'agrandissement sont ingénieuses. Puisque la nouvelle capacité est le double de l'ancienne (une autre puissance de 2), un élément se retrouvera soit à son index original, soit à son index original plus l'ancienne capacité. Cela est dû au fait que l'opération & (nouvelleCapacite - 1) ajoute un bit de poids fort au masque. [Illustration: Comparaison des positions d'index avant et après l'agrandissement (n devient 2n), montrant comment les clés se redistribuent.]

Grâce à cette observation, JDK 1.8 évite de recalculer l'intégralité du code de hachage pour chaque élément. Au lieu de cela, il examine un bit supplémentaire dans le code de hachage de chaque élément. Si ce bit est 0, l'élément reste au même index. S'il est 1, l'élément se déplace à index + ancienneCapacite. [Illustration: Schéma d'agrandissement d'une table de 16 à 32, montrant la division des éléments en deux groupes (index original et index original + oldCap) sans recalcul de hachage.]

Cette approche est extrêmement efficace car elle réduit le temps de recalcul de hachage et distribue de manière uniforme les éléments des listes chaînées existantes dans les nouveaux compartiments. Contrairement à JDK 1.7, l'ordre des éléments dans les listes chaînées n'est pas inversé en JDK 1.8. Voici un aperçu du code de la méthode resize() en JDK 1.8 :

final EntreeNoeud<K,V>[] agrandir() {
    EntreeNoeud<K,V>[] ancienTab = table;
    int ancienneCapacite = (ancienTab == null) ? 0 : ancienTab.length;
    int ancienSeuil = seuil;
    int nouvelleCapacite, nouveauSeuil = 0;

    if (ancienneCapacite > 0) {
        if (ancienneCapacite >= CAPACITE_MAXIMALE) { // Si la capacité max est atteinte
            seuil = Integer.MAX_VALUE;
            return ancienTab;
        }
        // Doubler la capacité et le seuil si possible
        else if ((nouvelleCapacite = ancienneCapacite << 1) < CAPACITE_MAXIMALE &&
                 ancienneCapacite >= CAPACITE_INITIALE_PAR_DEFAUT) // DEFAULT_INITIAL_CAPACITY (16)
            nouveauSeuil = ancienSeuil << 1; // Doubler le seuil
    }
    else if (ancienSeuil > 0) // Si le seuil était défini par l'utilisateur
        nouvelleCapacite = ancienSeuil;
    else {               // Utilisation des valeurs par défaut
        nouvelleCapacite = CAPACITE_INITIALE_PAR_DEFAUT;
        nouveauSeuil = (int)(FACTEUR_DE_CHARGE_PAR_DEFAUT * CAPACITE_INITIALE_PAR_DEFAUT);
    }

    // Calculer le nouveau seuil si non défini
    if (nouveauSeuil == 0) {
        float facteurTemp = (float)nouvelleCapacite * facteurDeCharge;
        nouveauSeuil = (nouvelleCapacite < CAPACITE_MAXIMALE && facteurTemp < (float)CAPACITE_MAXIMALE ?
                          (int)facteurTemp : Integer.MAX_VALUE);
    }
    seuil = nouveauSeuil;

    @SuppressWarnings({"rawtypes", "unchecked"})
    EntreeNoeud<K,V>[] nouveauTab = (EntreeNoeud<K,V>[])new EntreeNoeud[nouvelleCapacite];
    table = nouveauTab;

    if (ancienTab != null) {
        for (int j = 0; j < ancienneCapacite; ++j) {
            EntreeNoeud<K,V> element;
            if ((element = ancienTab[j]) != null) {
                ancienTab[j] = null;
                if (element.suivant == null)
                    nouveauTab[element.hachage & (nouvelleCapacite - 1)] = element;
                else if (element instanceof ArbreNoeud) // TreeNode
                    ((ArbreNoeud<K,V>)element).scinder(this, nouveauTab, j, ancienneCapacite);
                else { // Optimisation de re-hachage pour les listes chaînées
                    EntreeNoeud<K,V> teteBasse = null, queueBasse = null; // Éléments qui restent à l'ancien index
                    EntreeNoeud<K,V> teteHaute = null, queueHaute = null; // Éléments qui vont à l'ancien index + ancienneCapacite
                    EntreeNoeud<K,V> prochainElement;
                    do {
                        prochainElement = element.suivant;
                        if ((element.hachage & ancienneCapacite) == 0) { // Bit supplémentaire est 0
                            if (queueBasse == null)
                                teteBasse = element;
                            else
                                queueBasse.suivant = element;
                            queueBasse = element;
                        }
                        else { // Bit supplémentaire est 1
                            if (queueHaute == null)
                                teteHaute = element;
                            else
                                queueHaute.suivant = element;
                            queueHaute = element;
                        }
                    } while ((element = prochainElement) != null);

                    if (queueBasse != null) {
                        queueBasse.suivant = null;
                        nouveauTab[j] = teteBasse; // Placer le groupe à l'ancien index
                    }
                    if (queueHaute != null) {
                        queueHaute.suivant = null;
                        nouveauTab[j + ancienneCapacite] = teteHaute; // Placer le groupe à l'ancien index + ancienneCapacite
                    }
                }
            }
        }
    }
    return nouveauTab;
}

Considérations sur la Sécurité des Threads

Dans un environnement multithread, il est impératif d'éviter l'utilisation de HashMap, car elle n'est pas thread-safe. L'alternative recommandée est ConcurrentHashMap. Examinons un exemple qui illustre comment l'utilisation concurrente de HashMap peut entraîner une boucle infinie (cet exemple est basé sur JDK 1.7 pour mieux montrer le problème).

public class BoucleInfinieHashMap {  
    private static HashMap<Integer, String> carte = new HashMap<Integer, String>(2, 0.75f);  

    public static void main(String[] args) {  
        carte.put(5, "C");  

        new Thread("Fil1") {  
            public void run() {  
                carte.put(7, "B");  
                System.out.println("Fil1: " + carte);  
            };  
        }.start();  

        new Thread("Fil2") {  
            public void run() {  
                carte.put(3, "A");  
                System.out.println("Fil2: " + carte);  
            };  
        }.start();        
    }  
} 

Ici, carte est initialisée avec une capacité de 2 et un facteur de charge de 0.75, ce qui donne un seuil de 1. Ainsi, l'ajout du deuxième élément déclenchera un redimensionnement. Si nous mettons des points d'arrêt et débuguons Fil1 et Fil2 pour qu'ils atteignent simultanément la ligne Entry next = e.next; de la méthode transferer() (section 3.3), les données auront déjà été ajoutées avec succès.

Si Fil1 continue son exécution jusqu'à la fin de la méthode transferer(), puis Fil2 exécute son propre redimensionnement, il y a un risque de créer une boucle circulaire. [Illustration: Séquence d'événements montrant comment deux threads modifiant simultanément une HashMap peuvent créer une liste chaînée circulaire lors du redimensionnement, conduisant à une boucle infinie.]

Le problème survient dans JDK 1.7 en raison de l'insertion par la tête de liste lors du redimensionnement. Si Fil1 est suspendu au milieu de transferer() et que Fil2 termine le redimensionnement, la structure des listes chaînées est modifiée. Lorsque Fil1 reprend, ses pointeurs e et next, basés sur l'ancienne structure, peuvent interagir avec la nouvelle structure créée par Fil2 de manière à créer un cycle (par exemple, key(3).next pointant vers key(7) et key(7).next pointant vers key(3)). Si ensuite map.get(une_cle_impliquee) est appelé, cela entraînera une boucle infinie.

Comparaison des Performances entre JDK 1.8 et JDK 1.7

Les performances de HashMap dépendent fortement de la qualité de la fonction de hachage. Si toutes les clés ont des codes de hachage distincts et sont distribuées uniformément, la méthode get a une complexité temporelle de O(1). En cas de nombreuses collisions, où tous les éléments se concentrent dans un seul compartiment (liste chaînée), la complexité devient O(N). Avec les arbres rouges-noirs de JDK 1.8, cette complexité passe à O(log N).

Cas de Distribution de Hachage Uniforme

Pour évaluer les performances, nous utilisons une classe Cle (clé) qui fournit un excellent code de hachage (sa valeur entière) :

class Cle implements Comparable<Cle> {
    private final int valeur;

    Cle(int valeur) {
        this.valeur = valeur;
    }

    @Override
    public int compareTo(Cle autreCle) {
        return Integer.compare(this.valeur, autreCle.valeur);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Cle cle = (Cle) o;
        return valeur == cle.valeur;
    }

    @Override
    public int hashCode() {
        return valeur;
    }
}

Pour éviter les créations fréquentes d'objets, nous utilisons un cache d'instances de Cle :

public class GestionnaireCles {
    public static final int MAX_CLE = 10_000_000;
    private static final Cle[] CACHE_CLES = new Cle[MAX_CLE];

    static {
        for (int i = 0; i < MAX_CLE; ++i) {
            CACHE_CLES[i] = new Cle(i);
        }
    }

    public static Cle obtenir(int valeur) {
        return CACHE_CLES[valeur];
    }
}

Nous testons la performance en créant des HashMap de différentes tailles et en mesurant le temps de récupération des éléments, en désactivant le redimensionnement pour des mesures plus claires :

public class TestPerformanceHashMap {
    static void executerTest(int tailleMap) {
        HashMap<Cle, Integer> carte = new HashMap<Cle, Integer>(tailleMap);
        for (int i = 0; i < tailleMap; ++i) {
            carte.put(GestionnaireCles.obtenir(i), i);
        }

        long tempsDebut = System.nanoTime();
        for (int i = 0; i < tailleMap; i++) {
            carte.get(GestionnaireCles.obtenir(i));
        }
        long tempsFin = System.nanoTime();
        System.out.println("Taille Map: " + tailleMap + ", Temps écoulé (ns): " + (tempsFin - tempsDebut));
    }

    public static void main(String[] args) {
        for (int i = 10; i <= 10_000_000; i *= 10) {
            executerTest(i);
        }
    }
}

Les résultats (conceptuels) montrent que les performances de JDK 1.8 sont généralement supérieures à celles de JDK 1.7, avec des améliorations de 15% à plus de 100% selon les tailles. Cependant, comme la distribution de hachage est déjà très uniforme, l'avantage des arbres rouges-noirs de JDK 1.8 n'est pas pleinement apparent.

Cas de Distribution de Hachage Très Inégale

Pour ce scénario, nous modifions la classe Cle pour qu'elle retourne toujours le même code de hachage, créant ainsi le pire cas possible pour une HashMap :

class Cle implements Comparable<Cle> {
    // ... autres méthodes ...

    @Override
    public int hashCode() {
        return 1; // Toutes les clés hachent au même compartiment
    }
}

En exécutant le même test main, les résultats (conceptuels) sont très différents :

Pour JDK 1.7, le temps d'exécution augmente linéairement avec la taille de la HashMap (O(N)), car toutes les clés se retrouvent dans la même liste chaînée. Pour JDK 1.8, le temps d'exécution augmente de manière logarithmique (O(log N)) puis se stabilise. Cette différence spectaculaire est due à la conversion des longues listes chaînées en arbres rouges-noirs, ce qui transforme une recherche linéaire en une recherche arborescente plus rapide. Cela démontre clairement l'importance cruciale d'une bonne fonction de hachage et les bénéfices de l'optimisation par arbre rouge-noir de JDK 1.8 en cas de collisions extrêmes.

Résumé des Points Clés

1. L'agrandissement d'une HashMap est une opération coûteuse en performance. Il est recommandé d'estimer la taille finale de la HashMap et de lui donner une capacité initiale appropriée pour minimiser les agrandissements fréquents.
2. Le facteur de charge peut être ajusté et peut même être supérieur à 1. Cependant, il est généralement conseillé de ne pas le modifier sauf dans des cas très spécifiques où les compromis temps/espace sont critiques.
3. HashMap n'est pas thread-safe. Pour les applications multithread, utilisez ConcurrentHashMap pour éviter les problèmes de concurrence tels que les boucles infinies ou les incohérences de données.
4. L'introduction des arbres rouges-noirs dans JDK 1.8 a considérablement amélioré les performances de HashMap, en particulier dans les scénarios où de nombreuses collisions de hachage se produisent.
5. Si vous n'avez pas encore mis à niveau vers JDK 1.8 (ou versions ultérieures), c'est fortement recommandé, car les améliorations de HashMap ne sont qu'une petite partie des nombreux bénéfices apportés par cette version.