Причина номера 5381 в хэш-функции DJB?

Может кто-нибудь сказать мне, почему номер 5381 используется в хэш-функции DJB?

Функция DJB Hash

h (0) = 5381

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

Программа 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 ответа

Решение

5381 - это просто число, которое при тестировании привело к меньшему количеству столкновений и лучшему сходу лавин. Вы найдете "магические константы" практически в каждом хэш-алгоритме.

Источник

Я наткнулся на комментарий, который проливает свет на то, чем занимается DJB:

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

Это немного другая хеш-функция, чем та, на которую вы смотрите, хотя она использует магическое число 5831. Код ниже этого комментария на цели ссылки был развернут.

Тогда я нашел это:

Magic Constant 5381:

  1. odd number

  2. prime number

  3. deficient number

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

Есть также ответ на вопрос Кто-нибудь может объяснить логику хеш-функции djb2? Он ссылается на пост самого DJB на список рассылки, в котором упоминается 5381 (отрывок из этого ответа приведен здесь):

[...] практически любой хороший множитель работает. Я думаю, что вас беспокоит тот факт, что 31c + d не покрывает какой-либо разумный диапазон значений хеш-функции, если c и d находятся между 0 и 255. Вот почему, когда я обнаружил 33-хеш-функцию и начал использовать ее в своих компрессорах Я начал со значения хеш-функции 5381. Я думаю, вы обнаружите, что это так же хорошо, как множитель 261.

Источник

Я обнаружил, что очень интересное свойство этого числа может быть причиной этого.

5381 - это 709-е простое число.
709 это 127-е простое число.
127 - 31-е простое число.
31-е простое число.
11 пятый премьер.
5 - это третье простое число.
3 является вторым простым.
2 1-е простое число.

5381 - это первое число, для которого это происходит 8 раз. 5381-е простое число может превысить предел подписанного int, так что это хороший момент, чтобы остановить цепочку.

Источник
Другие вопросы по тегам