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é touches, qui se jumelé avec une liste correspondante de valeurs, appelé un tableau. Par exemple, un nom d'entreprise pourrait se jumelé avec son adresse. Typiquement, chaque valeur de la matrice a un numéro de position appelée une table de hachage. La fonction de hachage est généralement un ensemble d'instructions ou un algorithme qui associe à chaque valeur de clé de hachage - connexion, le nom de l'entreprise à son adresse, son numéro de téléphone et sa catégorie d'entreprise, par exemple. Le but de la fonction de hachage est d'associer chaque touche correspondant à une valeur unique dans la matrice; ce qui est communément désigné sous le hachage. Les fonctions de hachage doivent être correctement formatés pour une table de hachage pour 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 fournit généralement pour une recherche uniforme de touches et une répartition uniforme de mappages dans le tableau correspondant. Une collision de hachage se produit lorsque deux touches sont affectées à la même valeur correspondant. Lors d'une collision de hachage se produit, la fonction de hachage est généralement exécutée à nouveau jusqu'à une valeur correspondant unique est trouvé; il en résulte souvent en plus temps de hachage. Bien que le nombre de clés dans une table de hachage est généralement fixe, parfois il peut y avoir un double des clés. Même si, une table de hachage bien conçu a des fonctions de hachage efficaces qui correspondent chaque touche pour une valeur correspondant unique dans le tableau.
Parfois, les fonctions de hachage inefficaces dans une table de hachage peuvent également produire un ensemble de mappages. Si une fonction de hachage crée un groupe de mappages de touches existantes, ce qui peut augmenter la quantité de temps qu'il faut pour rechercher les valeurs correspondantes. Cela peut ralentir le hachage des clés de demain, car la plupart des fonctions de hachage recherchent généralement la position suivante disponible dans le tableau. Si un grand ensemble de valeurs a déjà été attribué, il généralement faudrait beaucoup plus de temps à chercher 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 hashings déjà existants en ce qui concerne la taille globale de la matrice correspondant à une table de hachage. Elle est généralement définie en divisant le nombre de clés déjà attribués par la taille de la matrice correspondante.Comme le facteur de charge augmente, une bonne fonction de hachage est normalement toujours maintenir un nombre constant de collisions et les clusters jusqu'à un certain point.Souvent, ce seuil peut être utilisée pour déterminer le degré d'efficacité de fonction de hachage est avec un nombre donné de touches et si une nouvelle fonction de hachage peut être nécessaire.
Beaucoup de chercheurs en informatique se sont efforcés de produire la fonction de hachage parfait - celui qui ne produit pas de collisions ou des groupes donnés un facteur d'augmentation de la charge. En théorie, la clé pour produire une table de hachage parfaite est de produire une fonction de hachage parfait. En général, les chercheurs croient que la fonction de hachage parfait devrait avoir des performances constantes - le nombre de collisions et de groupes - avec un facteur de charge croissante. Dans le pire des cas, une fonction de hachage parfaite permettrait encore de hachage constant sans atteindre un seuil.
