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

49

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

unsigned long hash = 5381;
int c;

while (c = *str++)
    hash = ((hash < 5) + hash) + c; /* hash * 33 + c */
Возможный дубликатПричина номера 5381 в хэш-функции DJB? rob mayoff

Ваш Ответ

4   ответа
37

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

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

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

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

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

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

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

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

8

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

Кредит дляДжером Бергер

Обновить:

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

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

21

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) обеспечивают лучшее распределение выходных данных, чем случайные данные, которые очень похожи.

Этот ответ фактически отвечает на вопрос. Спасибо! Erik Aronesty
20

Эта статья:

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

Вся нитьВот если ты'заинтересован.

Озан Йигит имеетстраница о хэш-функциях который говорит:

[...] магия числа 33 (почему она работает лучше, чем многие другие константы, простые или нет) никогда не была адекватно объяснена.
Обратите внимание, что начальное значение хэша (5381) не имеет значения для строк одинаковой длины, но будет играть роль в генерации различных значений хеш-функции для строк различной длины. yoyo

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