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

Question

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

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

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

В этом случае мой 32 разрядное число является результатом модифицированной Adler32 контрольной суммы, используя 2^16, как М.

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

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

Answer 1

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

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

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