Qu'est-ce que Table de hachage (hash table) ?
Structure de données qui calcule une position de stockage à partir d'une clé au moyen d'une fonction de hachage, ce qui permet la recherche, l'insertion et la suppression en O(1) en moyenne. Les collisions, où des clés différentes tombent sur la même position, sont traitées par chaînage ou par adressage ouvert.
Nom japonais: ハッシュテーブル
« Table de hachage (hash table) » apparaît dans 7 questions d'entraînement réparties sur 4 thèmes, dont Structures de données et algorithmes, Probabilités, statistiques et files d'attente, Hiérarchie mémoire.
Domaine: Structures de données et algorithmes
Fonctionnement et traitement des collisions
Une table de hachage convertit une clé en entier au moyen d'une fonction de hachage et utilise, par exemple, le reste de sa division par la taille de la table comme position de stockage. Il existe beaucoup plus de clés possibles que de positions, si bien que les collisions, où des clés différentes tombent sur la même position, sont inévitables. Le chaînage relie les éléments d'une même position, par exemple dans une liste chaînée. L'adressage ouvert cherche une autre position libre dans la table, avec des méthodes comme le sondage linéaire, qui examine tour à tour les positions voisines, ou le double hachage, qui utilise une seconde fonction de hachage pour choisir le pas.
Facteur de charge et rehachage
Le nombre d'éléments stockés divisé par la taille de la table s'appelle le facteur de charge. Avec le chaînage, la longueur moyenne des listes est proportionnelle au facteur de charge ; avec l'adressage ouvert, le nombre de sondages pour trouver un emplacement libre augmente fortement quand le facteur de charge approche de 1. Quand le facteur de charge dépasse une limite choisie, on agrandit donc la table, généralement à environ deux fois sa taille, et on réinsère tous les éléments (rehachage). Un rehachage coûte O(n), mais comme les intervalles entre agrandissements doublent à chaque fois, le coût par insertion reste en O(1) amorti.
Performances et précautions
La moyenne en O(1) suppose que la fonction de hachage répartit les clés uniformément dans la table. Une mauvaise fonction de hachage, ou une entrée conçue pour provoquer des collisions (attaque par inondation de hachage, hash flooding), peut dégrader les performances jusqu'à O(n) dans le pire cas : les serveurs web et les logiciels similaires utilisent donc des fonctions de hachage mélangées à une graine aléatoire. Une table de hachage ne conserve pas non plus ses éléments dans l'ordre : les arbres binaires de recherche ou les arbres B conviennent mieux aux recherches par intervalle et aux listages ordonnés. La vitesse réelle dépend aussi du comportement du cache : les méthodes qui examinent les emplacements voisins, comme le sondage linéaire, sont souvent plus rapides que le chaînage, qui suit des pointeurs.
Questions fréquentes
Quel est le lien entre tables de hachage et fonctions de hachage ?
Une fonction de hachage calcule à partir d'une clé une valeur comprise dans un intervalle fixe, et une table de hachage est une structure de données qui l'utilise pour calculer des positions de stockage. Les fonctions de hachage pour tables de hachage privilégient la rapidité et une répartition uniforme, et n'ont généralement pas besoin d'être à sens unique comme les fonctions de hachage cryptographiques.
Où utilise-t-on les tables de hachage ?
Partout où il faut retrouver rapidement des valeurs par leur clé : dictionnaires (tableaux associatifs) et ensembles des langages de programmation, tables des symboles des compilateurs, jointures par hachage et index par hachage des bases de données, gestion des caches, etc.