Programmation · concepts · structures de donnees

Qu'est-ce qu'une table de hachage ?

Une table de hachage (aussi appelee hash table ou hash map) est une structure de donnees qui stocke des paires cle-valeur et vous permet de retrouver n'importe quelle valeur par sa cle en, en moyenne, temps constant - quelle que soit la quantite de donnees qu'elle contient. C'est l'une des structures les plus utiles de toute la programmation, et c'est elle qui alimente les dictionnaires et les maps integres dans presque tous les langages. Une fois que vous comprenez son fonctionnement, beaucoup de moments "comment est-ce si rapide ?" prennent tout leur sens.

Le probleme qu'elle resout

Imaginez stocker un annuaire telephonique sous forme de simple liste. Pour trouver une personne, vous devriez peut-etre parcourir chaque entree - un travail lent qui ralentit a mesure que l'annuaire grandit, une operation O(n). La promesse d'une table de hachage est differente : donnez-lui la cle et elle saute plus ou moins directement a la valeur, sans parcourir quoi que ce soit. C'est la difference entre verifier chaque entree et savoir exactement ou regarder.

Comment ca marche : la fonction de hachage et les buckets

En dessous, une table de hachage repose sur un tableau d'emplacements appeles buckets. L'ingredient magique est la fonction de hachage (hash function) : elle prend votre cle et la transforme en un nombre, qui est associe a un index dans ce tableau.

index = hash(key) % number_of_buckets

Pour stocker une valeur, vous hachez la cle pour obtenir un index et placez la valeur dans ce bucket. Pour la relire, vous hachez de nouveau la meme cle, tombez sur le meme index, et recuperez la valeur. Comme calculer le hash et indexer un tableau sont deux etapes rapides a cout fixe, les recherches ne ralentissent pas a mesure que la table grandit. C'est toute l'astuce.

Les collisions, et comment elles sont gerees

Deux cles differentes peuvent produire le meme bucket. C'est ce qu'on appelle une collision, et toute vraie table de hachage doit la gerer. Il existe deux strategies courantes :

• Chaining : chaque bucket contient une petite liste, et les entrees en collision y sont stockees ensemble. Les recherches parcourent alors la liste (generalement tres courte) du bon bucket.
• Open addressing : si un bucket est occupe, la table sonde l'emplacement libre suivant selon une regle fixe, et les recherches suivent la meme regle.

Avec une bonne fonction de hachage et suffisamment de buckets, les collisions restent rares et ces listes restent minuscules, si bien que les recherches restent rapides.

Et les performances ?

C'est ici que les tables de hachage brillent, et c'est ici que se cache la mise en garde honnete. En moyenne, l'insertion, la recherche et la suppression sont toutes en O(1) - temps constant. Dans le pire des cas, si une mauvaise fonction de hachage ou une entree hostile entasse chaque cle dans un seul bucket, ces operations se degradent en O(n), parce que vous revenez a parcourir une seule longue liste. Les bonnes implementations evitent cela en utilisant des fonctions de hachage solides et en redimensionnant (rehachage dans un tableau plus grand) quand la table devient trop pleine, ce qui maintient la performance a un O(1) amorti. Si vous voulez une piqure de rappel sur cette notation, consultez notre guide sur la notation Big O.

Ou vous en utilisez deja une

Vous utilisez des tables de hachage en permanence, souvent sans les nommer. Les types dictionnaire et map de la plupart des langages sont des tables de hachage sous le capot : le dict de Python, le HashMap de Java, le Map de JavaScript et l'objet, le Hash de Ruby, le map de Go. Ce sont aussi l'outil de reference pour les caches, la de-duplication d'elements et le comptage d'occurrences. L'optimisation classique qui transforme une recherche lente a boucles imbriquees en une recherche rapide - passer de O(n²) a O(n) - se fait presque toujours en remplacant des parcours repetes par une recherche dans une table de hachage.

Les compromis

• Rapide, mais non ordonnee. Une table de hachage de base ne conserve pas les cles dans un ordre trie ou d'insertion (meme si certaines versions de langages ajoutent un ordre par-dessus).
• Utilise de la memoire supplementaire. Garder les collisions rares signifie garder des buckets libres, donc une table de hachage echange un peu de memoire contre sa vitesse.
• Le pire des cas est reel. Le O(1) est une moyenne ; une entree adverse peut forcer le chemin lent, ce qui compte pour du code sensible a la securite.

FAQ

Une table de hachage est-elle la meme chose qu'un dictionnaire ? Au quotidien, oui - un dictionnaire ou une map est l'idee generale (cle vers valeur), et une table de hachage est la maniere la plus courante de l'implementer. Quand quelqu'un parle du "dict" de Python ou du "HashMap" de Java, il utilise une table de hachage.

Pourquoi la recherche est-elle en O(1) en moyenne ? Parce que vous calculez le hash de la cle et indexez directement dans un tableau, plutot que de parcourir les entrees. Les deux etapes prennent un temps constant quel que soit le nombre d'elements stockes, donc le cout moyen n'augmente pas avec les donnees.

Qu'est-ce qu'une collision ? Quand deux cles differentes produisent le meme bucket. C'est normal et attendu ; les tables de hachage la gerent avec le chaining ou l'open addressing, et la gardent rare grace a une bonne fonction de hachage et au redimensionnement.

Quand ne devrais-je pas utiliser une table de hachage ? Quand vous avez besoin de garder les cles dans un ordre trie, ou pour des requetes ordonnees par plage - une structure a base d'arbre convient mieux. Egalement quand la memoire est extremement limitee, puisque les tables de hachage gardent de l'espace libre pour rester rapides.

Guides associes : notation Big O, ce qu'est un algorithme.