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

Если у меня есть список значений ключей от 1 до 100, и я хочу организовать их в массив из 11 блоков, меня научили формировать функцию мода

Теперь все значения будут размещены один за другим в 9 строк. Например, в первом сегменте будет . Во втором будет и т. Д.$0, 11, 22 \dots$$1, 12, 23 \dots$

Допустим, я решил быть плохим парнем и использовать не простое число в качестве своей функции хеширования - взять 12. Использование функции хеширования

приведет к созданию хеш-таблицы со значениями в первом сегменте, и т. д. во втором и так далее.$0, 12, 24 \dots$$1, 13, 25 \dots$

По сути, это одно и то же. Я не уменьшал коллизии, и я не распространял вещи лучше, используя хеш-код простого числа, и я не могу понять, насколько это полезно.

Рассмотрим набор ключей и хеш-таблицу, где количество сегментов равно . Поскольку коэффициент равен , ключи, кратные будут хэшироваться в сегменты, кратные :$K=\{0,1,...,100\}$$m=12$$3$$12$$3$$3$

• Ключи будут хэшированы в сегмент .$\{0,12,24,36,...\}$$0$
• Ключи будут хэшированы в сегмент .$\{3,15,27,39,...\}$$3$
• Ключи будут хэшированы в корзину .$\{6,18,30,42,...\}$$6$
• Ключи будут хэшированы в корзину .$\{9,21,33,45,...\}$$9$

Если распределен равномерно (т. Е. Каждый ключ в одинаково вероятен), то выбор не так критичен. Но что произойдет, если распределено неравномерно? Представьте, что ключи, которые чаще всего встречаются, кратны . В этом случае все сегменты, которые не кратны будут пустыми с высокой вероятностью (что действительно плохо с точки зрения производительности хеш-таблицы).$K$$K$$m$$K$$3$$3$

Такая ситуация встречается чаще, чем может показаться. Представьте, например, что вы отслеживаете объекты в зависимости от того, где они хранятся в памяти. Если размер слова вашего компьютера составляет четыре байта, то вы будете хэшировать ключи, кратные . Само собой разумеется, что выбор как кратного был бы ужасным выбором: у вас было бы ведра полностью пустыми, и все ваши ключи сталкивались в оставшихся ведрах.$4$$m$$4$$3m/4$$m/4$

В общем:

Каждый ключ в который имеет общий множитель с числом сегментов будет хэширован в сегмент, кратный этому коэффициенту.$K$$m$

Поэтому, чтобы свести к минимуму столкновений, важно , чтобы уменьшить количество общих факторов между и элементами . Как этого достичь? Выбирая для числа, у которого очень мало факторов: простое число .$m$$K$$m$

Вероятность столкновения с использованием простых чисел зависит от распределения ваших ключей.

Если многие из ваших ключей имеют форму и ваша хеш-функция , то эти ключи переходят в небольшое подмножество сегментов, если делит . Поэтому вам следует минимизировать количество таких , чего можно добиться, выбрав простое число.$a+k\cdot b$$H(n)=n \bmod m$$b$$n$$b$

С другой стороны, если вам нравится иметь от до сегментов и вы знаете, что различия, кратные , более вероятны, чем различия, кратные и , вы можете выбрать для своего особого применения.$11$$12$$11$$2$$3$$12$

Будет ли это иметь влияние (также) зависит от того, как вы относитесь к столкновениям. При использовании некоторых вариантов открытого хеширования использование простых чисел гарантирует, что будут найдены пустые слоты, если таблица достаточно пуста.

Попробуйте показать следующее, например:

Предположим , мы хотим , чтобы вставить элемент , который хэши для решения и коллизий разрешать пробуя позиции в дальнейшем для .$a$$a + i^2$$i=1,2,\dots$

Покажите, что эта процедура всегда дает пустую позицию, если хеш-таблица имеет размер , простое число больше , и по крайней мере половина всех позиций свободна.$p$$p$$3$

Подсказка: Используйте тот факт , что кольцо классов вычетов по модулю является полем , если является простым и , следовательно имеет не более решения.$p$$p$$i^2=c$$2$

Если ваша хеш-функция имеет вид где простое число и случайное выбрано , то вероятность того, что 2 разных ключа хешируют в один и тот же сегмент, равна . Таким образом, для , что очень мало.$h(k)=a\times k \mod m$$m$$a$$1\over m$$m=1009$$Pr\{h(x)=h(y), x\neq y\}=0.00099108027$

Эта схема известна как: Универсальное хеширование.