Le hashmap : O(1) au lieu de O(n)
La structure la plus utile pour transformer une recherche répétée en accès instantané.
Un hashmap (table de hachage) associe des clés à des valeurs. Une fonction de hachage transforme la clé en index de tableau, ce qui permet en moyenne un accès, une insertion et une suppression en O(1).
Collisions : deux clés peuvent produire le même index. On les gère par chaînage (une liste dans chaque case) ou par adressage ouvert (chercher la case libre suivante). Bien dimensionné, un hashmap reste O(1) en moyenne — mais le pire cas théorique (beaucoup de collisions) est O(n).
Usage typique en entretien : remplacer une recherche linéaire répétée (O(n) à chaque fois) par une consultation O(1) dans un hashmap déjà construit. C'est souvent exactement le « travail redondant » qu'on cherche à éliminer d'après la méthode vue en Phase 0.
Exemple canonique — Two Sum : au lieu de comparer chaque paire d'éléments (O(n²)), on stocke chaque valeur vue avec son index dans un hashmap ; pour chaque nouvel élément, on vérifie en O(1) si son complément existe déjà. Résultat : O(n) au lieu de O(n²).
Un `Set` est un hashmap sans valeurs — juste des clés. Utile pour tester rapidement une appartenance ou repérer des doublons. En JS/Python/Java, utilise directement `Map`/`dict`/`HashMap` : pas besoin de réimplémenter la structure en entretien, sauf si on te le demande explicitement.
Vidéo
NeetCode — Arrays & Hashing (playlist) — NeetCodeQuiz
1. Pourquoi l'accès à une clé dans un hashmap est-il en moyenne O(1) ?
2. Une collision se produit quand :
3. Sur Two Sum, un hashmap fait passer la complexité de O(n²) à O(n) parce que :
4. Un `Set` se décrit le mieux comme :