Вопрос по algorithm, hash, primes – Причина номера 5381 в хэш-функции DJB?

37

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

Функция хеша DJB

h (0) = 5381

h (i) = 33 * h (i-1) ^ стр [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   ответа
18

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

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

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

@JakubKaszycki Я нашел это в развлекательной математике
oeis.org/search?q=5381   5381-е простое число не близко к пределу со знаком int.
@evilotto В этом коде он взял unsigned int, и он может хранить значение 52711.
Как ты это нашел?
50

Я наткнулся накомментарий это проливает некоторый свет на то, чем занимается 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 <[email protected]>
*/

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

Потом я нашелэтот:

Magic Constant 5381:

  1. odd number

  2. prime number

  3. deficient number

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

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

[...] practically any good multiplier works. I think you're worrying about the fact that 31c + d doesn't cover any reasonable range of hash values if c and d are between 0 and 255. That's why, when I discovered the 33 hash function and started using it in my compressors, I started with a hash value of 5381. I think you'll find that this does just as well as a 261 multiplier.

Они "не" немного отличаются ".(x << 5) + x является побитовым умножением. Это эквивалентноx * 33! В некоторых системах использование побитового метода выполняется быстрее или является единственным способом умножения.
Спасибо - Последний комментарий - это то, что ударило по голове 5381.
26

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

Вопрос был в том, как он делал меньше столкновений? Я тоже смеялся вслух. Более того, человек, задававший вопрос, принял ответ без каких-либо доказательств !!!!
Я не мог понять вышеупомянутый юмор.
Эти поменявшиеся URL заставили меня смеяться.
@Хорошо, я рад, что вы в хорошем настроении :) К счастью, поменять URL-адреса очень просто, так как мне просто нужно было переключать номера.
djb2 (как и fnv1a) на самом деле имеетbad avalanche/distribution, Они не справляются даже с нестрогим лавинным критерием, который требует меньше вычислительной мощности для расчета. Но ониdo иметь приличный уровень столкновений. :) Часто частота столкновений связана с ее лавинным поведением, что означает, что djb2 не так хорош, как другие варианты. Чем ближе все биты являются случайными, тем меньше вероятность совпадения любых двух значений.

Похожие вопросы