почему составные числа плохо для хеширования по делению?

Question

Это мой первый вопрос по стеку.Как вы можете сказать, я новичок в изучении алгоритмов и структуры данных.

При использовании метода деления для создания хеш-функции (т. Е. H (k) = k mod m) рекомендуется (например, CLRS) использовать простое число, не слишком близкое к степени 2 дляделитель м.Может ли кто-нибудь любезно объяснить мне, почему выбор m в качестве составного числа плох?

Answer 1

Рассмотрим случай, если m четно, а все значения k четны. Тогда все значения хеш-функции также будут четными.

Например, рассмотрим случай m = 6 значений хэширования:

Input values:  0, 2, 4, 6, 8, 10, 12, 14, 16, ...
Hash values:   0, 2, 4, 0, 2,  4,  0,  2,  4, ...

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

Рассмотрим те же входные значения, но с m = 7:

Input values:  0, 2, 4, 6, 8, 10, 12, 14, 16, ...
Hash values:   0, 2, 4, 6, 1,  3,  5,  0,  2, ...

Несмотря на то, что все входные значения являются четными, значения хеш-функции по-прежнему равномерно распределены по [0..6].

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

Answer 2

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

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

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

Совет об использовании простого числа, а не составного числа, без знания значений для хеширования, не лучше, чем утверждение, что 87654321 - лучший модуль для хеширования.

Если вы хотитедля хеширования простых чисел, или чисел Фибоначчи, тогда советы по использованию простого модуля, или составного модуля, или степени 2 не имеют значения.

Если вы хотите хешировать составные числа попарно взаимно простыми, тосоставной модуль, взаимно простой для каждого элемента входного набора, является кандидатом на «хороший» выбор.Простой модуль, больший, чем наибольший фактор из всех элементов входного набора, является еще одним «хорошим» выбором.

Если ваш входной набор представляет собой разреженный набор целых чисел в пределах интервала с гауссовым распределением интервалов между числами, то «лучшим» выбором модуля является число, которое минимизирует вхождения gcd (модуль, входные данные)! = 1. Это более вероятно при выборе простого числа в качестве модуля.

По этой причине рекомендуется использовать простые числа.