Зачем использовать простое число в hashCode?

174

Мне просто интересно, почему эти простые числа используются в hashCode()методе класса ? Например, при использовании Eclipse для генерации моего hashCode()метода всегда используется простое число 31:

public int hashCode() {
     final int prime = 31;
     //...
}

Ссылки:

Вот хороший учебник по Hashcode и статья о том, как работает хеширование, которую я нашел (C #, но концепции переносимы): Руководство и правила Эрика Липперта для GetHashCode ()

Ян Даллас
источник
Это более или менее дубликат вопроса stackoverflow.com/questions/1145217/… .
Ханс-Петер Стёрр
1
Пожалуйста, проверьте мой ответ на stackoverflow.com/questions/1145217/… Это связано со свойствами многочленов над полем (не кольцо!), Следовательно, простые числа.
TT_

Ответы:

104

Потому что вы хотите, чтобы число, на которое вы умножали, и количество блоков, в которые вы вставляете, имели ортогональные простые факторизации.

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

31 - достаточно большое простое число, которое вряд ли будет делиться им на количество сегментов (и на самом деле современные реализации Java HashMap поддерживают количество сегментов в степени 2).

ILMTitan
источник
9
Тогда хеш-функция, умноженная на 31, будет работать неоптимально. Однако я бы посчитал, что такая реализация хеш-таблицы плохо спроектирована, учитывая, насколько распространенным является 31 как множитель.
ILMTitan
11
Таким образом, 31 выбирается исходя из предположения, что разработчики хеш-таблиц знают, что 31 обычно используется в хеш-кодах?
Стив Куо
3
31 выбирается исходя из идеи, что большинство реализаций имеют факторизации относительно небольших простых чисел. 2 с, 3 с и 5 с обычно. Он может начинаться в 10 и расти в 3 раза, когда он становится слишком полным. Размер редко бывает полностью случайным. И даже если бы это было так, 30/31 не являются плохими шансами для хорошо синхронизированных алгоритмов хеширования. Это также может быть легко рассчитать, как утверждают другие.
ILMTitan
8
Другими словами ... нам нужно что-то знать о наборе входных значений и регулярностях набора, чтобы написать функцию, предназначенную для удаления их из этих закономерностей, чтобы значения в наборе не сталкивались в одном и том же хэш ведра. Умножение / деление / модуляция на простое число позволяет добиться такого эффекта, потому что если у вас есть LOOP с элементами X и вы перепрыгиваете Y-пробелы в цикле, то вы никогда не вернетесь в то же место, пока X не станет фактором Y Поскольку X часто является четным числом или степенью 2, вам нужно, чтобы Y было простым, поэтому X + X + X ... не является фактором Y, поэтому 31 yay! : /
Трийнко
3
@FrankQ. Это природа модульной арифметики. (x*8 + y) % 8 = (x*8) % 8 + y % 8 = 0 + y % 8 = y % 8
ILMTitan
136

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

Это часто имеет место при работе с областями памяти. Например, все 32-разрядные целые числа выровнены по адресам, кратным 4. Посмотрите на таблицу ниже, чтобы визуализировать эффекты использования простого и не простого модуля:

Input       Modulo 8    Modulo 7
0           0           0
4           4           4
8           0           1
12          4           5
16          0           2
20          4           6
24          0           3
28          4           0

Обратите внимание на почти идеальное распределение при использовании простого модуля против не простого модуля.

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

advait
источник
17
Разве мы не говорим о множителе, используемом для генерации хеш-кода, а не по модулю, используемому для сортировки этих хеш-кодов в сегменты?
ILMTitan
3
Тот же принцип. С точки зрения ввода-вывода, хеш-код подается в операцию по модулю хеш-таблицы. Я думаю, что дело в том, что если вы умножите на простые числа, вы получите больше случайно распределенных входных данных до такой степени, что модуль не будет иметь значения. Так как хеш-функция помогает лучше распределить входные данные, делая их менее регулярными, они с меньшей вероятностью сталкиваются, независимо от того, по какому модулю они были помещены в корзину.
Трийнко
9
Подобный ответ очень полезен, потому что это все равно, что учить кого-то ловить рыбу, а не ловить его для них. Это помогает людям увидеть и понять основополагающий принцип использования простых чисел для хэшей ... который заключается в неравномерном распределении входных данных, чтобы они равномерно попадали в сегменты после модуляции :).
Трийнко
29

Во что бы то ни стало, Effective Java 2nd Edition отказывается от математической проблемы и просто говорит, что причина выбора 31:

  • Потому что это нечетное простое число, и это «традиционно» использовать простые числа
  • Это также на единицу меньше, чем степень два, что позволяет для побитовой оптимизации

Вот полная цитата из пункта 9: Всегда переопределять hashCodeпри переопределенииequals :

Значение 31 было выбрано, потому что это нечетное простое число. Если бы оно было четным и умножение было переполнено, информация была бы потеряна, так как умножение на 2 эквивалентно сдвигу. Преимущество использования прайма менее очевидно, но оно традиционно.

Хорошим свойством 31 является то, что умножение может быть заменено сдвигом ( §15.19 ) и вычитанием для лучшей производительности:

 31 * i == (i << 5) - i

Современные виртуальные машины выполняют такую ​​оптимизацию автоматически.


Хотя рецепт в этом пункте дает достаточно хорошие хеш-функции, он не дает современных хеш-функций, и библиотеки Java не предоставляют такие хеш-функции, как в выпуске 1.6. Написание таких хеш-функций - тема исследования, которую лучше оставить математикам и теоретикам.

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

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

Смежные вопросы

polygenelubricants
источник
4
Эх, но вы много подходящих простых чисел , которые являются либо 2 ^ п + 1 (так называемые Ферма простых чисел ), то есть 3, 5, 17, 257, 65537или 2 ^ N - 1 ( простых чисел Мерсенна ): 3, 7, 31, 127, 8191, 131071, 524287, 2147483647. Однако 31(а не, скажем, 127) выбран.
Дмитрий Быченко
4
"потому что это нечетное простое число" ... есть только одно четное простое число: P
Мартин Шнайдер
Мне не нравится формулировка «менее понятна, но она традиционна» в «Эффективной Java». Если он не хочет вдаваться в математические детали, он должен вместо этого написать что-то вроде «имеет [похожие] математические причины». То, как он пишет, звучит так, как будто оно имеет исторический фон :(
Qw3ry
5

Я слышал, что 31 был выбран так, чтобы компилятор мог оптимизировать умножение до 5 битов влево и затем вычесть значение.

Стив Куо
источник
Как может компилятор оптимизировать таким образом? х * 31 == х * 32-1 не верно для всех х в конце концов. То, что вы имели в виду, это сдвиг влево 5 (умножается на 32), а затем вычесть исходное значение (x в моем примере). Хотя это может быть быстрее, чем умножение (кстати, это не для современных процессоров ЦП), есть и более важные факторы, которые следует учитывать при выборе умножения для хэш-кода (на ум приходит равное распределение входных значений по сегментам)
Гризли
Попробуйте немного, это довольно распространенное мнение.
Стив Куо
4
Общее мнение не имеет значения.
фрактор
1
@Grizzly, то есть быстрее , чем умножение. IMul ​​имеет минимальную задержку в 3 цикла на любом современном процессоре. (см. руководства agner fog) mov reg1, reg2-shl reg1,5-sub reg1,reg2может выполняться в 2 цикла. (mov это просто переименование и занимает 0 циклов).
Йохан
3

Вот цитата немного ближе к источнику.

Это сводится к:

  • 31 простое, что уменьшает столкновения
  • 31 производит хорошее распределение, с
  • разумный компромисс в скорости
Джон
источник
3

Сначала вы вычисляете значение хеша по модулю 2 ^ 32 (размер an int), поэтому вы хотите получить что-то относительно простое до 2 ^ 32 (относительно простое означает, что общих делителей нет). Для этого подойдет любое нечетное число.

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

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

starblue
источник
2

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

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

Но когда данные не случайны, происходят странные вещи. Например, рассмотрим числовые данные, которые всегда кратны 10.

Если мы используем мод 4, мы находим:

10 мод 4 = 2

20 мод 4 = 0

30 мод 4 = 2

40 мод 4 = 0

50 мод 4 = 2

Таким образом, из 3 возможных значений модуля (0,1,2,3) только 0 и 2 будут иметь столкновения, что плохо.

Если мы используем простое число, такое как 7:

10 мод 7 = 3

20 мод 7 = 6

30 мод 7 = 2

40 мод 7 = 4

50 мод 7 = 1

и т.д

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

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

Амар Магар
источник
1

31 также специфичен для Java HashMap, который использует int как тип хеш-данных. Таким образом, максимальная емкость 2 ^ 32. Нет смысла использовать большие простые числа Ферма или Мерсенна.

DED
источник
0

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


источник