Вопрос по java, algorithm, hashmap – Эффективная реализация hashCode ()

12

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

result = 31 * result + ...

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

Ваш Ответ

1   ответ
20

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

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

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

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

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

Похожие вопросы