public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    // Implémentation interne
}

Cette déclaration indique clairement que la classe hérite de AbstractMap et implémente le contrat de base défini par l'interface Map, tout en étant clonable et sérialisable.

Architecture et Champs Internes

Pour comprendre son comportement, il est nécessaire d'examiner les attributs principaux qui régissent sa gestion mémoire et ses opérations.

// Capacité initiale par défaut (2^4 = 16)
static final int CAPACITE_INITIALE_DEF = 1 << 4;
// Taille maximale autorisée (2^30)
static final int TAILLE_MAXIMALE = 1 << 30;
// Facteur de charge standard
static final float FACTEUR_CHARGE_DEF = 0.75f;
// Seuils pour la transformation Arbre/Liste
static final int SEUIL_ARBORISATION = 8;
static final int SEUIL_DESBORISATION = 6;
// Capacité minimale requise avant arborisation
static final int CAPACITE_MINI_ARBRE = 64;

// Le tableau principal contenant les cellules
transient Nœud<K,V>[] entrepot;
// Nombre d'éléments stockés
transient int taille;
// Limite déclenchant le redimensionnement
int seuil;
float facteurCharge;

L'attribut clé est entrepot (communément appelé table), qui est un tableau de références vers des objets de type Nœud. Chaque case de ce tableau, ou cellule, pointe soit vers une liste simple, soit vers un arbre rouge-noir en fonction de la densité des collisions.

Héritage des Nœuds

La hiérarchie des classes représentant les entrées est structurée comme suit :

1. Map.Entry : Interface abstraite définissant la paire clé-valeur.
2. Nœud (HashMap.Node) : Implémente Map.Entry. Ajoute hash, clé, valeur et suivant.
3. EntréeOrdre (LinkedHashMap.Entry) : Étend Nœud. Gère l'ordre d'insertion via avant et après.
4. NœudArbre (HashMap.TreeNode) : Étend EntréeOrdre. Ajoute la logique d'arbre (père, gauche, droit, couleur).

Lors de l'insertion dans entrepot, le type réel dépendra de la configuration : des objets standards Nœud pour les chaînes courtes, et NœudArbre lorsque la chaîne atteint une certaine longueur critique.

Initialisation et Constructeurs

Le processus de création n'alloue pas immédiatement la mémoire du tableau. C'est une stratégie de chargement paresseux (lazy loading). Voici une vue simplifiée d'un constructeur typique :

public HashMap(int capInitiale, float facteur) {
    if (capInitiale < 0 || facteur <= 0) {
        throw new IllegalArgumentException("Paramètres invalides");
    }
    this.facteurCharge = facteur;
    // Calcul de la capacité réelle (puissance de 2 supérieure ou égale)
    this.seuil = alignerPuissanceDeux(capInitiale); 
}

La méthode alignerPuissanceDe2 (correspondant à tableSizeFor dans le JDK) assure toujours que la capacité interne est une puissance de deux (ex: 16, 32, 64...). Cela permet d'utiliser des opérations bit à la place du modulaire coûteux pour calculer les indices.

static final int alignerPuissanceDe2(int demande) {
    int n = demande - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= TAILLE_MAXIMALE) ? TAILLE_MAXIMALE : n + 1;
}

Opérations Fondamentales

Récupération (get)

L'accélération des requêtes repose sur une fonction de hachage améliorée. Le calcul de l'indice de cellule ne se fait pas directement avec hashCode(), mais après un mélange des bits pour réduire les collisions systématiques.

static final int calculerHash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

public V recuperer(Object key) {
    int index = (tailleEntrepot - 1) & calculerHash(key);
    return obtenirValeur(entrepot[index], index, key);
}

Notez l'opération & (ET binaire) au lieu du modulo. Si la taille est une puissance de 2, alors (taille - 1) & hash est mathématiquement équivalent à hash % taille mais bien plus rapide pour le processeur.

Mis à jour et Insertion (put)

L'ajout d'une entrée vérifie d'abord si l'espace existe. Si non, un redimensionnement automatique peut être déclenché. Ensuite, la méthode navigue dans la liste ou l'arbre existant à cet index.

public V insérer(K key, V val) {
    return mettreVal(calculerHash(key), key, val, false, true);
}

final V mettreVal(int h, K k, V v, boolean uniqueSiAbsent, boolean evict) {
    Nœud<K,V>[] tab; Nœud<K,V> p; int cap, idx;
    
    // Initialisation si vide
    if ((tab = entrepot) == null || (cap = tab.length) == 0) {
        cap = (entrepot = redimensionner()).length;
    }
    
    // Cas : Case vide, insertion directe
    if ((p = tab[idx = (cap - 1) & h]) == null) {
        return tab[idx] = nouveauNœud(h, k, v, null);
    }
    
    // Cas : Collision, traitement selon le type (Liste ou Arbre)
    Nœud<K,V> e; K kk;
    if (p.hash == h && ((kk = p.key) == k || (k != null && k.equals(kk)))) {
        e = p; // Clé existante, remplacement potentiel
    } else if (p instanceof NœudArbre) {
        e = ((NœudArbre<K,V>)p).ajouterDansArbre(this, tab, h, k, v);
    } else {
        // Parcours de la liste chaînée
        for (int compteur = 0;; ++compteur) {
            if ((e = p.suivant) == null) {
                p.suivant = nouveauNœud(h, k, v, null);
                // Vérification seuil arborisation
                if (compteur >= SEUIL_ARBORISATION - 1) 
                    transformerEnArbre(tab, h);
                break;
            }
            if (e.hash == h && ((kk = e.key) == k || (k != null && k.equals(kk)))) 
                break;
            p = e;
        }
    }
    
    // Gestion de la valeur retournée et augmentation de la taille
    if (e != null) {
        V ancienne = e.valeur;
        if (!uniqueSiAbsent || ancienne == null) e.valeur = v;
        return ancienne;
    }
    
    taille++;
    if (taille > seuil) redimensionner();
    return null;
}

Mécanisme de Redimensionnement

Lorsque le nombre d'éléments dépasse seuil = capacité * facteurCharge, le tableau est doublé. La distribution des éléments existants est cruciale. Plutôt que de recalcuelr tous les hachages, Java exploite les propriétés binaires.

Si l'ancienne capacité était $N$, la nouvelle est $2N$. Pour chaque élément, seul le bit correspondant à $N$ détermine si l'élément reste à l'index initial ou passe à l'index + $N$.

final Nœud<K,V>[] redimensionner() {
    Nœud<K,V>[] ancienTableau = entrepot;
    int ancienneCap = (ancienTableau == null) ? 0 : ancienTableau.length;
    
    // Logique de calcul de la nouvelle capacité (omise pour brièveté, double généralement)
    int nouvelleCap = ancienneCap > 0 ? ancienneCap << 1 : CAPACITE_INITIALE_DEF;
    
    @SuppressWarnings({"rawtypes","unchecked"})
    Nœud<K,V>[] nouveauTableau = (Nœud<K,V>[])new Nœud[nouvelleCap];
    entrepot = nouveauTableau;
    
    if (ancienTableau != null) {
        for (int i = 0; i < ancienneCap; ++i) {
            Nœud<K,V> element = ancienTableau[i];
            if (element == null) continue;
            
            ancienTableau[i] = null;
            
            if (element.suivant == null) {
                // Cas singleton : recopie directe
                nouveauTableau[element.hash & (nouvelleCap - 1)] = element;
            } else if (element instanceof NœudArbre) {
                // Séparation de l'arbre rouge-noir
                ((NœudArbre<K,V>)element).scinder(this, nouveauTableau, i, ancienneCap);
            } else {
                // Séparation de la liste chaînée (Optimisation J.U.C.)
                Nœud<K,V> teteBas = null, queueBas = null;
                Nœud<K,V> teteHaut = null, queueHaut = null;
                
                do {
                    Nœud<K,V> suivant = element.suivant;
                    if ((element.hash & ancienneCap) == 0) {
                        // Reste à l'index i
                        if (queueBas == null) teteBas = element;
                        else queueBas.suivant = element;
                        queueBas = element;
                    } else {
                        // Passe à l'index i + ancienneCap
                        if (queueHaut == null) teteHaut = element;
                        else queueHaut.suivant = element;
                        queueHaut = element;
                    }
                    element = suivant;
                } while (element != null);
                
                // Assignation finale
                if (queueBas != null) {
                    queueBas.suivant = null;
                    nouveauTableau[i] = teteBas;
                }
                if (queueHaut != null) {
                    queueHaut.suivant = null;
                    nouveauTableau[i + ancienneCap] = teteHaut;
                }
            }
        }
    }
    return nouveauTableau;
}

Balancement Dynamique : Listes et Arbres

Pour éviter les attaques DoS par collision massive de hachages, HashMap convertit automatiquement une liste chaînée trop longue en un arbre rouge-noir. Cependant, cela se produit uniquement si la taille globale du tableau dépasse une certaine limite (CAPACITE_MINI_ARBRE). Sinon, une simple extension de capacité est préférée pour diluer les collisions.

La méthode transformerEnArbre effectue la conversion :

final void transformerEnArbre(Nœud<K,V>[] tab, int h) {
    int idx = (tab.length - 1) & h;
    if ((entropo = tab[idx]) != null) {
        NœudArbre<K,V> teteArbre = null, finChain = null;
        
        // Conversion des nœuds liste en nœuds arbre
        do {
            NœudArbre<K,V> noeudArb = remplacerParNoeudArbre(entropo, null);
            if (finChain == null) teteArbre = noeudArb;
            else {
                noeudArb.precedent = finChain;
                finChain.suivant = noeudArb;
            }
            finChain = noeudArb;
        } while ((entropo = entropo.suivant) != null);
        
        // Construction de la structure rouge-noir équilibrée
        if ((tab[idx] = teteArbre) != null)
            teteArbre.equilibrerArbre(tab);
    }
}

Inversement, lors d'un redimensionnement ou si la taille diminue drastiquement, les arbres peuvent redevenir des listes simples (désarborisation) via la méthode désarboriser, exploitant l'ordre de succession déjà conservé dans les nœuds pour éviter une reconstruction coûteuse.