Qu'est-ce qu'une table de hachage?
En informatique, une table de hachage est une structure de données pour stocker des données qui consiste en une liste de valeurs, appelée clés, qui sont associées à une liste de valeurs correspondante, appelée tableau. Par exemple, un nom d'entreprise peut être associé à son adresse. En règle générale, chaque valeur du tableau a un numéro de position appelé hachage. La fonction de hachage est généralement un ensemble d'instructions ou un algorithme qui associe chaque valeur de clé à un hachage - connectant par exemple le nom de l'entreprise à son adresse, son numéro de téléphone et sa catégorie d'entreprise. Le but de la fonction de hachage est d'attribuer à chaque clé une valeur unique correspondante dans le tableau; Ceci est communément appelé hachage. Les fonctions de hachage doivent être correctement formatées pour qu'une table de hachage puisse fonctionner correctement.
La performance d'une table de hachage sur un ensemble de données dépend de l'efficacité de sa fonction de hachage. Une bonne fonction de hachage permet généralement une recherche uniforme des clés et une distribution uniforme des mappages dans le tableau correspondant. Une collision de hachage se produit lorsque deux clés sont affectées à la même valeur correspondante. Lorsqu'une collision de hachage se produit, la fonction de hachage est généralement exécutée à nouveau jusqu'à ce qu'une valeur unique unique soit trouvée. cela se traduit généralement par des temps de hachage plus longs. Bien que le nombre de clés dans une table de hachage soit généralement fixe, il peut parfois y avoir des clés en double. Malgré tout, une table de hachage bien conçue possède des fonctions de hachage efficaces qui associent chaque clé à une valeur unique correspondante dans le tableau.
Parfois, des fonctions de hachage inefficaces dans une table de hachage peuvent également produire un cluster de mappages. Si une fonction de hachage crée un cluster de mappages pour les clés existantes, cela peut augmenter le temps nécessaire à la recherche des valeurs correspondantes. Cela peut ralentir le hachage des futures clés car la plupart des fonctions de hachage recherchent généralement la prochaine position disponible dans le tableau. Si un grand groupe de valeurs a déjà été affecté, il faudra généralement beaucoup plus de temps pour rechercher une valeur non attribuée pour une nouvelle clé.
Le facteur de charge est un autre concept lié à l'efficacité d'une fonction de hachage; le facteur de charge est la quantité de hachages déjà existants par rapport à la taille globale du tableau correspondant dans une table de hachage. Il est généralement défini en divisant le nombre de clés déjà attribuées par la taille du tableau correspondant. À mesure que le facteur de charge augmente, une bonne fonction de hachage conserve normalement un nombre constant de collisions et de grappes jusqu'à un certain point. Souvent, ce seuil peut être utilisé pour déterminer l'efficacité d'une fonction de hachage avec un nombre donné de clés et le moment où une nouvelle fonction de hachage peut être nécessaire.
De nombreux chercheurs en informatique se sont efforcés de produire la fonction de hachage parfaite - une fonction qui ne produit pas de collision ou de grappes étant donné un facteur de charge croissant. En théorie, la clé pour produire une table de hachage parfaite est de produire une fonction de hachage parfaite. En général, les chercheurs pensent qu'une fonction de hachage parfaite devrait avoir une performance constante (nombre de collisions et de clusters) avec un facteur de charge croissant. Dans les cas les plus défavorables, une fonction de hachage parfaite permettrait toujours un hachage constant sans atteindre un seuil.