Introduction aux Structures de Données de HashMap
L'implémentation de la classe HashMap en Java, particulièrement depuis la version 1.8, est une structure de données fondamentale qui offre des performances optimales pour le stockage et la récupération d'associations clé-valeur. Elle s'appuie sur une combinaison astucieuse de tableaux, de listes chaînées et d'arbres rouges-noirs pour gérer les collisions et maintenir une efficacité de recherche élevée.
Arbres Rouge-Noir : Un Aperçu
Avant Java 8, HashMap utilisait exclusivement un tableau de listes chaînées pour résoudre les collisions de hachage. Cependant, dans le pire des cas (lorsque toutes les clés ont le même hachage), une liste chaînée peut devenir très longue, dégradant la complexité de recherche à O(n). Pour remédier à cela, Java 8 a introduit l'utilisation des arbres rouge-noir (Red-Black Trees) lorsque la longueur d'une liste chaînée dépasse un certain seuil (généralement 8).
Un arbre rouge-noir est un type spécial d'arbre binaire de recherche auto-équilibré. Chaque nœud y est coloré en rouge ou en noir, et l'arbre maintient un équilibre grâce à un ensemble de règles strictes :
- Chaque nœud est soit rouge, soit noir.
- Le nœud racine est noir.
- Chaque feuille (représentée par un pointeur NIL/NULL) est noire.
- Si un nœud est rouge, ses enfants doivent être noirs (il ne peut y avoir deux nœuds rouges consécutifs sur un chemin).
- Tous les chemins d'un nœud donné à ses feuilles contiennent le même nombre de nœuds noirs.
L'insertion d'un élément dans un arbre rouge-noir se déroule en trois étapes :
- Insertion comme dans un arbre binaire de recherche standard.
- Coloration du nouveau nœud en rouge.
- Rééquilibrage de l'arbre par des rotations et des recolorations pour préserver les propriétés de l'arbre rouge-noir.
Analyse du Code Source de HashMap (Java 1.8)
HashMap en Java 8 combine un tableau (souvent appelé "buckets" ou "bins") avec des listes chaînées ou des arbres rouge-noir pour stocker les éléments. Les listes chaînées sont transformées en arbres rouge-noir (opération "treeify") lorsque leur taille dépasse un seuil (TREEIFY_THRESHOLD, généralement 8), et redeviennent des listes chaînées (opération "untreeify") si leur taille diminue (généralement en dessous de 6) suite à des suppressions ou des redimensionnements.
Initialisation de HashMap
Lors de la création d'une instance de HashMap, plusieurs paramètres clés sont définis :
- Capacité initiale (
initialCapacity) : La taille initiale du tableau interne. Par défaut, elle est de 16. La capacité est toujours une puissance de deux pour optimiser les calculs d'indexation. - Facteur de charge (
loadFactor) : Un seuil qui détermine quand la table doit être redimensionnée. La valeur par défaut est 0.75. - Seuil de redimensionnement (
threshold) : Calculé commecapacité * facteurDeCharge. Lorsque le nombre d'éléments dans laHashMapdépasse ce seuil, le tableau interne est redimensionné (doublé).
Le choix du facteur de charge influence l'équilibre entre l'utilisation de la mémoire et les performances. Un facteur de charge élevé réduit les redimensionnements mais augmente la longueur moyenne des chaînes/arbres, potentiellement dégradant les performances de recherche. Un faible facteur de charge réduit la longueur des chaînes mais augmente la fréquence des redimensionnements et l'utilisation de la mémoire.
La méthode statique tableSizeFor est utilisée pour garantir que la capacité fournie par l'utilisateur est toujours une puissance de deux, essentielle pour l'efficacité des opérations bit à bit lors de l'indexation.
// Création d'un HashMap avec une capacité initiale de 11
// HashMap<String, String> maCarte = new HashMap<String, String>(11);
/**
* Retourne la puissance de deux la plus proche (et supérieure ou égale) à la capacité cible fournie.
* Cette méthode assure que la capacité interne du tableau sera toujours une puissance de deux.
*
* @param capaciteCible La capacité désirée.
* @return La capacité ajustée à la prochaine puissance de deux.
*/
static final int calculerTailleTableau(int capaciteCible) {
int n = capaciteCible - 1; // Décrémente pour gérer correctement le cas où capaciteCible est déjà une puissance de deux
// Ex: si capaciteCible = 16, n devient 15 (0...01111)
// si capaciteCible = 11, n devient 10 (0...01010)
// Ces opérations OR bit à bit avec décalage vers la droite (opérateur non signé >>>)
// propagent le bit le plus significatif vers la droite.
// L'objectif est de remplir tous les bits de n avec des 1 à partir du bit le plus significatif.
// Ex pour n=10 (01010):
// n |= n >>> 1; // n = 01010 | 00101 = 01111 (15)
// n |= n >>> 2; // n = 01111 | 00011 = 01111 (15)
// n |= n >>> 4; // n = 01111 | 00000 = 01111 (15)
// ... jusqu'à 16 bits pour un entier (ou 32 pour des systèmes 64 bits si int est 32-bit).
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
// Retourne n + 1, ce qui correspond à la prochaine puissance de deux.
// Gère les cas limites: négatif (retourne 1) ou dépassement de la capacité maximale.
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // Ex: 15 + 1 = 16
}
Opération put (Insertion)
L'insertion d'une paire clé-valeur dans la HashMap via la méthode put (qui délègue à putVal) implique plusieurs étapes cruciales. L'emplacement de stockage dans le tableau est déterminé par un calcul d'index basé sur le code de hachage de la clé. Pour une table de taille N (toujours une puissance de deux), l'index est calculé comme (N - 1) & hash. Cette opération bit à bit est un moyen rapide et efficace de calculer le modulo hash % N lorsque N est une puissance de deux.
// Exemple d'appel: maCarte.put("2020", "bonne chance");
/**
* Implémente l'opération Map.put et les méthodes associées.
*
* @param hash Le code de hachage de la clé.
* @param cle La clé à insérer.
* @param valeur La valeur associée à la clé.
* @param seulementSiAbsent Si vrai, n'écrase pas une valeur existante pour la même clé.
* @param evict Si faux, le tableau est en mode création (pour les sous-classes comme LinkedHashMap).
* @return L'ancienne valeur associée à la clé, ou null si aucune.
*/
final V insererValeur(int hash, K cle, V valeur, boolean seulementSiAbsent,
boolean evict) {
Node<K,V>[] tableauInterne; Node<K,V> noeudCourant; int tailleTableau, indexBucket;
// 1. Vérifie et initialise le tableau interne si nécessaire.
// Si le tableau est null ou vide, déclenche un redimensionnement (qui l'initialisera).
if ((tableauInterne = table) == null || (tailleTableau = tableauInterne.length) == 0)
tailleTableau = (tableauInterne = resize()).length;
// 2. Calcule l'index du bucket. Si le bucket est vide, insère directement le nouveau nœud.
if ((noeudCourant = tableauInterne[indexBucket = (tailleTableau - 1) & hash]) == null)
tableauInterne[indexBucket] = newNode(hash, cle, valeur, null);
else {
// 3. Collision : un ou plusieurs éléments existent déjà à cet index.
Node<K,V> entreeExistante; K cleComparee;
// 3a. Vérifie si le premier nœud du bucket correspond à la clé à insérer.
if (noeudCourant.hash == hash &&
((cleComparee = noeudCourant.key) == cle || (cle != null && cle.equals(cleComparee))))
entreeExistante = noeudCourant;
// 3b. Si le bucket est une structure d'arbre rouge-noir (TreeNode), délègue l'insertion à l'arbre.
else if (noeudCourant instanceof TreeNode)
entreeExistante = ((TreeNode<K,V>)noeudCourant).putTreeVal(this, tableauInterne, hash, cle, valeur);
else {
// 3c. Le bucket est une liste chaînée : parcours de la liste.
for (int compteurBin = 0; ; ++compteurBin) {
// Si la fin de la liste est atteinte sans trouver la clé, ajoute le nouveau nœud.
if ((entreeExistante = noeudCourant.next) == null) {
noeudCourant.next = newNode(hash, cle, valeur, null);
// Vérifie si la liste est devenue trop longue et doit être convertie en arbre.
// (TREEIFY_THRESHOLD - 1 car compteurBin est basé sur l'index 0)
if (compteurBin >= TREEIFY_THRESHOLD - 1)
treeifyBin(tableauInterne, hash);
break;
}
// Si la clé est trouvée dans la liste, on sort de la boucle pour mettre à jour sa valeur.
if (entreeExistante.hash == hash &&
((cleComparee = entreeExistante.key) == cle || (cle != null && cle.equals(cleComparee))))
break;
noeudCourant = entreeExistante; // Avance au nœud suivant dans la liste.
}
}
// Si une entrée existante a été trouvée (soit le premier nœud, soit dans la liste/l'arbre),
// et que la politique le permet, met à jour sa valeur.
if (entreeExistante != null) {
V ancienneValeur = entreeExistante.value;
if (!seulementSiAbsent || ancienneValeur == null)
entreeExistante.value = valeur;
afterNodeAccess(entreeExistante); // Hook pour les sous-classes (ex: LinkedHashMap)
return ancienneValeur;
}
}
++modCount; // Incrémente le compteur de modifications structurelles.
// Si la taille totale de la carte dépasse le seuil, déclenche un redimensionnement.
if (++size > threshold)
resize();
afterNodeInsertion(evict); // Hook pour les sous-classes.
return null; // Retourne null si aucune ancienne valeur n'a été remplacée.
}
Opération get (Récupération)
La récupération d'une valeur associée à une clé via la méthode get (qui utilise getNode) suit un chemin similaire à l'insertion pour localiser l'élément. Elle commence par calculer l'index du bucket, puis traverse la structure (liste chaînée ou arbre rouge-noir) à cet emplacement.
/**
* Implémente Map.get et les méthodes associées.
*
* @param hash La valeur de hachage de la clé.
* @param cle L'objet clé dont la valeur est recherchée.
* @return Le nœud correspondant à la clé, ou null si non trouvé.
*/
final Node<K,V> recupererNoeud(int hash, Object cle) {
Node<K,V>[] tableauActuel; Node<K,V> premierNoeud, noeudParcouru; int tailleTableau; K cleRef;
// 1. Vérifie que le tableau interne existe, qu'il n'est pas vide,
// et que le bucket calculé par le hachage n'est pas nul.
if ((tableauActuel = table) != null && (tailleTableau = tableauActuel.length) > 0 &&
(premierNoeud = tableauActuel[(tailleTableau - 1) & hash]) != null) {
// 2. Vérifie si le premier nœud du bucket correspond à la clé recherchée.
if (premierNoeud.hash == hash && // Le hachage correspond.
((cleRef = premierNoeud.key) == cle || (cle != null && cle.equals(cleRef)))) // La clé correspond.
return premierNoeud; // Retourne le nœud s'il est trouvé au début du bucket.
// 3. Si d'autres éléments existent dans le bucket après le premier.
if ((noeudParcouru = premierNoeud.next) != null) {
// 3a. Si le bucket est une structure d'arbre rouge-noir (TreeNode), délègue la recherche à l'arbre.
if (premierNoeud instanceof TreeNode)
return ((TreeNode<K,V>)premierNoeud).getTreeNode(hash, cle);
// 3b. Si le bucket est une liste chaînée, parcourt la liste.
do {
if (noeudParcouru.hash == hash &&
((cleRef = noeudParcouru.key) == cle || (cle != null && cle.equals(cleRef))))
return noeudParcouru; // Retourne le nœud si trouvé dans la liste.
} while ((noeudParcouru = noeudParcouru.next) != null); // Continue tant qu'il y a un nœud suivant.
}
}
return null; // Retourne null si le nœud n'a pas été trouvé.
}
Opération resize (Redimensionnement)
Le redimensionnement est une opération coûteuse mais essentielle pour maintenir les performances de la HashMap. Il se produit lorsque le nombre d'éléments dépasse le seuil défini par capacity * loadFactor. La capacité du tableau est alors doublée, et tous les éléments existants doivent être redistribués dans le nouveau tableau.
/**
* Initialise ou double la taille du tableau de stockage interne.
* Si le tableau est actuellement null, il est alloué selon la capacité initiale
* cible spécifiée par le 'threshold'. Sinon, comme l'expansion utilise des puissances de deux,
* les éléments de chaque bucket doivent soit rester au même index,
* soit se déplacer avec un décalage de 'ancienneCapacite' dans la nouvelle table.
*
* @return Le nouveau tableau de nœuds (la table redimensionnée).
*/
final Node<K,V>[] redimensionnerTableau() {
Node<K,V>[] ancienTableau = table;
int ancienneCapacite = (ancienTableau == null) ? 0 : ancienTableau.length;
int ancienSeuil = threshold;
int nouvelleCapacite, nouveauSeuil = 0;
// Détermine la nouvelle capacité et le nouveau seuil.
if (ancienneCapacite > 0) {
if (ancienneCapacite >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE; // La capacité maximale a été atteinte, pas de redimensionnement.
return ancienTableau;
}
// Double la capacité si elle ne dépasse pas la capacité maximale et si elle est au moins la capacité par défaut.
else if ((nouvelleCapacite = ancienneCapacite << 1) < MAXIMUM_CAPACITY &&
ancienneCapacite >= DEFAULT_INITIAL_CAPACITY)
nouveauSeuil = ancienSeuil << 1; // Double également le seuil.
}
// Cas où la HashMap est initialisée pour la première fois avec un seuil non nul (la capacité initiale est stockée dans threshold).
else if (ancienSeuil > 0)
nouvelleCapacite = ancienSeuil;
// Cas où la HashMap est initialisée avec les valeurs par défaut (capacité et seuil à zéro).
else {
nouvelleCapacite = DEFAULT_INITIAL_CAPACITY;
nouveauSeuil = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// Calcule le nouveau seuil si celui-ci n'a pas été défini dans les étapes précédentes.
if (nouveauSeuil == 0) {
float facteurCalcul = (float)nouvelleCapacite * loadFactor;
nouveauSeuil = (nouvelleCapacite < MAXIMUM_CAPACITY && facteurCalcul < (float)MAXIMUM_CAPACITY ?
(int)facteurCalcul : Integer.MAX_VALUE);
}
threshold = nouveauSeuil; // Met à jour le seuil de redimensionnement de l'instance.
// Crée le nouveau tableau avec la nouvelle capacité.
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] nouveauTableau = (Node<K,V>[])new Node[nouvelleCapacite];
table = nouveauTableau; // Met à jour la référence au tableau interne.
// Redistribue les éléments de l'ancien tableau vers le nouveau.
if (ancienTableau != null) {
for (int j = 0; j < ancienneCapacite; ++j) {
Node<K,V> elementCourant;
if ((elementCourant = ancienTableau[j]) != null) {
ancienTableau[j] = null; // Libère la référence de l'ancien bucket pour le garbage collector.
// Si le bucket contient un seul élément, le place directement dans le nouveau tableau.
if (elementCourant.next == null)
nouveauTableau[elementCourant.hash & (nouvelleCapacite - 1)] = elementCourant;
// Si le bucket est une structure d'arbre rouge-noir, délègue la redistribution à la méthode split de TreeNode.
else if (elementCourant instanceof TreeNode)
((TreeNode<K,V>)elementCourant).split(this, nouveauTableau, j, ancienneCapacite);
// Si le bucket est une liste chaînée, divise la liste en deux.
else { // Préserve l'ordre relatif des éléments.
Node<K,V> teteListeBasse = null, queueListeBasse = null; // Pour les éléments qui restent à l'index 'j'.
Node<K,V> teteListeHaute = null, queueListeHaute = null; // Pour les éléments qui vont à l'index 'j + ancienneCapacite'.
Node<K,V> noeudSuivant;
do {
noeudSuivant = elementCourant.next;
/*
* Le bit 'ancienneCapacite' dans le hachage de l'élément détermine son nouveau bucket.
* Si (elementCourant.hash & ancienneCapacite) == 0, l'élément reste à l'index 'j'.
* Sinon, il se déplace à l'index 'j + ancienneCapacite'.
* C'est une optimisation clé grâce au fait que les capacités sont des puissances de deux.
*/
if ((elementCourant.hash & ancienneCapacite) == 0) {
if (queueListeBasse == null)
teteListeBasse = elementCourant;
else
queueListeBasse.next = elementCourant;
queueListeBasse = elementCourant;
} else {
if (queueListeHaute == null)
teteListeHaute = elementCourant;
else
queueListeHaute.next = elementCourant;
queueListeHaute = elementCourant;
}
} while ((elementCourant = noeudSuivant) != null);
// Place les listes nouvellement formées dans le nouveau tableau.
if (queueListeBasse != null) {
queueListeBasse.next = null; // Termine la liste.
nouveauTableau[j] = teteListeBasse;
}
if (queueListeHaute != null) {
queueListeHaute.next = null; // Termine la liste.
nouveauTableau[j + ancienneCapacite] = teteListeHaute;
}
}
}
}
}
return nouveauTableau;
}
Lors du redimensionnement d'une HashMap, la capacité du tableau est doublée. Les éléments de chaque bucket de l'ancien tableau sont alors réexaminés pour leur placement dans le nouveau tableau. Grâce à l'utilisation de capacités qui sont toujours des puissances de deux, la redistribution des éléments est très efficace. Pour un élément donné à l'index j dans l'ancien tableau, son nouvel index sera soit j, soit j + ancienneCapacite. Cette décision est prise en testant un seul bit du code de hachage de l'élément : le bit correspondant à la valeur de ancienneCapacite.
Par exemple, si ancienneCapacite était de 16 (binaire ...010000), et le hachage d'une clé est H :
- Si le 5ème bit (à partir de la droite, en commençant par le bit 0) de
Hest 0, alors(H & 16) == 0. L'élément reste à l'indexj. - Si le 5ème bit de
Hest 1, alors(H & 16) == 16(ouancienneCapacite). L'élément se déplace à l'indexj + ancienneCapacite.
Cette optimisation permet de scinder chaque liste ou arbre de l'ancien tableau en deux nouvelles listes (ou sous-arbres) dans le nouveau tableau, sans avoir à recalculer complètement le modulo pour chaque élément, ce qui est très performant.
Considérations sur la Concurrence
Il est crucial de noter que HashMap n'est pas thread-safe. Dans les versions de Java antérieures à Java 8, des problèmes de boucles infinies pouvaient survenir lors d'opérations concurrentes de put et resize, en particulier à cause de la manipulation des listes chaînées (souvent en utilisant une insertion en tête qui pouvait inverser l'ordre des éléments). Bien que Java 8 ait amélioré la gestion du redimensionnement (par exemple, en scindant les listes au lieu de les reconstruire entièrement et en transformant les longues listes en arbres), HashMap reste inadapté à un usage multi-threadé sans synchronisation externe. Pour les scénarios concurrents, il est recommandé d'utiliser des alternatives comme ConcurrentHashMap.