Raison pour le numéro 5381 dans la fonction de hachage de DJB?
Quelqu'un peut-il me dire pourquoi le numéro 5381 est utilisé dans la fonction de hachage DJB ?
la fonction de hachage DJB est
h (0) = 5381
h ( i) = 33 * h (i-1) ^ str [I]
Un programme c:
unsigned int DJBHash(char* str, unsigned int len)
{
unsigned int hash = 5381;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash = ((hash << 5) + hash) + (*str);
}
return hash;
}
3 réponses
5381 est juste un nombre qui, dans les essais, a entraîné moins de collisions et meilleure avalanche . Vous trouverez des "constantes magiques" dans à peu près chaque algue de hash.
je suis tombé sur un commentaire qui jette un peu de lumière sur ce que DJB est jusqu'à:
/*
* DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
*
* This is Daniel J. Bernstein's popular `times 33' hash function as
* posted by him years ago on comp.lang.c. It basically uses a function
* like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
* known hash functions for strings. Because it is both computed very
* fast and distributes very well.
*
* The magic of number 33, i.e. why it works better than many other
* constants, prime or not, has never been adequately explained by
* anyone. So I try an explanation: if one experimentally tests all
* multipliers between 1 and 256 (as RSE did now) one detects that even
* numbers are not useable at all. The remaining 128 odd numbers
* (except for the number 1) work more or less all equally well. They
* all distribute in an acceptable way and this way fill a hash table
* with an average percent of approx. 86%.
*
* If one compares the Chi^2 values of the variants, the number 33 not
* even has the best value. But the number 33 and a few other equally
* good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
* advantage to the remaining numbers in the large set of possible
* multipliers: their multiply operation can be replaced by a faster
* operation based on just one shift plus either a single addition
* or subtraction operation. And because a hash function has to both
* distribute good _and_ has to be very fast to compute, those few
* numbers should be preferred and seems to be the reason why Daniel J.
* Bernstein also preferred it.
*
*
* -- Ralf S. Engelschall <rse@engelschall.com>
*/
c'est une fonction de hachage légèrement différente de celle que vous regardez, bien qu'elle utilise le nombre magique 5831. Le code sous ce commentaire à la cible de lien a été déroulé.
puis j'ai trouvé ce :
Magic Constant 5381: 1. odd number 2. prime number 3. deficient number 4. 001/010/100/000/101 b
il y a aussi ce réponse à quelqu'un Peut-il expliquer la logique derrière djb2 fonction de hachage? il fait référence à un post de DJB lui-même à une liste de diffusion qui mentionne 5381 (extrait de cette réponse extrait ici):
[...] 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.
j'ai trouvé une propriété très intéressante de ce nombre peut être que peut être une raison à cela.
5381 est le 709ème prime.
709, c'est la 127e place.
127 31 premier.
31 c'est la 11ème prime.
11 c'est la 5ème prime.
5, c'est la 3ème prime.
3 c'est 2nd prime.
2 est le 1er premier.
5381 est le premier nombre pour lequel cela se produit pour 8 fois. 5381st premier peut dépasser la limite de signé int tellement c'est un bon point pour arrêter la chaîne.