Java Challengers #4: Сравнение объектов с equals() и hashCode()
В преддверии запуска нового потока по курсу «Разработчик Java» мы продолжаем перевод серии статей Java Challengers, предыдущие части которых можно прочитать по ссылкам ниже:
В этой статье вы узнаете, как связаны между собой методы equals() и hashCode() и как они используются при сравнении объектов.
Без использования equals() и hashCode() для сравнения состояния двух объектов нам нужно писать много сравнений » if «, сравнивая каждое поле объекта. Такой подход делает код запутанным и трудным для чтения. Работая вместе, эти два метода помогают создавать более гибкий и согласованный код.
Исходный код для статьи находится здесь.
Переопределение equals() и hashCode()
Переопределение метода (method overriding) — это приём при котором поведение родительского класса или интерфейса переписывается (переопределяется) в подклассе (см. Java Challengers #3: Полиморфизм и наследование, анг.). В Java у каждого объекта есть методы equals() и hashCode() и для правильной работы они должны быть переопределены.
Это native — метод, который написан на другом языке, таком как Си, и он возвращает некоторый числовой код, связанный с адресом памяти объекта. (Если вы не пишете код JDK, то не важно точно знать, как работает этот метод.)
Примечание переводчика: про значение, связанное с адресом сказано не совсем корректно (спасибо vladimir_dolzhenko). В HotSpot JVM по умолчанию используются псевдослучайные числа. Описание реализации hashCode() для HotSpot, есть здесь и здесь.
Сравнение объектов с equals()
Метод equals() используется для сравнения объектов. Чтобы определить одинаковые объекты или нет, equals() сравнивает значения полей объектов:
Во втором сравнении проверяется, является ли переданный объект null и какой у него тип. Если переданный объект другого типа, то объекты не равны.
Наконец, equals() сравнивает поля объектов. Если два объекта имеют одинаковые значения полей, то объекты совпадают.
Анализ вариантов сравнения объектов
Затем снова сравниваем два объекта Simpson :
Наконец, давайте сравним объект Simpson и экземпляр класса Object :
equals() в сравнении с ==
На первый взгляд кажется, что оператор == и метод equals() делают одно и то же, но, на самом деле, они работают по-разному. Оператор == сравнивает, указывают ли две ссылки на один и тот же объект. Например:
Во следующем примере используем переопределенный метод equals() :
Идентификация объектов с hashCode()
Использование equals() и hashCode() с коллекциями
Классы, реализующие интерфейс Set (множество) должны не допускать добавления повторяющихся элементов. Ниже приведены некоторые классы, реализующие интерфейс Set :
Посмотрим на часть реализации метода add() в HashSet :
Перед добавлением нового элемента HashSet проверяет, существует ли элемент в данной коллекции. Если объект совпадает, то новый элемент вставляться не будет.
Рекомендации по использованию equals() и hashCode()
Таблица 1. Сравнение хэш-кодов
Этот принцип в основном используется в коллекциях Set или Hash по соображениям производительности.
Правила сравнения объектов
Таблица 2.Сравнение объектов с hashCode()
Таблица 3. Сравнение объектов с equals()
Решите задачку на equals() и hashCode()
Для начала, внимательно изучите следующий код :
Сначала проанализируйте код, подумайте, какой будет результат. И только потом запустите код. Цель в том, чтобы улучшить ваши навыки анализа кода и усвоить основные концепции Java, чтобы вы могли сделать свой код лучше.
Какой будет результат?.
Что произошло? Понимание equals() и hashCode()
Первый объект в наборе будет вставлен как обычно:
Следующий объект также будет вставлен в обычном порядке, поскольку содержит значение, отличное от предыдущего объекта:
Наконец, следующий объект Simpson имеет то же значение имени, что и первый объект. В этом случае объект вставляться не будет:
Ответ
Правильный ответ — B. Вывод будет:
Частые ошибки с equals() и hashCode()
Что нужно помнить о equals() и hashCode()
Изучите больше о Java
Традиционно жду ваши комментарии и приглашаю на открытый урок, который уже 18 марта проведет наш преподаватель Сергей Петрелевич
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() по умолчанию?
Тривиальная загадка
После корректирования 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, собрано из разных источников. Основные из них:
Методы equals & hashCode: зачем, где используются, как работают
— Теперь я расскажу о не менее полезных методах equals(Object o) & hashCode().
Как ты уже, наверное, успел запомнить, в Java при сравнении ссылочных переменных сравниваются не сами объекты, а ссылки на объекты.
| Код | Пояснение | ||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| i не равно j Переменные указывают на различные объекты. Хотя объекты содержат одинаковые данные; | |||||||||||||||||||||||||||||
| Пример вызова: |
|---|
| Дробь one = new Дробь(2,3); Дробь two = new Дробь(4,6); System.out.println(one.equals(two)); |
| Результат вызова будет true. дробь 2/3 равна дроби 4/6 |
— Для большей ясности я использовала русские названия. Так можно делать только в обучающих целях.
Теперь разберем пример.
Мы переопределили метод equals, и теперь для объектов класса Дробь у него будет своя реализация.
В этом методе есть несколько проверок:
1) Если переданный для сравнения объект – null, то объекты не равны. Объект, у которого вызвали метод equals ведь точно не null.
2) Проверка на сравнение классов. Если объекты разных классов, то мы не будем пробовать их сравнить, а сразу скажем, что это различные объекты – return false.
3) Со второго класса школы все помнят, что дробь 2/3 равна дроби 4/6. А как это проверить?
| 2/3 == 4/6 |
|---|
| Умножим обе части на оба делителя (6 и 3), получим: |
| 6 * 2 == 4 * 3 |
| 12 == 12 |
| Общее правило: |
| Если a / b == c / d То a * d == c * b |
— Поэтому в третьей части метода equals мы преобразуем переданный объект к типу Дробь и сравниваем дроби.
— Понятно. Если бы мы просто сравнивали числитель с числителем и знаменатель со знаменателем, то дробь 2/3 не была бы равной 4/6.
Теперь понятно, что ты имела ввиду, когда говорила, что только разработчик класса знает, как правильно его сравнивать.
— Да, но это только половина дела. Есть еще второй метод – hashCode()
— С методом equals все понятно, а зачем нужен hashCode()?
— Метод hashCode нужен для быстрого сравнения.
У метода equals есть большой минус – он слишком медленно работает. Допустим, у тебя есть множество(Set) из миллиона элементов, и нам нужно проверить, содержит ли оно определенный объект или нет. Как это сделать?
— Можно в цикле пройтись по всем элементам и сравнить нужный объект с каждым объектом множества. Пока не найдем нужный.
— А если его там нет? Мы выполним миллион сравнений, чтобы узнать, что там нет этого объекта? Не многовато ли?
— Да, даже мне понятно, что слишком много сравнений. А что, есть другой способ?
— Да, для этого и используется hashCode().
Метод hashCode() для каждого объекта возвращает определенное число. Какое именно – это тоже решает разработчик класса, как и в случае с методом equals.
Давай рассмотрим ситуацию на примере:
Представь, что у тебя есть миллион 10-тизначных чисел. Тогда в качестве hashCode для каждого числа можно выбрать остаток от его деления на 100.
| Число | Наш hashCode |
|---|---|
| 1234567890 | 90 |
| 9876554321 | 21 |
| 9876554221 | 21 |
| 9886554121 | 21 |
— Да, с этим понятно. И что нам делать с этим hashCode-числом?
— Вместо того чтобы сравнивать числа, мы будем сравнивать их hashCode. Так быстрее.
И только если hashCode-ы равны, сравнивать уже посредством equals.
— Да, так быстрее. Но нам все равно придется сделать миллион сравнений, только уже более коротких чисел, а для тех чисел, чьи hashCode совпадают, опять вызвать equals.
— Нет, можно обойтись гораздо меньшим числом.
Представь, что наше множество хранит числа, сгруппированные по hashCode или отсортированные по hashCode (что равносильно их группировке, т.к. числа с одинаковым hashCode находятся рядом). Тогда можно очень быстро и легко отбросить ненужные группы, достаточно один раз для каждой группы проверить совпадает ли ее hashCode с hashCode заданного объекта.
Представь, что ты студент, и ищешь своего друга, которого знаешь в лицо и про которого известно, что он живет в 17 общаге. Тогда ты просто проходишься по всем общежитиям универа и в каждом общежитии спрашиваешь «это 17 общага?». Если нет, то ты отбрасываешь всех из этой общаги и переходишь к следующей. Если «да», то начинаешь ходить по всем комнатам и искать друга.
В данном примере номер общаги – 17 – это и есть hashCode.
Разработчик, который реализует функцию hashCode, должен знать следующие вещи:
А) у двух разных объектов может быть одинаковый hashCode (разные люди могут жить в одной общаге)
В) хеш-коды должны быть выбраны таким образом, чтобы не было большого количества различных объектов с одинаковыми hashCode. Это сведет все их преимущество на нет (Ты пришел в 17 общагу, а там живет пол универа. Облом-с).
И теперь самое важное. Если ты переопределяешь метод equals, обязательно нужно переопределить метод hashCode(), с учетом трех вышеописанных правил.
В нашем примере с Дробью, если бы мы взяли hashCode равный числителю, то дроби 2/3 и 4/6 имели бы разные hashCode. Дроби – одинаковые, equals говорит, что они одинаковые, но hashCode говорит, что они разные. И если перед сравнением с помощью equals сравнивать по hashCode, то получим что объекты разные и до equals просто не дойдём.
— А как правильно реализовать hashCode для дроби?
— Тут надо помнить, что одинаковым дробям обязательно должен соответствовать одинаковый hashCode.
Вариант 1: hashCode равен целой части от деления.
Для дроби 7/5 и 6/5 это будет 1.
Для дроби 4/5 и 3/5 это будет 0.
Но этот вариант плохо годится для сравнения дробей, которые заведомо меньше 1. Целая часть (hashCode) всегда будет 0.
Вариант 2: hashCode равен целой части от деления знаменателя на числитель.
Этот вариант подойдет для случая, когда значение дроби меньше 1. Если дробь меньше 1, значит перевернутая дробь больше 1. А если мы переворачиваем все дроби – это никак не скажется на их сравнении.
Итоговый вариант будет совмещать в себе оба решения:
Проверяем для дробей 2/3 и 4/6. У них должны быть равные hashCode:
| Дробь 2/3 | Дробь 4/6 | |
|---|---|---|
| числитель / знаменатель | 2 / 3 == 0 | 4 / 6 == 0 |
| знаменатель / числитель | 3 / 2 == 1 | 6 / 4 == 1 |
| числитель / знаменатель + знаменатель / числитель | 0 + 1 == 1 | 0 + 1 == 1 |
— Спасибо, Элли, было действительно интересно.
Разбираемся с 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.
