- PVSM.RU - https://www.pvsm.ru -
Опять на собеседованиях по Java спрашивают про hashCode
и equals
? А кто из собеседующих сам ответит на вопрос, как вычисляется Object.hashCode()
и System.identityHashCode()
? Насколько дорог вызов этих методов? Как их можно ускорить в HotSpot JVM? Держу пари, едва ли кто даст правильный ответ. Разве что, кто прочитает эту статью.
Существует распространенное заблуждение, что Object.hashCode
возвращает адрес объекта в памяти. Когда-то давно, наверное, так оно и было. Например, Dalvik VM до сих пор использует адрес объекта, сдвинутый на 3 бита вправо. Однако такая реализация неудачна: во-первых, последовательно выделяемые объекты будут иметь последовательные хеш-коды; во-вторых, сборщик мусора может передвигать объекты в памяти, меняя их адреса.
Так получилось, что на прошлой неделе я дважды столкнулся с темой вычисления хеш-кода, что и побудило меня написать заметку. Сначала попался на глаза крайне несправедливо заминусованный комментарий [1]. Именно SSSurkv [2] совершенно верно предположил, что для вычисления Object.hashCode
используется генератор случайных чисел.
– Как так? – спросите вы. – Ведь хеш-код объекта должен оставаться постоянным в течение жизни приложения.
Все верно. Встроенный хеш-код генерируется лишь один раз для каждого объекта при первом вызове метода hashCode()
, после чего сохраняется в заголовке объекта для последующих вызовов. Но для первого раза используется именно random! Убедитесь сами, заглянув в исходники OpenJDK [3] (функция get_next_hash
).
Вероятно, я бы забыл про этот случай, если бы на днях не столкнулся с реальной проблемой в реальном проекте. Профилируя приложение, среди горячих методов я неожиданно увидел IdentityHashMap.put()
, который, на мой взгляд, реализован довольно эффективно. Узким местом оказался System.identityHashCode()
, на который IdentityHashMap полагается. Причем медленным был только первый вызов identityHashCode на объекте. Второй и последующие вызовы, как мы теперь знаем, берут сохраненное значение из заголовка.
Но нет худа без добра. Дело в том, что в HotSpot можно выбирать реализацию Object.hashCode
с помощью ключа командной строки -XX:hashCode=n
(где n от 0 до 5).
0 – Park-Miller RNG [4] (по умолчанию)
1 – f(адрес, глобальное_состояние)
2 – константа 1
3 – последовательный счетчик
4 – адрес объекта
5 – Thread-local Xorshift [5]
Наиболее адекватным, на мой взгляд, является последний – он дает неплохое равномерное распределение, используя только битовые операции, и, что важно для конкурентных алгоритмов, не трогает глобальные переменные.
Так, всего лишь добавив ключ JVM -XX:hashCode=5
, я магическим образом ускорил свой алгоритм на 30%! Почему этот вариант до сих пор не сделали дефолтным, остается загадкой…
Напоследок забавный факт: хотспотовский hashCode
никогда не вернет 0, так как 0 считается признаком того, что хеш-код для данного объекта еще не генерировался:
if (value == 0) value = 0xBAD ;
Надеюсь, теперь, когда вы узнали всю правду о hashCode
, вы сможете не только удивить коллег на собеседовании, но и сделать свои алгоритмы еще эффективнее.
Автор: apangin
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/java/24736
Ссылки в тексте:
[1] комментарий: http://habrahabr.ru/post/164881/#comment_5678769
[2] SSSurkv: http://habrahabr.ru/users/sssurkv/
[3] исходники OpenJDK: http://hg.openjdk.java.net/jdk7/jdk7/hotspot/file/tip/src/share/vm/runtime/synchronizer.cpp
[4] Park-Miller RNG: http://en.wikipedia.org/wiki/Park-Miller_random_number_generator
[5] Xorshift: http://en.wikipedia.org/wiki/Xorshift
[6] Источник: http://habrahabr.ru/post/165683/
Нажмите здесь для печати.