La classe HashMap est un incontournable des entretiens techniques pour les développeurs Java. Que vous soyez débutent ou architecte, sa structure interne permet d'évaluer vos connaissances sur les collections, mais aussi votre maîtrise des structures de données fondamentales et de la gestion de la mémoire dans la JVM.
L'évolution de HashMap : de Java 7 à Java 8
Historiquement, HashMap reposait sur un mécanisme de "hachage avec chaînage" utilisant un tableau de listes chaînées. Java 8 a introduit des optimisations majeures pour améliorer les performances en cas de fortes collisions : - Structure hybride : Au-delà d'un certain seuil, les listes chaînées sont transformées en arbres rouge-noir (Red-Black Trees). Alors qu'une recherche dans une liste est en $O(n)$, l'arbre garantit une complexité de $O(\log n)$, ce qui protège contre les scénarios de déni de service basés sur les collisions de hachage.
- Amélioration de l'adressage : La fonction de hachage a été simplifiée tout en restant efficace pour mieux répartir les clés dans le tableau de base.
Analyse de la méthode d'insertion (put)
L'opération put(K key, V value) est le cœur du fonctionnement de la map. Elle délègue sa logique à une méthode interne souvent nommée putVal. ```
public V put(K key, V value) {
return insererValeur(genererHash(key), key, value, false, true);
}
final V insererValeur(int hash, K cle, V valeur, boolean seulementSiAbsent, boolean evict) { Node<K,V>[] tableNoeuds; Node<K,V> noeudActuel; int tailleTable, index;
// Initialisation paresseuse du tableau via resize()
if ((tableNoeuds = table) == null || (tailleTable = tableNoeuds.length) == 0) {
tailleTable = (tableNoeuds = redimensionner()).length;
}
// Calcul de l'index : (n - 1) & hash
index = (tailleTable - 1) & hash;
if ((noeudActuel = tableNoeuds[index]) == null) {
tableNoeuds[index] = creerNouveauNoeud(hash, cle, valeur, null);
} else {
Node<K,V> noeudCible = null;
K k;
// Cas 1 : La clé existe déjà sur le premier nœud
if (noeudActuel.hash == hash && ((k = noeudActuel.key) == cle || (cle != null && cle.equals(k)))) {
noeudCible = noeudActuel;
}
// Cas 2 : Le compartiment est déjà un arbre rouge-noir
else if (noeudActuel instanceof TreeNode) {
noeudCible = ((TreeNode<K,V>)noeudActuel).putTreeVal(this, tableNoeuds, hash, cle, valeur);
}
// Cas 3 : Parcours de la liste chaînée
else {
for (int compteurChainage = 0; ; ++compteurChainage) {
if ((noeudCible = noeudActuel.next) == null) {
noeudActuel.next = creerNouveauNoeud(hash, cle, valeur, null);
// Transformation en arbre si le seuil est atteint (TREEIFY_THRESHOLD = 8)
if (compteurChainage >= 7) {
transformerEnArbre(tableNoeuds, hash);
}
break;
}
if (noeudCible.hash == hash && ((k = noeudCible.key) == cle || (cle != null && cle.equals(k)))) {
break;
}
noeudActuel = noeudCible;
}
}
// Gestion de la mise à jour de la valeur
if (noeudCible != null) {
V ancienneValeur = noeudCible.value;
if (!seulementSiAbsent || ancienneValeur == null) {
noeudCible.value = valeur;
}
apresAccesNoeud(noeudCible);
return ancienneValeur;
}
}
++modCount;
if (++size > threshold) {
redimensionner();
}
apresInsertionNoeud(evict);
return null;
}
### Optimisation du calcul du Hash
Pour déterminer l'emplacement d'une clé, Java n'utilise pas directement le `hashCode()` natif de l'objet. Il applique une fonction de perturbation : ```
static final int genererHash(Object cle) {
int h;
return (cle == null) ? 0 : (h = cle.hashCode()) ^ (h >>> 16);
}
**Pourquoi ce décalage de 16 bits ?**Le tableau de HashMap a généralement une taille modeste (puissance de 2). L'index est calculé par (taille - 1) & hash. Sans le décalage, seuls les bits de poids faible du hashCode seraient utilisés. En effectuant un XOR entre les bits de poids fort (décalés de 16) et les bits de poids faible, on s'assure que toute la signature du hash contribue à l'indexation, réduisant ainsi les collisions. ### Le dilemme entre Liste et Arbre
Le passage d'une liste à un arbre rouge-noir s'effectue lorsque la liste atteint 8 éléments. Inversement, l'arbre redevient une liste si sa taille descend en dessous de 6 lors d'un redimensionnement. Cette décision repose sur un compromis espace/temps : - Un TreeNode occupe environ deux fois plus d'espace mémoire qu'un Node standard.
- Selon la distribution de Poisson, la probabilité qu'une liste atteigne 8 éléments avec un bon hash est extrêmement faible (environ 1 sur 10 millions). Le passage à l'arbre est donc une mesure de sécurité contre les mauvais algorithmes de hachage.
Le mécanisme de redimensionnement (resize)
Le redimensionenment est l'opération la plus coûteuse car elle implique de réorganiser les données. ``` final Node<K,V>[] redimensionner() { Node<K,V>[] ancienneTable = table; int ancienneCapacite = (ancienneTable == null) ? 0 : ancienneTable.length; int ancienSeuil = threshold; int nouvelleCapacite, nouveauSeuil = 0;
if (ancienneCapacite > 0) {
if (ancienneCapacite >= 1 << 30) {
threshold = Integer.MAX_VALUE;
return ancienneTable;
}
// Doublement de la capacité
nouvelleCapacite = ancienneCapacite << 1;
nouveauSeuil = ancienSeuil << 1;
} else if (ancienSeuil > 0) {
nouvelleCapacite = ancienSeuil;
} else {
nouvelleCapacite = 16;
nouveauSeuil = (int)(0.75f * 16);
}
threshold = nouveauSeuil;
Node<K,V>[] nouvelleTable = (Node<K,V>[])new Node[nouvelleCapacite];
table = nouvelleTable;
if (ancienneTable != null) {
for (int j = 0; j < ancienneCapacite; ++j) {
Node<K,V> e;
if ((e = ancienneTable[j]) != null) {
ancienneTable[j] = null;
if (e.next == null) {
nouvelleTable[e.hash & (nouvelleCapacite - 1)] = e;
} else if (e instanceof TreeNode) {
((TreeNode<K,V>)e).split(this, nouvelleTable, j, ancienneCapacite);
} else {
// Préservation de l'ordre et séparation en deux groupes
Node<K,V> teteBasse = null, queueBasse = null;
Node<K,V> teteHaute = null, queueHaute = null;
Node<K,V> suivant;
do {
suivant = e.next;
// Ce bit permet de savoir si l'élément reste au même index ou se déplace
if ((e.hash & physiqueCapacite) == 0) {
if (queueBasse == null) teteBasse = e;
else queueBasse.next = e;
queueBasse = e;
} else {
if (queueHaute == null) teteHaute = e;
else queueHaute.next = e;
queueHaute = e;
}
} while ((e = suivant) != null);
if (queueBasse != null) {
queueBasse.next = null;
nouvelleTable[j] = teteBasse;
}
if (queueHaute != null) {
queueHaute.next = null;
nouvelleTable[j + ancienneCapacite] = teteHaute;
}
}
}
}
}
return nouvelleTable;
}
Lors du transfert, `HashMap` utilise une astuce binaire élégante. Comme la capacité double toujours (puissance de 2), un élément soit reste au même index `j`, soit se déplace à l'index `j + ancienneCapacité`. Cela est déterminé par le bit correspondant à la nouvelle puissance de 2 dans le hash de la clé. ### Récupération des données (get)
La méthode `get(Object key)` est plus simple. Elle calcule le hash, localise l'index et vérifie d'abord le premier nœud. S'il ne correspond pas, elle délègue la recherche à l'arbre ou parcourt la liste chaînée. La comparaison se base toujours sur l'égalité des hashs suivie de la méthode `equals()` pour garantir l'exactitude malgré les collisions potentielles.