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

58

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

H=kmod 11

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

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

H=kmod 12

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

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

CodyBugstein
источник
Соответствующий вопрос, почему мы используем xor в хэш-функции stackoverflow.com/questions/5889238/…
shuva

Ответы:

63

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

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

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

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

В общем:

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

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

Марио Сервера
источник
Я только что увидел, что мой запрос соответствует вашему ответу. Как вы думаете, хэш-функция в моем запросе работает?
обмен
@overexchange: я ответил на ваш вопрос. Этот ответ также может быть интересен для вас.
Марио Сервера
почему выбор m имеет значение только в случае перекоса K? не правда ли, что при плохом m производительность будет хуже, даже если K распределен равномерно?
vorou
Это зависит от того, что вы подразумеваете под «плохой ». Если вы имеете в виду «маленький по сравнению с количеством элементов в хэш-таблице» (т. Е. Высокий коэффициент загрузки ), то производительность будет низкой. Однако, если вы имеете в виду «не простое», то этот факт не так важен, если все ключи одинаково вероятны, потому что они будут равномерно распределены в хеш-таблице. Сам вопрос дает пример. m
Марио Сервера
16

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

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

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

frafl
источник
1
Но если мои ключи не имеют форму тогда не имеет значения? Это правильно? a+k×bm
CodyBugstein
1
@lmray, если ваши ключи распределены равномерно, не имеет значения. Если это не так, это будет зависеть от распределения точности для значения или нет. mm
AProgrammer
Просто отменил последнее редактирование, я забыл, что . 12>11
13
3
Вы имели в виду, что "перейти к небольшому подмножеству сегментов, если делит "? bm
Михаил Дубов
8

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

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

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

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

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

Рафаэль
источник
2

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

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

saadtaame
источник