Leçon 6 : tables de hachage et comptage de fréquences

Imagine un dictionnaire : tu ne le lis pas depuis le début, tu sautes directement au mot et tu obtiens sa définition. C'est exactement une table de hachage (hash map, en Python : dict) — une structure de paires clé-valeur qui sait sauter directement à une clé. Une vérification « ai-je déjà vu ça ? »

Une table de hachage, c'est comme l'index à la fin d'un livre : au lieu de feuilleter toutes les pages pour trouver un mot (c'est un « balayage » lent), tu regardes dans l'index et tu sautes directement à la bonne page (c'est O(1) — instantané). Le prix ? Un peu de papier en plus — c'est-à-dire un peu de mémoire supplémentaire contre beaucoup de vitesse.

table de hachage (hash map): Une structure qui fait correspondre une clé à une valeur et offre recherche et insertion en O(1) en moyenne, en calculant une adresse directement à partir de la clé. En Python, c'est un dict.
ensemble (set): Une collection sans doublons qui vérifie l'appartenance (un élément est-il présent) en O(1) en moyenne — utile pour repérer et supprimer les doublons.
comptage de fréquences: Compter combien de fois chaque valeur apparaît dans l'entrée à l'aide d'un dict qui associe valeur → compteur, en un seul passage O(n).