Хэш-код объекта, hashCode
Рассмотрим простой пример HashCodeTest.java, который в консоли будет печатать значение hashCode.
Значение hashCode программы можно увидеть в консоли.
По умолчанию, функция hashCode() для объекта возвращает номер ячейки памяти, где объект сохраняется. Поэтому, если изменение в код приложения не вносятся, то функция должна выдавать одно и то же значение. При незначительном изменении кода значение hashCode также изменится.
Функция сравнения объектов equals()
В родительском классе Object наряду с функцией hashCode() имеется еще и логическая функция equals(Object)/ Функция equals(Object) используется для проверки равенства двух объектов. Реализация данной функции по умолчанию просто проверяет по ссылкам два объекта на предмет их эквивалентности.
Рассмотрим пример сравнения двух однотипных объектов Test следующего вида :
Создадим 2 объекта типа Test с одинаковыми значениями и сравним объекты с использованием функции equals().
Результат выполнения программы будет выведен в консоль :
Не трудно было догадаться, что результат сравнения двух объектов вернет «false». На самом деле, это не совсем верно, поскольку объекты идентичны и в real time application метод должен вернуть true. Чтобы достигнуть этого корректного поведения, необходимо переопределить метод equals() объекта Test.
Вот теперь функция сравнения equals() возвращает значение «true». Достаточно ли этого? Попробуем добавить объекты в коллекцию HashSet и посмотрим, сколько объектов будет в коллекции? Для этого в в метод main примера EqualsExample добавим следующие строки :
Однако в коллекции у нас два объекта.
Поскольку Set содержит только уникальные объекты, то внутри HashSet должен быть только один экземпляр. Чтобы этого достичь, объекты должны возвращать одинаковый hashCode. То есть нам необходимо переопределить также функцию hashCode() вместе с equals().
Таким образом, переопределяя методы hashCode() и equals() мы можем корректно управлять нашими объектами, не допуская их дублирования.
Использование библиотеки commons-lang.jar для переопределения hashCode() и equals()
Процесс формирования методов hashCode() и equals() в IDE Eclipse автоматизирован. Для создания данных методов необходимо правой клавишей мыши вызвать контекстное меню класса (кликнуть на классе) и выбрать пункт меню Source (Class >> Source), в результате которого будет открыто следующее окно со списком меню для класса.
Выбираем пункт меню «Generate hachCode() and equals()» и в класс будут добавлены соответствующие методы.
Библиотека Apache Commons включает два вспомогательных класса HashCodeBuilder и EqualsBuilder для вызова методов hashCode() и equals(). Чтобы включить их в класс необходимо внести следующие изменения.
Примечание : желательно в методах hashCode() и equals() не использовать ссылки на поля, заменяйте их геттерами. Это связано с тем, что в некоторых технологиях java поля загружаются при помощи отложенной загрузки (lazy load) и не доступны, пока не вызваны их геттеры.
Скачать пример
Исходный код рассмотренного примера в виде проекта Eclipse можно скачать здесь (263 Kб).
Как работает hashCode() по умолчанию?
Тривиальная загадка
После корректирования toString() наш кастомный hashCode() перестал вызываться. Мы пропустили тест.
Чем является реализация по умолчанию hashCode()?
Здравый смысл подсказывает, что идентификационный хеш использует целочисленное представление адреса памяти. Об этом свидетельствует документация J2SE на Object.hashCode():
. обычно реализуется с помощью конвертации внутреннего адреса объекта в целочисленное значение, но в Java эта методика не требуется.
Однако с этим связаны проблемы, поскольку контракт метода (method contract) требует:
При применении к одному и тому же объекту более одного раза в ходе выполнения Java-приложения метод hashCode должен в обязательном порядке возвращать одно и то же целочисленное значение.
Учитывая, что JVM будет перемещать объекты (например, при сборке мусора в ходе продвижения или уплотнения), после вычисления идентификационного хеша объекта мы должны сделать так, чтобы он как-то отслеживал местоположение самого объекта.
Например, можно взять текущую позицию объекта в памяти при первом вызове hashCode() и сохранить её где-нибудь, например в заголовке объекта. Тогда при перемещении объекта в другое место с ним переедет и исходный хеш. Недостаток способа: два объекта могут иметь одинаковый хеш, но это разрешено спецификацией.
Лучшим подтверждением будет посмотреть в исходный код. К сожалению, дефолтная java.lang.Object::hashCode() является нативной функцией:
Настоящий hashCode()
Обратите внимание, что идентификационная реализация hashCode() зависит от JVM. Я буду рассматривать только исходный код OpenJDK, помните об этом при каждом дальнейшем упоминании JVM. Все ссылки относятся к набору изменений 5934:87ee5ee27509 дерева Hotspot, и полагаю, что большинство из них применимы и к Oracle JVM, но в других машинах есть свои нюансы.
Можно наивно ожидать, что ObjectSynchronizer::FastHashCode() делает что-то вроде:
Но оказывается, что там функция на сотню строк. А это куда сложнее. По крайней мере, мы можем отметить пару блоков «если-не-существует-то-генерировать»:
Реальное генерирование идентификационного хеша
0. Случайно сгенерированное число.
1. Функция адреса объекта в памяти.
2. Жёстко запрограммированное значение 1 (используется при тестировании на чувствительность (sensitivity testing)).
3. Последовательность.
4. Адрес объекта в памяти, приведённый к целочисленному значению.
5. Состояние потока, объединённое с xorshift (https://en.wikipedia.org/wiki/Xorshift)
Какой метод используется по умолчанию? Согласно globals.hpp, в OpenJDK 8 это метод 5:
Так что, если я не ошибаюсь, как минимум с шестой версии реализация по умолчанию hashCode в OpenJDK не имеет ничего общего с адресом памяти.
Заголовки объектов и синхронизация
Вернёмся немного и рассмотрим пару пропущенных моментов. Во-первых, функция ObjectSynchronizer::FastHashCode() выглядит слишком сложной, в ней используется больше 100 строк кода для выполнения того, что мы считали тривиальной операцией «получить-или-сгенерировать». Во-вторых, что это вообще такое – monitor – и почему у него есть заголовки нашего объекта?
Структура слова mark — хорошее место для начала изысканий. В OpenJDK она выглядит так:
Для 32 и 64 битов формат несколько различается. Во втором случае могут быть два варианта, в зависимости от того, включены ли указатели сжатых объектов (Compressed Object Pointers). В Oracle и OpenJDK 8 по умолчанию они включены.
Таким образом, заголовки объектов могут относиться к свободному блоку или к реальному объекту, так что возможны несколько разных состояний. В простейшем случае («нормальный объект») идентификационный хеш сохраняется напрямую в младшие биты заголовка.
Попробуем ответить на все эти вопросы.
Привязанная блокировка (biased locking)
Привязанные объекты — это результат привязанной блокировки. Это запатентованный механизм, по умолчанию используемый начиная с HotSpot 6. Он пытается снизить стоимость блокирования объектов. Подобные операции дороги, поскольку ради безопасной обработки запросов блокировки/разблокировки объекта от разных потоков их реализации часто опираются на атомарные процессорные инструкции (сравнение с обменом). Но подмечено, что во многих реализациях большинство объектов когда-либо блокируются лишь одним потоком, так что использование атомарных операций зачастую расточительно. Чтобы этого избежать, JVM’ы с привязанной блокировкой позволяют потокам попытаться самостоятельно «привязать» объект. Когда потоку это удаётся, он может блокировать/разблокировать объект без использования атомарных инструкций. А раз у нас нет потоков, борющихся за один и тот же объект, то мы получаем прирост производительности.
Погодите. Здесь просто отменяются привязка и привязанная блокировка объекта (метод false означает «не пытайся снова привязать»). Несколькими строками ниже это остаётся действительно неизменным:
Если я прочитал правильно, то простой запрос идентификационного хеша объекта отключает привязанную блокировку, что предотвратит любые попытки заблокировать объект для использования дорогих атомарных инструкций.
Почему сохранение состояния привязанной блокировки конфликтует с сохранением идентификационного хеша?
Для ответа на этот вопрос мы должны понять, где может находиться слово mark (содержащее идентификационный хеш) в зависимости от состояния блокировки объекта. Ниже показаны возможные переходы:
Моё (возможно, ошибочное) мнение таково.
Для четырёх состояний в верхней части схемы OpenJDK сможет использовать представления thin-блокировок. В простейшем случае (без блокировок) это означает хранение идентификационного хеша и других данных прямо в пространстве слова mark в объекте:
В более сложных случаях это пространство используется для хранения указателя на «запись о блокировке». Тогда слово mark будет «перемещено» в другое место.
Поскольку заблокировать объект у нас только пытается один поток, этот указатель фактически ссылается на область памяти в собственном стеке потока. Это хорошо по двум причинам:
Нашим нуждам удовлетворяет структура ObjectMonitor, которая на схеме называется «тяжёлый монитор». Оставшееся в заголовке объекта значение указывает не на «перемещённое слово mark», а на реальный объект (монитор). Теперь для доступа к идентификационному хешу требуется «получить монитор» (inflating the monitor): сделать указатель на объект и считывать/изменять в зависимости от поля, содержащего перемещённое слово mark. Это дороже и требует координации.
В строках с L640 по L680 выполняется поиск заголовка и проверка на наличие закешированного идентификационного хеша. Я считаю, что это быстрый способ проверки случаев, когда нам не нужно получить монитор.
Начиная с L682 придётся стиснуть зубы:
Это даёт разумное объяснение, почему вызов hashCode() применительно к объекту класса, который не переопределяет реализацию по умолчанию, делает объекты недоступными для привязанной блокировки:
Промежуточные итоги
Бенчмарки
Для проверки своих умозаключений я написал простой тест JMH.
Бенчмарк (исходник) делает нечто вроде этого:
Кастомный хеш в четыре раза ускоряет цикл блокировки/разблокировки по сравнению с идентификационным хешем (который отключает привязанную блокировку). Когда за блокировку конкурируют два потока, привязанная блокировка отключается в любом случае, так что между двумя методам хеширования не наблюдается значимой разницы.
Метод хеширования больше не влияет на результат, и withoutIdHash теряет своё преимущество.
Все бенчмарки прогонялись на Intel Core i5 2,7 ГГц.
Ссылки
Всё, что не является дикими спекуляциями и моими слабыми рассуждениями в попытке осмыслить исходные коды JVM, собрано из разных источников. Основные из них:
Разбираемся с hashCode() и equals()
Что такое хеш-код?
Если очень просто, то хеш-код — это число. На самом деле просто, не так ли? Если более точно, то это битовая строка фиксированной длины, полученная из массива произвольной длины (википедия).
Пример №1
Выполним следующий код:
Вторая часть объяснения гласит:
полученная из массива произвольной длины.
В итоге, в терминах Java, хеш-код — это целочисленный результат работы метода, которому в качестве входного параметра передан объект.
Подведём итог:
Сперва, что-бы избежать путаницы, определимся с терминологией. Одинаковые объекты — это объекты одного класса с одинаковым содержимым полей.
Понятие эквивалентности. Метод equals()
Начнем с того, что в java, каждый вызов оператора new порождает новый объект в памяти. Для иллюстрации создадим какой-нибудь класс, пускай он будет называться “BlackBox”.
Пример №2
Выполним следующий код:
Во втором примере, в памяти создастся два объекта.
Эквивалентность и хеш-код тесно связанны между собой, поскольку хеш-код вычисляется на основании содержимого объекта (значения полей) и если у двух объектов одного и того же класса содержимое одинаковое, то и хеш-коды должны быть одинаковые (см. правило 2).
Класс Object
При сравнение объектов, операция “ == ” вернет true лишь в одном случае — когда ссылки указывают на один и тот-же объект. В данном случае не учитывается содержимое полей.
Заглянем в исходный код метода hashCode() в классе Object :
При вычислении хэш-кода для объектов класса Object по умолчанию используется Park-Miller RNG алгоритм. В основу работы данного алгоритма положен генератор случайных чисел. Это означает, что при каждом запуске программы у объекта будет разный хэш-код.
Но, как мы помним, должно выполняться правило: “если у двух объектов одного и того же класса содержимое одинаковое, то и хеш-коды должны быть одинаковые ”. Поэтому, при создании пользовательского класса, принято переопределять методы hashCode() и equals() таким образом, что бы учитывались поля объекта.
Это можно сделать вручную либо воспользовавшись средствами генерации исходного кода в IDE. Например, в Eclipse это Source → Generate hashCode() and equals().
В итоге, класс BlackBox приобретает вид:
Теперь методы hashCode() и equals() работают корректно и учитывают содержимое полей объекта:
Кому интересно переопределение в ручную, можно почитать Effective Java — Joshua Bloch, chapter 3, item 8,9.
Что такое hashcode java
Объявление метода выглядит так:
Представим, что у нас есть массив пар ключ-значение. Для поиска по ключу в таком массиве вам надо обойти весь массив, заглянуть в каждую ячейку и сравнить ключ. Долго? Долго!
Если планируется использовать объекты в качестве ключа в ассоциативном массиве, то переопределять hashCode надо обязательно.
Еще раз посмотрим на метод:
Контракт hashCode предъявляет следующие требования к реализации:
Равенство объектов проверяется через вызов метода equals.
Логично, что коллизии возможны, так как размер int ограничен, да и реализации хэш-функции могут быть далеко не идеальны.
Что это за значения? По-умолчанию hashCode() возвращает значение, которое называется идентификационный хэш (identity hash code). В документации сказано:
This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the Java™ programming language.
Более подробно об этом можно прочесть в разделе полезные ссылки.
Для равных объектов такой метод вернет одно и то же число, что удовлетворяет спецификации. Но, делать так категорически не рекомендуется.
Правила вычисления hashCode :
Если поле это ссылка на другой объект, то рекурсивно вызовите hashCode()
После каждого обработанного поля объединяем его hashCode с текущим значением:
Пример приведем с помощью многострадального класса Person :
Также, с версии Java 8+ в классе java.util.Objects есть вспомогательные методы для генерации hashCode :
Использование hashCode в equals
Так как hashCode допускает возникновение коллизий, то использовать его в equals нет смысла. Методы идут в паре, но использование одного в другом не желательно и бесмыссленно.
Классы-обертки над примитивами
Помните, что хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива!
Решением является использовать статический метод для рассчета hashCode у массивов: Arrays.hashCode(. ) :
Эти методы всегда должны определяться парой!
Заметки о реализации hashCode() в Java
Часто на собеседованиях приходится спрашивать про функцию hashCode().
Я не буду здесь перечислять все свойства этой функции и ее связь с другой, не менее важной функцией equals(). Данная информация есть во всех учебниках по Java и я не вижу смысла ее здесь повторять. Мне бы хотелось остановиться лишь на одном свойстве: hashCode должен быть равномерно распределен на области значений функции. Я задумался: “А чем гарантировано равномерное распределение?”
Забегая вперед, скажу, что я пришел к довольно интересным выводам. Мне бы хотелось, чтобы меня поправили, если я где-то ошибся в рассуждениях.
Спросим у Гуру
Вначале я решил обратиться к Java документации на Object.hashCode(). Как каждый может убедиться, там нет информации, которая нас интересует. После этого я пошел к Гуру. Брюс Эккель написал 5 страниц, кивнул на Блоха (точнее списал у него), привел пример со строками, а в конце посоветовал использовать “полезные библиотеки”. Джошуа Блох поступил лучше: он предложил алгоритм вычисления, высказался о пользе простых чисел и… тоже привел пример. Я не могу не удержаться от цитирования:
The multiplier 37 was chosen because it is an odd prime. … The advantages of using a prime number are less clear, but it is traditional to use primes for this purpose.
Никто из авторов не удосужился провести анализ приведенного алгоритма и доказать его корректность.
Алгоритм (в вольном пересказе)
1) Взять число, отличное от нуля, к примеру 17. Для удобства, назовем его p. Присвоить переменной result это начальное значение (result = p).
2) Для каждого поля вычислить hashCode c по некоторым правилам. Эти правила, нас сейчас не очень интересуют, они не влияют на результат. Для простоты будем работать с целыми числами (int) и будем принимать hashCode равным самому значению числа…
3) Скомбинировать result и полученный hashCode с: result = result * q + c, где q = 37, потому что, как мы помним, оно нечетное и простое.
4) Вернуть result.
Анализ алгоритма
Чтобы быть более конкретным, я стану рассматривать точки с целочисленными координатами (x, y) на плоскости в двухмерном пространстве, при условии, что x>= 0, y>=0.
Запишем hash функцию для точки P1 (x1, y1):
q(x1-x2) + y1 — y2 = 0 (Обратите внимание, что множитель, содержащий p пропал после вычитания)
(x1 — x2) / (y2-y1) = q (понятно, что знаменатель должен быть отличен от нуля)
Если подобрать такие значения x1, x2, y1, y2, что выполнится полученное равенство, то эти координаты будут соответствовать значениям аргумента hash функции, при которой возникнет коллизия.
Можно предложить такой вариант:
То есть точки P(38, 1) и P(1, 2) имеют одинаковый hashCode… Я думал, что имея 4 миллиарда возможных значений для hash кода, можно было бы избежать коллизий хотя бы в квадрате 100×100!
Теперь рассмотрим случай n переменных, независимо изменяющихся от 0 до некоторого M. Хотелось бы найти максимальное значение M, такое, что хорошо написанная функция hashCode не имела бы коллизий на промежутке от 0 до M по всем n переменным. После недолгих раздумий, получаем значение для M:
Для случая точек на плоскости M принимает значение 65536.
Похоже, что формула, приведенная Блохом, будет давать приемлемое распределение hash кодов для случая 8 и более переменных.
Рассмотрим теперь точки в трехмерном пространстве. Напишем небольшую программу, которая в тройном цикле перебирает точки от 0 до 100 (всего миллион точек) и считает количество коллизий. Код этой программы элементарный, поэтому не буду его здесь приводить. Интересен результат: я получил 901692 коллизий! То есть чуть более, чем 90%. Получается, что Блох, под видом hash функции, предложил функцию для получения коллизий?
Хороший hashCode для случая двух переменных
p*(x1-x2) + q(y1-y2) = 0
или
(x1-x2)/(y2-y1)=q/p (при условии, что знаменатель не равен нулю)
Выводы
Как писал Дональд Кнут в главе про генератор псевдослучайных последовательностей, если алгоритм выглядит сложно и запутанно, это еще не означает, что он работает правильно (недословное изложение).
Те кто используют реализацию hash функции от Джошуа Блоха, но имеют большое количество хешируемых переменных, могут спать спокойно. Так же могут не волноваться те, у кого различного рода Hash-коллекции не являются узким местом в производительности.
Если же вы бьетесь за производительность своего кода, учитываете все возможные мелочи, то вам, пожалуй, следует взглянуть на свои реализации hashCode() свежим взглядом. Учитывая, что хешируемые значения, могут быть не равномерно распределены для вашей конкретной бизнес области, вы сможете написать hash функцию с лучшим распределением hash кодов, чем любой сгенерированный вариант. Переписав hashCode(), вам, возможно, следует взглянуть на equals(): может быть вы сможете меньшим числом проверок вернуть значение false.
Спасибо тем, кто дочитал до конца.
Литература:
Bruce Eckel “Thinking in Java Third Edition”
Joshua Bloch “Effective Java: Programming Language Guide”
