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. LaHashMaples range dans le même seau et les départage avecequals: d'où l'obligation de redéfinir les deux ensemble.- Clé composite
Une clé faite de plusieurs valeurs. En Java, un
recorden fait une en une ligne, avecequalsethashCodecorrects par construction.
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.