Как считается хэшкод по умолчанию? На собеседованиях часто об | Java: fill the gaps

Как считается хэшкод по умолчанию?

На собеседованиях часто обсуждают методы equals и hashcode. За что отвечают, как соотносятся между собой, когда переопределять, а когда не стоит.

В этом посте разберём, как считается хэшкод под умолчанию. Практической пользы у него, конечно, нет . Цель вопроса - проверить, понимает ли человек внутреннюю работу JVM. Бывает, что ответы на стандартные вопросы знает, а как всё связано вместе - нет. Возможен такой диалог:

- Как считается хэшкод по умолчанию?
- Это адрес объекта в памяти.
- А почему так?
- Адрес каждого объекта уникален, то что надо для хэшкода.
- Сборщик мусора перемещает объекты внутри памяти. Как это влияет на значения хэшей?
- Ээээ...

Разберём вычисление хэшкода от и до. Сигнатура метода в классе Object выглядит так:
public native int hashCode();

В разных JVM реализации могут отличаться. Рассмотрим исходный код hashcode() в OpenJDK. Там 6(!) стратегий вычисления хэшкода. Стратегия задаётся опциями VM:

-XX:+UnlockExperimentalVMOptions -XX:hashCode={число}

При первом вызове результат сохраняется внутри объекта. Хэшкод для Object считается один раз и не меняется, даже если объект перемещается в памяти. Посмотрим все возможные варианты:

Стратегия по умолчанию.
Случайное число по алгоритму Xorshift RNG. Следующее значение вычисляется на основе предыдущего. Значения равномерно распределены. У каждого потока свой генератор. Синхронизации между потоками нет, поэтому алгоритм работает быстро.

-XX:hashCode=0
Случайное число по алгоритму Lehmer RNG. Генератор один на все потоки, поэтому работает медленно.

-XX:hashCode=1
Адрес объекта в памяти и немного манипуляций с битами. Работает быстро, но не даёт равномерного распределения хэш кодов.

-XX:hashCode=2
Чемпион по скорости, возвращает 1 для всех объектов:
java.lang.Object@1

Используется как отправная точка для тестов остальных стратегий.

-XX:hashCode=3
Обычная возрастающая последовательность:
java.lang.Object@a4
java.lang.Object@a5
java.lang.Object@a6

-XX:hashCode=4
Текущий адрес в памяти. Популярный, но неправильный ответ на собеседованиях. Отчасти в этом виновата документация: там адрес приводится как пример реализации.

Рейтинг стратегий по скорости:
Вернуть единицу: 184 операций за микросекунду
Вариант по умолчанию: 176 оп/мск
Адрес в памяти-1: 175 оп/мск
Адрес в памяти-2: 160 оп/мск
Растущая последовательность: 14 оп/мск
Случайное число и глобальная переменная: 10 оп/мск

Интересно, что до java 8 самая медленная опция была вариантом по умолчанию.

Резюме:
Реализация хэшкода зависит от JVM и VM-флажков.
Расчёт на основе адреса памяти не даёт равномерного распределения.
Общие переменные в маленьких методах снижают производительность в 10 раз.
В OpenJDK 6 стратегий вычисления хэшкода. По умолчанию используется генератор случайных чисел в рамках одного потока.