Мне просто интересно, почему эти простые числа используются в методе класса hashCode()? Например, при использовании Eclipse для генерации моего метода hashCode() всегда используется простое число 31:
public int hashCode() {
final int prime = 31;
//...
}
Литература:
Вот хороший пример на Hashcode и статья о том, как я нашел хэширующие работы (С#, но концепции передаются): Эрик Липперт Руководство и правила для GetHashCode()
Потому что вы хотите, чтобы число, которое вы умножаете, и количество ведер, которые вы вставляете, имеют ортогональные простые факторизации.
Предположим, что вставляются 8 ведер. Если число, которое вы используете для умножения, несколько кратно 8, тогда вставляемое в него ведро будет определяться только наименее значимой записью (она не умножается вообще). Аналогичные записи будут сталкиваться. Не подходит для хэш-функции.
31 - достаточно большое число, что количество ведер вряд ли будет делиться им (и на самом деле, современные java-реализации HashMap сохраняют количество ведер до степени 2).
Для наилучшего распределения данных между хэш-ведрами выбираются простые числа. Если распределение входов является случайным и равномерно распределенным, то выбор хэш-кода/модуля не имеет значения. Это влияет только на то, что на входе есть определенная структура.
Это часто бывает при работе с ячейками памяти. Например, все 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
Обратите внимание на почти идеальное распределение при использовании простого модуля по сравнению с несмещенным модулем.
Однако, хотя приведенный выше пример в значительной степени надуман, общий принцип заключается в том, что при работе с шаблоном входных данных с использованием модуля с простым числом даст наилучшее распределение.
Для чего это стоит, Effective Java 2nd Edition отказывается от математики и просто говорит, что причина выбора 31:
Здесь полная цитата из пункта 9: Всегда переопределяйте hashCode, когда вы переопределяете equals:
Значение 31 выбрано потому, что оно нечетное простое. Если бы он был четным и переполнение переполнено, информация была бы потеряна, поскольку умножение на 2 эквивалентно сдвигу. Преимущество использования штриха менее понятно, но оно традиционно.
Хорошим свойством 31 является то, что умножение может быть заменено сдвигом (§15.19) и вычитанием для лучшей производительности:
31 * i == (i << 5) - iСовременные виртуальные машины делают эту оптимизацию автоматически.
В то время как рецепт в этом элементе дает достаточно хорошие хеш-функции, он не дает современных хеш-функций, а библиотеки Java-платформ не предоставляют такие хэш-функции, как в версии 1.6. Написание таких хеш-функций является темой исследования, лучше всего оставляемой математикам и теоретическим компьютерным ученым.
Возможно, более поздняя версия платформы предоставит современные хеш-функции для своих классов и служебных методов, чтобы позволить средним программистам создавать такие хэш-функции. Тем временем, методы, описанные в этом пункте, должны быть адекватными для большинства приложений.
Скорее упрощенно, можно сказать, что использование множителя с множеством делителей приведет к более хеш-коллизациям. Поскольку для эффективного хэширования мы хотим минимизировать количество столкновений, мы пытаемся использовать множитель с меньшим числом делителей. Простое число по определению имеет ровно два различных положительных делителя.
Я слышал, что 31 был выбран так, чтобы компилятор мог оптимизировать умножение на сдвиг влево на 5 бит, а затем вычесть значение.
Здесь цитата немного ближе к источнику.
Это сводится к:
Сначала вы вычисляете значение хеша по модулю 2 ^ 32 (размер int), поэтому вам нужно что-то относительно простое 2 ^ 32 (относительно простое означает, что нет общих делителей). Для этого сделало бы нечетное число.
Затем для данной хэш-таблицы индекс обычно вычисляется из значения хэша по модулю размера хеш-таблицы, поэтому вы хотите, чтобы что-то было относительно простым размером хэш-таблицы. Часто размеры хэш-таблиц по этой причине выбираются как простые числа. В случае Java реализация Sun гарантирует, что размер всегда равен двум, поэтому здесь также будет нечетное число. Существует также несколько дополнительных массивов хеш-ключей для дальнейшего ограничения конфликтов.
Плохой эффект, если хэш-таблица и множитель имели общий коэффициент n, могут заключаться в том, что при определенных обстоятельствах будет использоваться только 1/n записей в хеш-таблице.
Обычно это помогает добиться более равномерного распространения ваших данных среди хэш-кодов, особенно для клавиш с низкой энтропией.
31 также специфичен для Java HashMap, который использует int как хэш-тип данных. Таким образом, максимальная емкость 2 ^ 32. Нет смысла использовать более крупные пробы Ферма или Мерсенна.
Причина, по которой используются простые числа, состоит в том, чтобы минимизировать коллизии, когда данные демонстрируют некоторые конкретные закономерности.
Перво-наперво: если данные случайные, то нет необходимости в простом числе, вы можете выполнить операцию мода для любого числа, и у вас будет одинаковое количество столкновений для каждого возможного значения модуля.
Но когда данные не случайны, происходят странные вещи. Например, рассмотрим числовые данные, которые всегда кратны 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. Это означает, что мы должны выбрать простое число, которое не делит наши ключи, обычно достаточно выбрать большое простое число,
Поэтому ошибочная сторона повторения приводит к тому, что простые числа используются для нейтрализации влияния шаблонов в ключах при распределении коллизий хэш-функции.