algorithm - ¿Motivo del número 5381 en la función hash de DJB?

primes

Question

¿Alguien puede decirme por qué se usa el número 5381 en la función de hash DJB?

La función DJB Hash es

h (0) = 5381

h (i) = 33 * h (i-1) ^ str [i]

Un programa 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;
}

Answer 1

5381 es solo un número que, en las pruebas, provocó menos colisiones y mejor avalancha . Encontrarás "constantes mágicas" en casi todos los algoritmos hash.

Answer 2

Encontré una propiedad muy interesante de este número que puede ser una razón para eso.

5381 es el 709o primer.
709 es el 127 ° primo.
127 es el 31 ° primo.
31 es el 11 ° primo.
11 es el quinto primo.
5 es el 3er primo.
3 es el segundo primo.
2 es el primer primo.

5381 es el primer número para el que esto sucede por 8 veces. 5381 prime puede exceder el límite de int firmado, por lo que es un buen punto detener la cadena.

Answer 3

Me encontré con un comment que arroja algo de luz sobre lo que DJB está haciendo:

/*
* 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]>
*/

Esa es una función hash ligeramente diferente a la que estás viendo, aunque usa el número mágico 5831. El código debajo de ese comentario en el enlace objetivo ha sido desenrollado.

Entonces encontré this :

Magic Constant 5381:

  1. odd number

  2. prime number

  3. deficient number

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

También existe this respuesta a ¿Alguien puede explicar la lógica detrás de la función de hash djb2? Hace referencia a una post de DJB a una lista de correo que menciona 5381 (extracto de esa respuesta extractada aquí):

[...] prácticamente cualquier buen multiplicador funciona. Creo que te preocupa el hecho de que 31c + d no cubre ningún rango razonable de valores hash si cyd están entre 0 y 255. Por eso, cuando descubrí la función 33 hash y comencé a usarla en mis compresores , Comencé con un valor hash de 5381. Creo que encontrará que esto funciona tan bien como un multiplicador 261.