Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › La HashMap comme index : le réflexe qui casse les O(n²)

La HashMap comme index : le réflexe qui casse les O(n²)

Maps, Sets et regroupementsintermediaire

Dès qu'un exercice demande « ai-je déjà vu ceci ? » ou « où se trouve cela ? », la réponse est une HashMap ou un HashSet — et un O(n²) devient un O(n).

Le motif « déjà vu », en un seul passage :

// Deux éléments de somme cible, tableau NON trié, index d'origine conservés
static int[] sommeDeux(int[] t, int cible) {
    Map<Integer, Integer> vus = new HashMap<>();     // valeur → index
    for (int i = 0; i < t.length; i++) {
        Integer j = vus.get(cible - t[i]);           // interroger AVANT d'insérer
        if (j != null) return new int[]{j, i};
        vus.put(t[i], i);
    }
    return new int[]{-1, -1};
}

L'ordre des deux opérations n'est pas anodin : interroger avant d'insérer empêche un élément de se marier avec lui-même quand cible = 2 × t[i].

Le premier doublon tient en trois lignes :

Set<Integer> vus = new HashSet<>();
for (int x : t) if (!vus.add(x)) return x;    // add renvoie false si déjà présent

Les clés composites se font avec un record :

record Cle(String ville, int annee) {}
Map<Cle, Integer> ventes = new HashMap<>();
ventes.merge(new Cle("Lyon", 2026), 1, Integer::sum);

Et la règle sans laquelle rien ne marche : equals et hashCode se redéfinissent ensemble. Un record le fait pour vous.

Les termes à connaître

Index inversé

Une Map qui associe une valeur à sa position, ou à l'ensemble des éléments qui la portent. Elle remplace une recherche linéaire répétée par un accès en O(1).

Motif « déjà vu »

Mémoriser au fil du parcours ce qu'on a rencontré, pour répondre instantanément à « ai-je déjà croisé cette valeur ? ». Le motif qui résout two-sum, la détection de doublon et bien d'autres.

Complément

Dans une recherche de somme, la valeur manquante : cible - courant. La chercher dans les éléments déjà vus évite la double boucle.

Un seul passage

Remplir et interroger la Map dans la même boucle. Cela suffit presque toujours, et évite un second parcours — à condition d'interroger avant d'insérer.

Collision de clés

Deux clés différentes avec le même hashCode. La HashMap les range dans le même seau et les départage avec equals : d'où l'obligation de redéfinir les deux ensemble.

Clé composite

Une clé faite de plusieurs valeurs. En Java, un record en fait une en une ligne, avec equals et hashCode corrects par construction.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.