хэш код объекта java
Хэш-код объекта, 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б).
Руководство по хэш-коду () на Java
Узнайте, как работает хэш-код и как его правильно реализовать.
1. Обзор
Хэшинг является фундаментальной концепцией информатики.
В этой статье мы сосредоточимся на том, как хэш-код () работает, как он играет в коллекции и как реализовать его правильно.
Дальнейшее чтение:
Java равно () и хэш-код () Контракты
Создание равных () и хэш-кода () с Eclipse
Введение в проект Ломбок
2. Использование хэш-кода () в структурах данных
Простейшие операции по сборам могут быть неэффективными в определенных ситуациях.
Например, это вызывает линейный поиск, который является крайне неэффективным для списков огромных размеров:
Java предоставляет ряд структур данных для решения этой проблемы в частности – например, несколько Карта реализации интерфейса хэш-таблицы.
При использовании хэш-стола эти коллекции вычисляют значение хэша для данного ключа с помощью хэш-код () метод и использовать это значение внутренне для хранения данных, чтобы операции доступа были гораздо более эффективными.
3. Понимание того, как работает хэш-код ()
Проще говоря, хэш-код () возвращает значение integer, генерируемое алгоритмом хэширования.
Объекты, которые равны (в соответствии с их равными () ) должны вернуть тот же хэш-код. Для различных объектов не требуется возвращать различные хэш-коды.
Генеральный контракт хэш-код () Государств:
“Насколько это разумно практично, хэш-код () метод, определяемый классом Объект возвращает различные интеграторы для отдельных объектов. (Обычно это реализуется путем преобразования внутреннего адреса объекта в интегратор, но этот метод реализации не требуется языком программирования JavaTM.)»
4. Наивный хэш-код () Реализация
Это на самом деле довольно просто иметь наивный хэш-код () полностью придерживается вышеупомянутого контракта.
Чтобы продемонстрировать это, мы собираемся определить образец Пользователь класс, переопределяет реализацию метода по умолчанию:
Пользователь класс предоставляет пользовательские реализации для обеих равны () и хэш-код () которые полностью придерживаются соответствующих контрактов. Более того, нет ничего незаконного в том, чтобы хэш-код () возврат любого фиксированного значения.
Однако эта реализация ухудшает функциональность хэш-таблиц практически до нуля, так как каждый объект будет храниться в одном и том же ведре.
В этом контексте поиск хэш-таблицы выполняется линейно и не дает нам реального преимущества – подробнее об этом в разделе 7.
5. Улучшение хэш-кода () Реализация
Давайте немного улучшить текущее хэш-код () реализации путем включения всех областей Пользователь класс, чтобы он может дать различные результаты для неравных объектов:
В общих чертах можно сказать, что это разумный хэш-код () реализации, до тех пор, как мы равны () реализации в соответствии с ним.
6. Стандартный хэш-код () Реализации
Чем лучше алгоритм хэширования, который мы используем для вычисления хэш-кодов, тем лучше будет производительность хэш-таблиц.
Давайте посмотрим на “стандартную” реализацию, которая использует два основных числа, чтобы добавить еще больше уникальности в вычисленные хэш-коды:
Хотя очень важно понимать роли, которые хэш-код () и равны () методы игры, мы не должны осуществлять их с нуля каждый раз, так как большинство IDEs может генерировать пользовательские хэш-код () и равны () реализации и с Java 7, мы получили Объекты.хэш () утилита для удобного хэширования:
IntelliJ IDEA генерирует следующую реализацию:
И Затмение производит этот:
Теперь достаточно аннотировать Пользователь класс с @EqualsAndHashCode :
Точно так же, если мы хотим Апач Викисклад Ланг HashCodeBuilder класс для создания хэш-код () реализации для нас, общий ланг Зависимость Maven должна быть включена в файл pom:
И хэш-код () могут быть реализованы так:
Что можно заметить здесь, что все эти реализации использовать номер 31 в той или иной форме – это потому, что 31 имеет хорошее свойство – его умножение может быть заменено немного сдвиг, который быстрее, чем стандартное умножение:
7. Обработка хэш-столкновений
Внутреннее поведение хэш-таблиц поднимает соответствующий аспект этих структур данных: даже при эффективном алгоритме хэширования два или более объектов могут иметь один и тот же хэш-код, даже если они неравны. Таким образом, их хэш-коды будут указывать на то же ведро, даже если они будут иметь различные хэш-ключи таблицы.
“Когда два или более объектов указывают на одно и то же ведро, они просто хранятся в связанном списке. В этом случае таблица хэша является массивом связанных списков, и каждый объект с одним и тем же хэшом прибвётся к связанному списку индекса ведра в массиве.
Методологии столкновения хэша в двух словах показывают, почему так важно реализовать хэш-код () эффективно .
8. Создание тривиального приложения
Проверить функциональность стандартного хэш-код () реализации, давайте создадим простое java-приложение, которое добавляет некоторые Пользователь объекты для HashMap и использует SLF4J для регистрации сообщения на консоли каждый раз, когда метод называется.
Вот точка входа образца приложения:
И это хэш-код () реализация:
Единственная деталь, которую стоит подчеркнуть здесь, состоит в том, что каждый раз объект хранится на хэш-карте и проверяется с содержитКей () метод, хэш-код () вызывается и вычисляемый хэш-код распечатан на консоли:
9. Заключение
Понятно, что производство эффективных хэш-код () реализация часто требует смешения нескольких математических понятий (т.е. простых и произвольных чисел), логических и базовых математических операций.
Разбираемся с 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.
В предыдущей части, если не читали вот она, мы подробно рассмотрели работу метода equals(), его контракт, ошибки и их исправления. Теперь настала очередь второго попугая-неразлучника – метода hashCode().
При переопределении метода equals() мы всегда должны переопределять метод hashCode(). Метод hashCode() – вычисляет целочисленное значение для конкретного элемента класса, чтобы использовать его для быстрого поиска и доступа к этому элементу в hash-структурах данных, например, HashMap, HashSet и прочих. Почему важно переопределять hashCode() всегда вместе с методом equals()? Развернуто ответим на этот вопрос. Пожалуй, необходимо и достаточно знать два важных аспекта, чтобы понять, почему необходимо делать переопределение методов вместе:
Что такое хеш-таблицы (Hash Tables)?
Хэш – таблицы – это своего рода ассоциативный массив, хранящий значения в виде “ключ-значение”. Рассмотрим работу вставки элемента в хеш-таблицу:
На деле все просто, но если еще раз перечитать контракт hashCode() и equals(), то все становиться немного труднее: возможны коллизии – два разных объекта имеют одинаковый hash-код. Что делать? Эта проблема и ее решение отражены на рисунке выше. Два объекта John Smith и Sandra Dee имеют один и тот же hash-код. Для разрешения это коллизии мы просто берем за структуру bucket направленный список. И сохраняем два значения по одному hash-коду.
Как сломать хеш – таблицу?
При неверной реализации метода hashCode() мы можем легко сломать hash-таблицу. Вернее даже сказать не сломать, а сделать ее вырожденной. Например, переопределив метод 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, собрано из разных источников. Основные из них: