Comprendre HashMap en Java 8 : Implémentation et Optimisations
HashMap est l'une des structures de données les plus fréquemment utilisées par les programmeurs Java pour manipuler des paires clé-valeur. Avec les évolutions du JDK (Java Development Kit), la version JDK 1.8 a optimisé l'implémentation sous-jacente de HashMap, notamment en introduisant la structure de données d'arbre rouge-noir et en optimisant le processus de redimensionnement. Cet article examine en détail les différences entre JDK 1.7 et JDK 1.8, et explore l'implémentation structurelle et les principes fonctionnels de HashMap.
Introduction aux implémentations de Map
Java définit une interface java.util.Map pour les structures de données de type mappage. Cette interface possède quatre implémentations couarntes : HashMap, Hashtable, LinkedHashMap et TreeMap. Voici leurs caractéristiques respectives :
- HashMap : Stocke les données en fonction de la valeur hashCode de la clé, permettant une localisation directe dans la plupart des cas, offrant ainsi un accès rapide. Cependant, l'ordre de parcours n'est pas garanti. HashMap autorise au maximum une clé nulle et plusieurs valeurs nulles. Il n'est pas thread-safe, ce qui peut entraîner des incohérences de données lorsque plusieurs threads y écrivent simultanément. Pour une utilisation thread-safe, on peut utiliser Collections.synchronizedMap ou ConcurrentHashMap.
- Hashtable : Classe héritée, fonctionnellement similaire à HashMap mais différente car elle hérite de Dictionary et est thread-safe. Sa concurrence est inférieure à celle de ConcurrentHashMap en raison de l'utilisation de verrous par segment. Hashtable est déconseillée dans le nouveau code.
- LinkedHashMap : Sous-classe de HashMap qui préserve l'ordre d'insertion. Lors de l'itération, les enregistrements obtenus d'abord sont ceux insérés en premier.
- TreeMap : Implémente l'interface SortedMap et permet de trier les enregistrements par clé, par ordre croissant par défaut, ou avec un Comparator personnalisé. Les clés doivent implémenter Comparable ou fournir un Comparator.
Pour ces implémentations, les clés doivent être des objets immuables dont la valeur de hashCode ne change pas après création. Sinon, la structure risque de ne pas pouvoir localiser la position du mappage.
Implémentation interne
HashMap est implémenté comme une combinaison de tableau, de liste chaînée et d'arbre rouge-noir (ajouté en JDK 1.8). Comprendre sa structure et ses méthodes est essentiel.
Structure de stockage - Champs
L'implémentation structurelle de HashMap repose sur un tableau de nœuds (tableau + liste chaînée + arbre rouge-noir). Le champ le plus important est le tableau Node[] table, qui est un tableau de nœuds. Voici la définition du nœud :
static class Entree<k> implements Map.Entry<k> {
final int hash; // Utilisé pour localiser l'index du tableau
final K cle;
V valeur;
Entree<k> suivant; // Le nœud suivant de la liste chaînée
Entree(int hash, K cle, V valeur, Entree<k> suivant) { ... }
public final K getCle(){ ... }
public final V getValeur() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValeur(V nouvelleValeur) { ... }
public final boolean equals(Object o) { ... }
}</k></k></k></k>
HashMap utilise une table de hachage pour le stockage. Pour gérer les collisions, Java utilise la méthode d'adressage chaîné : chaque élément du tableau contient une structure de liste chaînée. Lorsqu'un élément est hashé, son index est calculé et l'élément est placé dans la liste correspondante.
Plusieurs champs importants :
int seuil: Limite maximale de paires clé-valeurfinal float facteurCharge: Facteur de charge (par défaut 0.75)int modCount: Nombre de changements structurelsint taille: Nombre actuel de paires clé-valeur
La longueur du tableau table doit être une puissance de 2. Le seuil est calculé comme : seuil = longueur × facteurCharge. Lorsque le nombre d'éléments dépasse ce seuil, un redimensionnement (resize) est effectué, doublant la capacité.
En JDK 1.8, une optimisation majeure a été introduite : lorsque la longueur d'une liste chaînée dépasse un certain seuil (par défaut 8), elle est convertie en arbre rouge-noir pour améliorer les performances des opérations.
Fonctionnalité - Méthodes
1. Détermination de la position dans le tableau de hachage
L'index dans le tableau de hachage est déterminé par un algorithme de hachage à trois étapes :
static final int hacher(Object cle) {
int h;
return (cle == null) ? 0 : (h = cle.hashCode()) ^ (h >>> 16);
}
static int indexPour(int h, int longueur) {
return h & (longueur - 1);
}
Cet algorithme calcule d'abord le hashCode de la clé, effectue un opération XOR avec les bits de poids fort, puis utilise un ET binaire avec (longueur-1) pour obtenir l'index.
2. Analyse de la méthode put
La méthode put de HashMap suit le processus suivant :
- Vérifie si le tableau de hachage est vide et effectue un redimensionnement si nécessaire
- Calcule l'index basé sur la clé et le hash
- Si la position est vide, crée un nouveau nœud
- Si la position n'est pas vide, vérifie si la clé existe déjà
- Si une structure d'arbre est détectée, insère dans l'arbre
- Sinon, parcourt la liste chaînée, la convertissant en arbre si nécessaire
- Vérifie si le dépassement de la capacité maximale nécessite un redimensionnement
public V ajouter(K cle, V valeur) {
return mettreValeur(hacher(cle), cle, valeur, false, true);
}
final V mettreValeur(int hash, K cle, V valeur, boolean seulementSiAbsent,
boolean evict) {
Entree<k>[] tab; Entree<k> p; int n, i;
// Étape 1 : Si le tableau est vide, le créer
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = redimensionner()).length;
// Étape 2 : Calculer l'index et traiter null
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = nouveauNoeud(hash, cle, valeur, null);
else {
Entree<k> e; K k;
// Étape 3 : La clé existe déjà, remplacer la valeur
if (p.hash == hash &&
((k = p.cle) == cle || (cle != null && cle.equals(k))))
e = p;
// Étape 4 : Vérifier si c'est un arbre
else if (p instanceof ArbreNoirRouge)
e = ((ArbreNoirRouge<k>)p).ajouterArbre(this, tab, hash, cle, valeur);
// Étape 5 : C'est une liste chaînée
else {
for (int compte = 0; ; ++compte) {
if ((e = p.suivant) == null) {
p.suivant = nouveauNoeud(hash, cle, valeur, null);
// Convertir en arbre si la liste est trop longue
if (compte >= SEUIL_ARBO - 1)
arboriserTab(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.cle) == cle || (cle != null && cle.equals(k))))
break;
p = e;
}
}
if (e != null) {
V ancienneValeur = e.valeur;
if (!seulementSiAbsent || ancienneValeur == null)
e.valeur = valeur;
apresAccesNoeud(e);
return ancienneValeur;
}
}
++modCount;
// Étape 6 : Dépassement de capacité, redimensionner
if (++taille > seuil)
redimensionner();
apresInsertionNoeud(evict);
return null;
}</k></k></k></k>
3. Mécanisme de redimensionnement
Le redimensionnement (resize) est un processus coûteux où un tableau plus grand remplace l'ancien. En JDK 1.8, ce processus a été optimisé :
final Entree<k>[] redimensionner() {
Entree<k>[] ancienTab = table;
int ancienneCapacite = (ancienTab == null) ? 0 : ancienTab.length;
int ancienSeuil = seuil;
int nouvelleCapacite, nouveauSeuil = 0;
if (ancienneCapacite > 0) {
// Dépasser la capacité maximale, ne plus redimensionner
if (ancienneCapacite >= CAPACITE_MAXIMALE) {
seuil = Integer.MAX_VALUE;
return ancienTab;
}
// Redimensionner à 2 fois la capacité actuelle
else if ((nouvelleCapacite = ancienneCapacite << 1) < CAPACITE_MAXIMALE &&
ancienneCapacite >= CAPACITE_INITIALE)
nouveauSeuil = ancienSeuil << 1;
}
else if (ancienSeuil > 0)
nouvelleCapacite = ancienSeuil;
else {
nouvelleCapacite = CAPACITE_INITIALE;
nouveauSeuil = (int)(FACTEUR_CHARGE_DEFAUT * CAPACITE_INITIALE);
}
// Calculer le nouveau seuil de redimensionnement
if (nouveauSeuil == 0) {
float ft = (float)nouvelleCapacite * facteurCharge;
nouveauSeuil = (nouvelleCapacite < CAPACITE_MAXIMALE && ft < (float)CAPACITE_MAXIMALE ?
(int)ft : Integer.MAX_VALUE);
}
seuil = nouveauSeuil;
@SuppressWarnings({"rawtypes", "unchecked"})
Entree<k>[] nouveauTab = (Entree<k>[])new Entree[nouvelleCapacite];
table = nouveauTab;
if (ancienTab != null) {
// Déplacer chaque compartiment vers les nouveaux compartiments
for (int j = 0; j < ancienneCapacite; ++j) {
Entree<k> e;
if ((e = ancienTab[j]) != null) {
ancienTab[j] = null;
if (e.suivant == null)
nouveauTab[e.hash & (nouvelleCapacite - 1)] = e;
else if (e instanceof ArbreNoirRouge)
((ArbreNoirRouge<k>)e).diviser(this, nouveauTab, j, ancienneCapacite);
else { // Optimisation du re-hachage pour les listes chaînées
Entree<k> teteBas = null, queueBas = null;
Entree<k> teteHaut = null, queueHaut = null;
Entree<k> suivant;
do {
suivant = e.suivant;
// Ancien index
if ((e.hash & ancienneCapacite) == 0) {
if (queueBas == null)
teteBas = e;
else
queueBas.suivant = e;
queueBas = e;
}
// Ancien index + ancienne capacité
else {
if (queueHaut == null)
teteHaut = e;
else
queueHaut.suivant = e;
queueHaut = e;
}
} while ((e = suivant) != null);
// Placer à l'ancien index
if (queueBas != null) {
queueBas.suivant = null;
nouveauTab[j] = teteBas;
}
// Placer à l'ancien index + ancienne capacité
if (queueHaut != null) {
queueHaut.suivant = null;
nouveauTab[j + ancienneCapacite] = teteHaut;
}
}
}
}
}
return nouveauTab;
}</k></k></k></k></k></k></k></k></k>
Sécurité des threads
HashMap n'est pas thread-safe. Dans un environnement multi-thread, son utilisation peut conduire à des boucles infinies ou à des incohérences de données. Par exemple, pendant une opération de redimensionnement simultanée par plusieurs threads, des références cycliques peuvent se former dans les listes chaînées.
Pour une utilisation thread-safe, il est recommandé d'utiliser ConcurrentHashMap à la place.
Comparaison des performances : JDK 1.8 vs JDK 1.7
Les optimisations introduites dans JDK 1.8 améliorent significativement les performances de HashMap :
- Cas de hachage uniforme : Lorsque la distribution des clés est uniforme, JDK 1.8 montre une performance supérieure à JDK 1.7 d'environ 15% ou plus.
- Cas de hachage non uniforme : Lorsque toutes les clés ont le même hashCode (pire cas), JDK 1.8 maintient des performances stibles avec une complexité logarithmique grâce à l'introduction des arbres rouge-noir, tandis que JDK 1.7 montre une dégradation linéaire des performances.
Conseils d'utilisation
- Évitez les redimensionnements fréquents en estimant la taille initiale appropriée
- Ne modifiez pas le facteur de charge sauf cas spéciaux
- Utilisez ConcurrentHashMap pour les environnements multi-thread
- L'implémentation JDK 1.8 avec arbres rouge-noir offre de meilleures performances pour les cas de collision fréquents