Когда уместно использовать простой модуль в качестве функции хеширования?

Question

Мне нужно создать 16-битный хэш из 32-битного числа, и я пытаюсь определить, подходит ли простой модуль 2^16.

Хеш будет использоваться в хэш-таблице с 2^16 записями для быстрого поиска 32-битного числа.

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

В этом случае мое 32-битное число является результатом измененной контрольной суммы adler32, используя 2^16 в качестве M.

Итак, в общем смысле, правильно ли я понимаю, что в качестве функции хеширования нормально использовать простой мод n (где n - размер хеш-таблицы), если у меня равномерное распределение данных?

И, в частности, даст ли adler32 достаточно случайное распределение для этого?

Answer 1

Да, если ваши 32-битные числа равномерно распределены по всем возможным значениям, то их модуль также будет равномерно распределен по n возможным значениям.

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

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