Почему 5381 и 33 так важны в алгоритме djb2?

Question

Алгоритм djb2 имеет хеш-функцию для строк.

unsigned long hash = 5381;
int c;

while (c = *str++)
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

Почему 5381 и 33 так важны?

Answer 1

Эта хеш-функция похожа на линейный конгруэнтный генератор (LCG - простой класс функций, генерирующих серию псевдослучайных чисел), который обычно имеет вид:

X = (a * X) + c;  // "mod M", where M = 2^32 or 2^64 typically

Обратите внимание на сходство с хеш-функцией djb2... a=33, M=2^32. Чтобы у LCG был "полный период" (т. Е. Настолько случайный, насколько это возможно), a должен иметь определенные свойства:

• a-1 делится на все простые множители M (a-1 равно 32, что делится на 2, единственный простой фактор 2 ^ 32)
• a-1 кратно 4, если M кратно 4 (да и да)

Кроме того, c и M должны быть относительно простыми (что будет верно для нечетных значений c).

Итак, как вы можете видеть, эта хеш-функция чем-то напоминает хороший LCG. А когда дело доходит до хеш-функций, вам нужна такая, которая производит "случайное" распределение хеш-значений при реалистичном наборе входных строк.

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

РЕДАКТИРОВАТЬ: Этот хороший ответ объясняет, почему 33 и 5381 были выбраны по практическим соображениям.

Answer 2

33 был выбран потому что:

1) Как указывалось ранее, умножение легко вычислить, используя shift и add.

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

3) Сдвиг 5 относительно простого к 32 (число битов в регистре), что помогает с лавиной. Хотя в строке осталось достаточно символов, каждый бит входного байта будет в конечном итоге взаимодействовать с каждым предшествующим битом ввода.

4) Сдвиг 5- хорошая величина сдвига при рассмотрении символьных данных ASCII. Символ ASCII можно рассматривать как 4-битный селектор типа символа и 4-битный селектор типа символа. Например, все цифры имеют 0x3 в первых 4 битах. Таким образом, 8-битный сдвиг приведет к тому, что биты с определенным значением будут в основном взаимодействовать с другими битами, имеющими такое же значение. 4-битный или 2-битный сдвиг аналогично приведет к сильному взаимодействию между битами единомышленников. 5-битный сдвиг заставляет многие из четырех младших битов символа сильно взаимодействовать со многими из 4-х старших битов в одном и том же символе.

Как указано в другом месте, выбор 5381 не слишком важен, и многие другие варианты должны работать здесь.

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

На современных процессорах умножение выполняется намного быстрее, чем это было при разработке этого алгоритма, и другие коэффициенты умножения (например, 2^13 + 2^5 + 1) могут иметь аналогичную производительность, немного лучшую производительность и быть немного проще для записи.

Вопреки ответу выше, хорошая некриптографическая хеш-функция не хочет производить случайный вывод. Вместо этого, учитывая два входа, которые почти идентичны, он хочет производить очень разные результаты. Если ваши входные значения распределены случайным образом, вам не нужна хорошая хеш-функция, вы можете просто использовать произвольный набор битов из вашего ввода. Некоторые из современных хеш-функций (Jenkins 3, Murmur, вероятно, CityHash) производят лучшее распределение выходных данных, чем случайные данные, которые очень похожи.

Answer 3

На 5381 Дэн Бернштейн (djb2) говорит в этой статье:

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

Вся тема здесь, если вам интересно.

У Озана Йигита есть страница с хэш-функциями, которая гласит:

[...] магия числа 33 (почему она работает лучше, чем многие другие константы, простые или нет) никогда не была адекватно объяснена.

Answer 4

Может быть, потому, что 33 == 2^5 + 1 и многие алгоритмы хеширования используют 2^n + 1 как их множитель?

Кредит Джерому Берже

Обновить:

Похоже, это подтверждается текущей версией программного пакета djb2, изначально взятого из: cdb

Заметки, которые я связал, чтобы описать суть алгоритма хеширования как h = ((h << 5) + h) ^ c делать хеширование... x << 5 быстрый аппаратный способ использовать 2^5 в качестве множителя.