Зачем использовать простое число в хэш-коде?

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

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

ссылки:

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

8 146
javascript gethashcode primes

8 ответов:

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

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

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

86

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

это часто бывает при работе с ячейками памяти. Например, все 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

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

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

116

чего бы это ни стоило,эффективная Java 2-е издание рука отказывается от математической проблемы и просто говорит, что причина выбора 31:

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

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

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

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

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

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

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

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

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

вопросы

22

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

4

здесь цитата чуть ближе к источнику.

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

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

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

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

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

2

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

0

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

0