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

Опять на собеседованиях по 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, вы сможете не только удивить коллег на собеседовании, но и сделать свои алгоритмы еще эффективнее.

Источник

Класс Object в Java

Класс Object, из пакета java.lang, находится на вершине дерева иерархии классов. Каждый класс является потомком, прямым или косвенным, класса Object. Любой использованный или написанный нами класс наследует методы этого класса. Благодаря этому мы можем сослаться на объект, тип которого нам не известен.

Исходный код данного класса из OpenJDK можно посмотреть тут.


Разберемся по порядку с методами этого класса.

Обычно, для того, чтобы JVM нашла нативные функции, они должны быть названы определенным образом. Например для java.lang.Object.registerNatives, соответствующая функция на С должна называться Java_java_lang_Object_registerNatives. Используя JNI функцию registerNatives можно именовать наши С функции как захочется.

Код на С :

Следует заметить, что Object.getClass нет в этом списке. Это значит что он будет вызываться со стандартным именем Java_java_lang_Object_getClass.
Регистрация нативных функций также полезна если мы встраиваем Java в программу на С и хотим ссылаться на функции своего приложения, а не на функции из общей библиотеки или хотим привязать нативные методы к другим функциям на С.

Далее идет статичный конструктор.


Этот метод нельзя переопределить.
Возвращает класс объекта, методы которого можно использовать для получения информации об этом классе, например его имя (getSimpleName()), его суперкласс (getSuperClass()), и реализуемых интерфейсах (getInterfaces()).
Например, следующий метод выведет имя класса объекта:


Возвращает хэш-код объекта. Этот метод поддерживается в интересах хэш-таблиц (таких как HashMap, например).

По умолчанию, если два объекта равны, их хэш-коды должны быть также равны. Если переопределить метод equals(), реализация метода hashCode() у Object перестает быть корректной. Поэтому, если мы переопределяем метод equals(), мы должны переопределить метод hashCode().

В доках Oracle написано: нативный метод реализован так, что возвращает адрес объекта в памяти.
В openJDK 7 для HotSpot JVM он основан на генераторе случайных чисел. Смотреть метод get_next_hash.

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

С помощью ключа командной строки -XX:hashCode=n (где n от 0 до 5).
0 – Park-Miller RNG (по умолчанию)
1 – f(адрес, глобальное_состояние)
2 – константа 1
3 – последовательный счетчик
4 – адрес объекта
5 – Thread-local Xorshift


Метод сравнивает два объекта и возвращает true, если они равны. Метод equals(), реализованный в классе Object использует тождественный оператор (==), чтобы определить, являются ли два объекта равными. Для примитивных типов данных это корректно. Для объектов метод проверяет только то, ссылки указывают на один и тот-же объект.
Всегда надо переопределять метод equals(), если сравнение тождественным оператором не подходит для объекта.
Переопределив метод equals() обязывает разработчика переопределить метод hashCode().


Если класс или один из его суперклассов реализуют интерфейс Cloneable, то можно использовать метод clone() для создания копии существующего объекта.
Реализация этого метода у Object проверяет, реализует ли объект у которого clone() был вызван интерфейс Cloneable(). Если нет, то выбрасывается  CloneNotSupportedException. Если да, то создается объект того же класса, как исходный и его поля инициализируется теми же значениями.
Для некоторых классов стандартное поведение метода clone() работает отлично. Но если объект содержит ссылку на внешний объект, то возможно потребуется переопределить поведение метода clone(). В противном случае изменение внешнего объекта в одном классе приведет к его изменению в другом (полученном клонированием) классе.


Возвращает строковое представление объекта. При переопределении метода рекомендуется возвращать краткий но информативный результат. Для класса Object метод toString() возвращает строку, содержащую имя класса, экземпляром которого является объект и шестнадцатеричное представление хэщ-кода объекта, разделенные символом “@”.


Методы notify(), notifyAll(), wait() объекта участвуют в синхронизации независимо запущенных потоков в программе.

Класс Object предоставляет callback метод finalize(), который может вызываться для объекта когда он становится “мусором”. Реализация finalize() у Object не делает ничего. Его можно переопределить для очистки, нарпимер свободных ресурсов.

Метод finalize() может быть вызван системой автоматически, но тот момент когда он будет вызван никак не определен. По этому нельзя пологаться на этот метод, что-бы сделать свою чистку. Следует заметить, что если объект доступен для сборки и в нем переопределен метод finalize(), то он не вызовется сразу, а поместится в очередь, которая обрабатывается специально созданным для этого потоком.

Есть вероятность, что этот метод не будет вызван совсем. Это может произойти в момент, когда объект уже станет доступным для сборщика мусора и программа завершит свою работу.

Краткая выдержка про использование finalize (Джошуа Блох):
1. finalize() можно использовать только в двух случаях:
1.1. Проверка/подчистка ресурсов с логированием
1.2. При работе с нативным кодом, который не критичен к утечке ресурсов
2. finalize() замедляет работу GC по очистке объекта в 430 раз
3. finalize() может быть не вызван

Источник