Lors de la lecture de la documentation sur MSDN pour Object.GetHashCode méthode que je suis tombé sur des phrases comme la fonction de hachage devrait fournir une distribution aléatoire ou utile dans une table de hachage. Que signifie cette distribution en ce qui concerne la fonction de hachage ou la table de hachage?Que signifie "distribution de la fonction de hachage"?
Une fonction de hachage produit un entier de 32 bits dans le but d '"équilibrer" une table de hachage. Supposons que votre table comporte une centaine de "seaux" et que vous placiez des éléments dans la table dans un compartiment en fonction des deux chiffres décimaux inférieurs de la fonction de hachage.
Supposons maintenant que la fonction de hachage produit toujours des nombres pairs de centaines. Chaque élément va aller dans le même compartiment, et la table de hachage sera déséquilibrée. Ce serait une mauvaise fonction de hachage.
Un bon algorithme de hachage produit un peu près même la distribution peu importe combien de seaux que vous avez et peu importe comment extraire le numéro de seau du hachage.
Pour que les tables de hachage fonctionnent avec une efficacité maximale, les valeurs de hachage doivent être aussi uniques que possible pour éviter les collisions. Par exemple, considérons une fonction de hachage extrêmement naïve: disons que vos objets sont des prénoms et des noms, et pour votre valeur de hachage, vous choisissez les initiales. Donc, la valeur de hachage de Ginger Rodgers est GR et la valeur de hachage de Fred Astaire est FA. Jusqu'ici tout va bien, mais que se passe-t-il quand Frank Allen arrive avec une valeur de hachage de FA? Maintenant, vous avez une collision entre Fred Astaire et Frank Allen, et l'implémentation de la table de hachage doit gérer cela comme un cas particulier, ce qui réduit l'efficacité.
Les meilleures fonctions de hachage prennent l'espace d'entrée (Fred Astaire), et produisent une valeur aléatoire est (idéalement) unique à l'espace d'entrée. Tant que la taille de votre hachage est inférieure à la taille de vos données, il n'y a aucun moyen d'éviter complètement les collisions, mais elles doivent être minimisées en choisissant soigneusement l'algorithme de hachage.
Comme l'a souligné Eric ci-dessous, les tables de hachage pour équilibrer les tables de hachage doivent être très rapides, il faut donc trouver un équilibre entre la vitesse et les collisions. Vous pouvez étudier les algorithmes de hachage cryptographique comme SHA-1 (http://en.wikipedia.org/wiki/SHA-1) pour comprendre la complexité de la génération de hachages uniques, mais les algorithmes de hachage pour équilibrer les tables de hachage doivent être aussi rapides que possible .
Vous allez bien jusqu'à votre dernier paragraphe. Les exigences des fonctions de hachage cryptographiques et les exigences des fonctions de hachage pour équilibrer les tables de hachage sont très, très différentes et vous ne devriez pas confondre les deux. Vous ne devriez jamais utiliser un algorithme comme SHA1 pour équilibrer la table de hachage; Rappelez-vous, le point d'un algorithme d'équilibrage de table de hachage est que * c'est une optimisation de performance *, donc n'allez pas utiliser un algorithme de hachage * lent et compliqué! –
Bon point, Eric. J'essayais juste de signaler un algorithme de hachage qui fait un très bon travail pour éviter les collisions. Je vais mettre à jour ma réponse en conséquence. –
On pourrait choisir de hacher un entier de 32 bits en retournant simplement l'entier de 32 bits. Idéal pour équilibrer la table de hachage, terrible pour le hachage cryptographique. Je recommande de ne pas étudier les algorithmes de hachage cryptographique afin de comprendre les fonctions de hachage des tables de hachage. – Brian
http://en.wikipedia.org/wiki/Hash_table –
Grossièrement: Les valeurs de hachage doivent être "réparties de façon aléatoire sur leur domaine sans motif apparent" (par exemple, agglutination minimale et propagation maximale lorsqu'elles sont visualisées visuellement). De nombreuses implémentations de hachage * rehash * le hachage pour réduire le risque de "claquer" en cas de mise en seau. –