Опять на собеседованиях по Java спрашивают про hashCode и equals? А кто из собеседующих сам ответит на вопрос, как вычисляется Object.hashCode() и System.identityHashCode()? Насколько дорог вызов этих методов? Как их можно ускорить в HotSpot JVM? Держу пари, едва ли кто даст правильный ответ. Разве что, кто прочитает эту статью.Существует распространенное заблуждение, что
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 никогда не вернет 0, так как 0 считается признаком того, что хеш-код для данного объекта еще не генерировался:if (value == 0) value = 0xBAD ;
Надеюсь, теперь, когда вы узнали всю правду о
hashCode, вы сможете не только удивить коллег на собеседовании, но и сделать свои алгоритмы еще эффективнее.
