Зачем использовать простое число в hashCode?
Мне просто интересно, почему эти простые числа используются в методе класса hashCode () ? Например, при использовании Eclipse для генерации моего метода hashCode () всегда используется простое число 31 :
public int hashCode() {
final int prime = 31;
//...
}
Ссылки:
Вот хороший учебник по Hashcode и статья о том, как работает хеширование, которое я нашел (C #, но концепции можно передавать): Рекомендации и правила Эрика Липперта для GetHashCode ()
4 ответа
Я слышал, что 31 было выбрано, чтобы компилятор мог оптимизировать умножение для сдвига влево на 5 бит, а затем вычесть значение.
Сначала вы вычисляете хеш-значение по модулю 2^32 (размер int), поэтому вам нужно что-то относительно простое относительно 2^32 (относительно простое означает, что есть не имеют общих делителей). Для этого подойдет любое нечетное число.
Затем для данной хэш-таблицы индекс обычно вычисляется из значения хеш-функции по модулю размера хеш-таблицы, поэтому вам нужно что-то, что является относительно простым по отношению к размеру хэш-таблицы. Часто по этой причине размеры хеш-таблиц выбираются как простые числа.В случае с Java реализация Sun гарантирует, что размер всегда равен степени двойки, поэтому здесь также будет достаточно нечетного числа. Существует также некоторый дополнительный массаж хэш-ключей для дальнейшего ограничения коллизий.
Плохой эффект, если хеш-таблица и множитель имеют общий коэффициент n, может заключаться в том, что при определенных обстоятельствах будет использоваться только 1/n записей в хеш-таблице.
Вот цитата немного ближе к источнику.
Это сводится к следующему:
- 31 — простое число, что уменьшает коллизии
- 31 дает хорошее распределение с
- разумным компромиссом в скорости
Обычно это помогает добиться более равномерного распределения ваших данных по сегментам хеширования, особенно для ключей с низкой энтропией.