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

Question

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

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

Ссылка:

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

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

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

---

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

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

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

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

• Java hashCode из одного поля - рецепт плюс пример использования ApacheСтроители Ланга
• Неправильно ли определять хеш-код объекта как сумму, умножение и т. Д. Хеш-кодов всех переменных класса?
• Absolute Beginner'sРуководство по сдвигу битов?

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

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

Answer 7

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

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

Но когда данные не случайны, происходят странные вещи.Например, рассмотрим числовые данные, которые всегда кратны 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 mod 7 = 3

20 мод 7 = 6

30 мод 7 = 2

40 мод 7 = 4

50 мод 7 = 1

и т. Д.

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

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

Answer 8

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

Answer 9

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