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

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

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

Ответы

Ответ 1

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

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

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

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