hashCode в Java

Существует распространенное заблуждение, что Object.hashCode возвращает адрес объекта в памяти. Когда-то давно, наверное, так оно и было. Например, Dalvik VM до сих пор использует адрес объекта, сдвинутый на 3 бита вправо. Однако такая реализация неудачна: во-первых, последовательно выделяемые объекты будут иметь последовательные хеш-коды; во-вторых, сборщик мусора может передвигать объекты в памяти, меняя их адреса.

Так получилось, что на прошлой неделе я дважды столкнулся с темой вычисления хеш-кода, что и побудило меня написать заметку. Сначала попался на глаза крайне несправедливо заминусованный комментарий. Именно SSSurkv совершенно верно предположил, что для вычисления Object.hashCode используется генератор случайных чисел. – Как так? – спросите вы. – Ведь хеш-код объекта должен оставаться постоянным в течение жизни приложения.

Все верно. Встроенный хеш-код генерируется лишь один раз для каждого объекта при первом вызове метода hashCode(), после чего сохраняется в заголовке объекта для последующих вызовов. Но для первого раза используется именно random! Убедитесь сами, заглянув в исходники OpenJDK (функция get_next_hash).

Вероятно, я бы забыл про этот случай, если бы на днях не столкнулся с реальной проблемой в реальном проекте. Профилируя приложение, среди горячих методов я неожиданно увидел IdentityHashMap.put(), который, на мой взгляд, реализован довольно эффективно. Узким местом оказался System.identityHashCode(), на который IdentityHashMap полагается. Причем медленным был только первый вызов identityHashCode на объекте. Второй и последующие вызовы, как мы теперь знаем, берут сохраненное значение из заголовка.

Но нет худа без добра. Дело в том, что в HotSpot можно выбирать реализацию Object.hashCode с помощью ключа командной строки -XX:hashCode=n (где n от 0 до 5).

0 – Park-Miller RNG (по умолчанию)

1 – f(адрес, глобальное_состояние)

2 – константа 1

3 – последовательный счетчик

4 – адрес объекта

5 – Thread-local Xorshift

Наиболее адекватным, на мой взгляд, является последний – он дает неплохое равномерное распределение, используя только битовые операции, и, что важно для конкурентных алгоритмов, не трогает глобальные переменные. Так, всего лишь добавив ключ JVM -XX:hashCode=5, я магическим образом ускорил свой алгоритм на 30%! Почему этот вариант до сих пор не сделали дефолтным, остается загадкой…

Источник: Откуда растут ноги у hashCode