Table de hachage

Carte Peu commune · n° 155602

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 ) {\displaystyle 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. 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...

Lire sur Wikipédia · Image Public domain