Pourquoi les 5381 et 33 sont-ils si importants dans l'algorithme djb2?

cette fonction de hachage est similaire à un générateur de congruence linéaire (LCG-une classe simple de fonctions qui génèrent une série de psuedo-nombres aléatoires), qui a généralement la forme:

X = (a * X) + c;  // "mod M", where M = 2^32 or 2^64 typically

remarquez la similitude avec la fonction de hachage djb2... a = 33, M = 2^32. Pour qu'un LCG ait une " période complète "(c'est-à-dire aussi aléatoire que possible), a doit avoir certaines propriétés:

• a-1 est divisible par tous les facteurs principaux de M (a-1 est 32, qui est divisible par 2, le seul facteur principal de 2^32)
• a-1 est un multiple de 4 si M est un multiple de 4 (oui et oui)

En outre, c et M sont censés être relativement premier (ce qui sera vrai pour les valeurs de c ).

comme vous pouvez le voir, cette fonction de hachage quelque peu ça ressemble à un bon LCG. Et quand il s'agit de fonctions de hachage, vous en voulez une qui produit une distribution "aléatoire" de valeurs de hachage à partir d'un ensemble réaliste de chaînes d'entrée.

quant à la raison pour laquelle cette fonction de hachage est bonne pour les cordes, je pense qu'elle a un bon équilibre d'être extrêmement rapide, tout en fournissant une distribution raisonnable des valeurs de hachage. Mais j'ai vu beaucoup d'autres fonctions de hachage qui prétendent avoir de bien meilleures caractéristiques de sortie, mais beaucoup plus de lignes de code. Pour exemple voir cette page à propos des fonctions de hachage

EDIT: Cette bonne réponse explique pourquoi 33 et 5381 ont été choisis pour des raisons pratiques.

33 a été choisi parce que:

1) comme indiqué précédemment, la multiplication est facile à calculer en utilisant shift et add.

2) comme vous pouvez le voir à partir de l'implémentation shift et add, l'utilisation de 33 fait deux copies de la plupart des bits d'entrée dans l'accumulateur de hachage, et puis propage ces bits relativement éloignés l'un de l'autre. Cela aide à produire de bonnes avalanches. Utiliser un décalage plus grand dupliquerait moins de bits, utiliser un décalage plus petit garderait des interactions de bits plus les interactions se propagent localement et prennent plus de temps à se propager.

3) le décalage de 5 est relativement premier à 32 (le nombre de bits dans le registre), ce qui aide avec l'avalanche. Bien qu'il reste assez de caractères dans la chaîne, chaque bit d'un octet d'entrée interagira éventuellement avec chaque bit d'entrée précédent.

4) le décalage de 5 est une bonne quantité de décalage lorsque l'on considère les données des caractères ASCII. On peut penser à un personnage ASCII 4-bits type de caractère sélecteur et 4 bits de caractères-de-sélecteur de type. E. g. les chiffres ont tous 0x3 dans les 4 premiers bits. Ainsi, un décalage de 8 bits ferait en sorte que les bits ayant une certaine signification interagissent principalement avec d'autres bits ayant la même signification. Un changement de 4 bits ou de 2 bits produirait de la même manière de fortes interactions entre des bits partageant les mêmes idées. Le décalage de 5 bits fait que plusieurs des quatre bits d'ordre inférieur d'un caractère interagissent fortement avec plusieurs des 4 bits supérieurs du même caractère.

comme indiqué ailleurs, le choix du 5381 n'est pas trop important et beaucoup d'autres choix devraient fonctionner ici aussi.

ce n'est pas une fonction de hachage rapide car elle traite l'entrée d'un caractère à la fois et n'essaie pas d'utiliser le parallélisme d'instruction. Cependant, il est facile d'écrire. La qualité de la sortie divisée par la facilité d'écriture du code est susceptible d'atteindre un point doux.

sur les processeurs modernes, la multiplication est beaucoup plus rapide qu'elle était lorsque cet algorithme a été développé et d'autres facteurs de multiplication (par exemple 2^13 + 2^5 + 1) peut avoir des performances similaires, une sortie légèrement meilleure, et être légèrement plus facile à écrire.

contrairement à une réponse ci-dessus, une bonne fonction de hachage non cryptographique ne veut pas produire une sortie aléatoire. Au lieu de cela, étant donné deux entrées qui sont presque identiques, il veut produire des extrants très différents. Si vous êtes valeurs d'entrée sont distribuées au hasard, vous n'avez pas besoin d'un bon hachage fonction, vous pouvez juste utiliser un ensemble arbitraire de bits à partir de votre entrée. Certaines des fonctions de hachage modernes (Jenkins 3, Murmur, probablement CityHash) produisent une meilleure distribution des sorties que les entrées aléatoires qui sont très semblables.

sur 5381, Dan Bernstein (djb2) dit dans cet article :

[...] pratiquement n'importe quel bon multiplicateur fonctionne. Je pense que vous vous souciez sur le fait que 31c + d NE COUVRE PAS toute la gamme raisonnable de hash valeurs si c et d sont entre 0 et 255. C'est pourquoi, quand j'ai découvert 33 fonction de hachage et commencé à l'utiliser dans mes compresseurs, j'ai commencé à avec une valeur de hachage de 5381. Je pense que vous trouverez que cela fait tout comme ainsi qu'un multiplicateur de 261.

le fil entier est ici si vous êtes intéressé.

Ozan Yigit a une page sur les fonctions de hachage qui dit:

[...] la magie du nombre 33 (pourquoi il fonctionne mieux que beaucoup d'autres constantes, prime ou pas) n'a jamais été expliquée de manière adéquate.

peut-être parce que 33 == 2^5 + 1 et beaucoup d'algorithmes de hachage utilisent 2^n + 1 comme leur multiplicateur?

crédit à Jerome Berger "151980920

Cela semble être confirmé par la version actuelle du logiciel djb2 originaire de: cdb

les notes que j'ai liées pour décrire le cœur de l'algorithme de hachage en utilisant h = ((h << 5) + h) ^ c pour faire le hachage... x << 5 est un moyen matériel rapide d'utiliser 2^5 comme multiplicateur.