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

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

result = 31 * result + ...

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

Ответы на вопрос(1)

Решение Вопроса

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

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

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

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

 05 окт. 2010 г., 11:53
@ dma_k: боюсь, я не знаю подробностей этого ... только то, что он предназначен для хорошей работы. (Я думал, что Effective Java предлагает 31 на самом деле ... может, это второе издание, которое делает это?)
 Adamski02 июл. 2009 г., 16:08
Спасибо Джон. Если это причина, то странно, что IDEA просто не помещает (x & lt; 5) - x в сгенерированный код. Может ли JIT обнаружить эту оптимизацию?
 02 июл. 2009 г., 16:07
Тогда почему не 7? Это сдвиг на 3 и вычитание. И это простое
 02 июл. 2009 г., 17:19
В прошлый раз, когда я проверял 31, тоже был премьер.
 02 июл. 2009 г., 16:16
7 позволяет строкам, которые отличаются только двумя соседними символами, часто заканчиваться одним и тем же хеш-кодом. Фактически, практически любой процессор за последние десять или два десятилетия должен иметь возможность управлять умножением на восьмибитное число (если оно в регистре) в цикле.

Ваш ответ на вопрос