Une table de hachage (dictionnaire) offre des recherches, insertions et suppressions en O(1) en moyenne. Échanger O(n) de mémoire pour de la vitesse transforme de nombreux algorithmes O(n²) en O(n) en remplaçant les analyses répétées par des recherches instantanées.
L'idée
Au lieu de chercher dans une liste à chaque fois, stockez les valeurs vues dans une table de hachage et vérifiez l'appartenance en temps constant.
