Raison pour 5381 nombre de DJB fonction de hachage?

Quelqu'un peut me dire pourquoi le nombre 5381 est utilisé dans DJB fonction de hachage ?

DJB fonction de Hachage 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;
}
InformationsquelleAutor viji | 2012-05-22
  1. 28

    5381 est juste un nombre qui, dans les essais, entraîné dans moins de collisions et mieux shoda des avalanches. Vous trouverez "les constantes magiques" dans à peu près tous les algo de hachage.

    • Ceux échangé Url me faisait rire.
    • Je suis heureux que vous soyez dans la bonne humeur 🙂 Heureusement, la permutation des Url est super-facile, parce que j'ai eu à passer le nombre autour de.
    • Je ne pouvais pas comprendre la au-dessus de l'humour.
    • La question était de savoir comment il faisait moins de collisions? J'ai été aussi à rire à haute voix. En outre, la personne qui pose la question accepté de répondre sans aucune preuve!!!!
    • djb2 (comme fnv1a) a en fait mauvais avalanche/distribution. Ils ne parviennent pas même les non-stricte avalanche critère, ce qui prend moins de puissance de calcul pour calculer. Mais ils ne ont décent taux de collisions. 🙂 Souvent, les taux de collision est liée à son shoda des avalanches de comportement, ce qui signifierait djb2 n'est pas aussi bon que les autres choix. Le plus proche de tous les bits pesuedo aléatoire, moins il est probable que deux valeurs correspondent.
    InformationsquelleAutor Mahmoud Al-Qudsi
  2. 56

    Je suis tombé sur une commentaire qui jette une certaine lumière sur ce qui 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 <[email protected]>
*/

    C'est un peu différent en fonction de hachage que celui que vous êtes en train de regarder, si elle n'utiliser le 5831 nombre magique. Le code ci-dessous que ce commentaire sur le lien de la cible a été déroulé.

    Puis j'ai trouvé cette:

    Magic Constant 5381:

  1. odd number

  2. prime number

  3. deficient number

  4. 001/010/100/000/101 b

    Il est également cette réponse à Quelqu'un peut-il expliquer la logique derrière djb2 fonction de hachage? Il fait référence à un post par DJB lui-même à une liste de diffusion qui mentionne 5381 (extrait de la réponse extrait ici):

    [...] pratiquement n'importe quel bon multiplicateur fonctionne. Je pense que vous vous souciez
    sur le fait que 31 c + d ne permet pas de couvrir toute gamme raisonnable de hachage
    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 ne fonctionne tout simplement comme
    bien qu'un 261 multiplicateur.

    • Merci - Le dernier commentaire est ce qui a frappé le clou sur la tête pour 5381.
    • Ils ne sont pas "légèrement différent". (x << 5) + x est au niveau du bit de multiplication. C'est l'équivalent de x * 33! Sur certains systèmes à l'aide de la bit-à-bit méthode est plus rapide, ou le seul moyen de faire la multiplication.
    InformationsquelleAutor Mark Johnson
  3. 20

    J'ai trouvé une propriété très intéressante de ce nombre peut être que peut être une raison à cela.

    5381 est 709th premier.

    709 est 127e premier.

    127 31 premier.

    31 est la 11e le premier.

    11 est 5ème prime.

    5 est la 3e premier.

    3 est la 2e premier.

    2 est le 1er premier.

    5381 est le premier numéro de ce qui se passe 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.

    • Comment avez-vous trouvé cela?
    • oeis.org/search?q=5381 La 5381st premier n'est pas n'importe où près de la limite signée d'un int.
    • Dans ce code, il a pris unsigned int et qui permet de stocker la valeur 52711.
    • Je l'ai trouvé dans la zone de loisirs de Mathématiques
    InformationsquelleAutor Deep Joshi