Table de hachage
tableau associatif pour le stockage des paires de valeur-clé / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Table de hachage?
Résumez cet article pour un enfant de 10 ans
Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif. Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie.
Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » ().
Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes.
Il s'agit d'un tableau ne comportant pas d'ordre (contrairement à un tableau ordinaire qui est indexé par des entiers). On accède à chaque valeur du tableau par sa clé, qui, transformée par une fonction de hachage en une valeur de hachage (un nombre), indexe les éléments de la table, ces derniers étant appelés alvéoles (en anglais, buckets ou slots).
Le fait de créer une valeur de hachage à partir d'une clé peut engendrer un problème de collision, c’est-à-dire que deux clés différentes, voire davantage, pourront se retrouver associées à la même valeur de hachage et donc à la même alvéole (les fonctions de hachage ne sont pas injectives). Pour diminuer les risques de collisions, il faut donc premièrement choisir avec soin sa fonction de hachage. Ensuite, un mécanisme de résolution des collisions sera à implémenter si nécessaire. Il faudra alors stocker dans les alvéoles la paire clé–valeur et pas uniquement la valeur, afin de pouvoir comparer la clé avec celle qui sera donnée en entrée.
Tout comme les tableaux ordinaires, les tables de hachage permettent un accès en O(1) en moyenne, quel que soit le nombre de paires clé–valeur dans la table. Toutefois, comme plusieurs paires clé–valeur peuvent se trouver dans la même alvéole, le temps d'accès dans le pire des cas peut être de O(n). Comparées aux autres tableaux associatifs, les tables de hachage sont surtout utiles lorsque le nombre de paires clé–valeur est très important[réf. nécessaire].
La position des paires clé–valeur dans une table de hachage est pseudo-aléatoire mais dépend de la fonction de hachage choisie et des clés utilisées. Cette structure n'est donc pas adaptée au feuilletage (browsing) de données voisines. Des types de structures de données comme les arbres équilibrés, généralement plus lents (en O(log n)) et un peu plus complexes à implémenter, maintiennent une structure ordonnée.