Эффективная реализация hashCode()

Question

Я часто автоматически генерирую класс hashCode() метод с использованием IntelliJ IDEA, и обычно метод принимает вид:

result = 31 * result + ...

Мой вопрос в том, какова цель умножения на 31?Я знаю, что это простое число, но зачем выбирать именно 31?Кроме того, если внедрять hashCode() для особенно маленького / большого набора данных люди подошли бы к этой проблеме по-другому?

Answer 1

Умножение на 31 происходит быстро, потому что JIT может преобразовать его в сдвиг влево на 5 бит и вычитание:

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

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

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