Une table de hachage échange un peu de mémoire et une conception soignée contre l’une des promesses les plus utiles de l’informatique : retrouver une valeur à partir de sa clé en temps constant attendu.
L’idée centrale
Une fonction de hachage transforme une clé en nombre. Ce nombre, ramené à la taille de la table, désigne une case d’un tableau. Pour chercher « Maria », le programme calcule le hachage, saute directement à la case et regarde ce qu’elle contient. Il n’y a rien à parcourir depuis le début.
Les collisions sont normales
Deux clés différentes peuvent tomber dans la même case. Une bonne table s’y attend. Le chaînage garde une petite liste dans chaque case. L’adressage ouvert cherche la prochaine case libre. Les deux méthodes fonctionnent bien tant que la table n’est pas trop remplie.
Facteur de charge et redimensionnement
Le facteur de charge est le nombre d’éléments divisé par le nombre de cases. Quand il augmente, les collisions deviennent plus fréquentes et les opérations ralentissent. La plupart des implémentations agrandissent alors le tableau, souvent en le doublant, puis réinsèrent tous les éléments. Cette reconstruction est coûteuse mais rare, donc le coût moyen d’une insertion reste faible.
À retenir
- La recherche, l’insertion et la suppression sont en O(1) en moyenne, mais peuvent tomber à O(n) si beaucoup de clés entrent en collision.
- Une table de hachage ne garde pas les clés triées. Pour un parcours ordonné ou des requêtes par intervalle, un arbre équilibré convient mieux.
- Les clés doivent être hachables et ne doivent pas changer tant qu’elles sont stockées.
Quand l’utiliser
Pensez à une table de hachage quand la question est « ai-je déjà vu cet élément ? », « combien de fois ? » ou « quelle est la valeur associée à cette clé ? ». Compter des mots, mettre des résultats en cache et repérer des doublons s’y prêtent naturellement.
Pour aller plus loin
Retrouvez le traitement complet, les exemples et les exercices dans Les algorithmes en clair.
Adapté de Les algorithmes en clair, publié par Choral Software. Texte de l’article et exemples originaux © 2026 Choral Software. Tous droits réservés.