Qu'est-ce qu'un hachage?
Dans l'informatique, un hachage est une structure de données pour stocker des données qui se compose d'une liste de valeurs, appelées 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 mappe chaque valeur clé à un hachage - reliant 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'attribuer chaque clé à une valeur correspondante unique dans le tableau; Ceci est communément appelé hachage. Les fonctions de hachage doivent être correctement formatées pour un hachage pour fonctionner correctement.
Les performances d'un hachage sur un ensemble de données dépendent de l'efficacité de sa fonction de hachage. Une bonne fonction de hachage typiqueAlly prévoit 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 correspondante 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 un hachage soit généralement fixe, il peut parfois y avoir des clés en double. Même ainsi, un hashtable bien conçu a des fonctions de hachage efficaces qui mappent chaque clé d'une valeur correspondante unique dans le tableau.
Parfois, les fonctions de hachage inefficaces dans un hachage peuvent également produire un groupe de mappages. Si une fonction de hachage crée un groupe de mappages pour les clés existantes, cela peut augmenter le temps nécessaire pour rechercher les valeurs correspondantes. Cela peut ralentir le hachage des clés futures, car la plupart des fonctions de hachage recherchent généralement la prochaine position disponible dans le tableau. Si un grand clusterDes valeurs ont déjà été attribuées, il faudrait 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 réseau correspondant dans un hashtable. 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 maintiendra 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 lorsqu'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 - qui ne produit aucune collision ni grappes avec un facteur de charge croissant. En théorie, la clé pour produire un hashtable parfait est de profaire une fonction de hachage parfaite. En général, les chercheurs pensent qu'une fonction de hachage parfaite devrait avoir des performances constantes - le nombre de collisions et de grappes - avec un facteur de charge croissant. Dans le pire des cas, une fonction de hachage parfaite permettrait toujours un hachage constant sans atteindre un seuil.