Что такое hashcode java
Сразу же скажу, что статья во многом опирается базовые понятия алгебры, которые к великому счастью легко и быстро осознаются при помощи всего-лишь метода внимательного разглядывания. Поехали.
В Java так устроено, что любой класс, который вы определяете, наследуется от класса Object. Таким образом класс Object является суперклассом любого класса в любой программе.
Прежде всего я должен описать главные правила для любых реализаций этих двух методов, которые нужно обязательно соблюдать, запомнить как аксиому:
1). Если x.equals(y) == true, то обязательно hashcode(x) == hashcode(y)
2) Если hashcode(x) == hashcode(y), то не обязательно x.equals(y) == true
Отношение эквивалентности (алгебра)
симметричным (для любых x, y выполняется: если x = y, то y = x)
рефлексивным (для любого x выполняется: x = x)
транзитивным (для любых x, y, z выполняется: если x = y и y = z, то x = z)
Метод .equals() в классе Object реализован примерно следующим образом:
Фактически он делает следующее: Он принимает в качестве аргумента ссылочную переменную и проверяет, ссылается ли они на тот же объект (ту же область памяти, если быть точнее), что и объект, к которому мы применили метод .equals().
Таким образом, стандартная реализация .equals() выстраивает отношение эквивалентности, которое можно описать так: две ссылки эквивалентны, если они ссылаются на одну и ту же область памяти.
Очевидно, гораздо более применимой будет возможность сравнивать объекты по какому-нибудь другому критерию. Часто метод .equals() переопределяют так, чтобы он сравнивал объекты по значениям их полей.
К примеру, если классы двух объектов, на которые указывают ссылки, совпадают и все значения их полей совпадают, то эти два объекта эквивалентны между собой. Легко проследить, что такое определение не противоречит математической идеологии.
Конкретную кодовую реализацию я приводить не буду, потому что она не так важна, как сама идея
Это и другие возможные переопределения метода .equals() мало того, что расширяют круг наших возможностей, так ещё и не лишают старых, ведь мы по прежнему имеем возможность проверять, ссылаются ли две ссылки на одну область памяти, используя операнд ==, вместо прежнего .equals()
Сюръекция (алгебра)
Если немного более подробно разобрать это определение, то мы увидим следующее:
Даже несколько элементов из X могут быть сопоставлены одному и тому же элементу из Y (это называется коллизией).
Возможно есть такое элемент из X, и даже возможно не один, что он не сопоставлен никакому элементу из Y. (см. рисунок, всё интуитивно)
Что происходит в java?
Метод .hashcode() как-раз осуществляет сюръекцию. Множеством X выступает множество всевозможных объектов которые мы можем создать, множеством Y выступает область значений типа данных int. Метод .hashcode() вычисляет каким-то скрытым от нас способом целое число, опираясь на объект, к которому применяется.
Единственное отличие метода .hashcode() от сюръекции в том, что любой объект может быть обработан методом .hashcode()
Здесь нет элементов по типу E из пред. рисунка
Насколько я понял, точно так никто в этом и не разобрался. Есть много версий:
Сама функция написана не на Java а вообще на C.
И многие другие. В общем каким-то образом она всё же устроена, но самое главное в том, что стандартная реализация .hashcode() со стандартной реализацией .equals() подчиняются правилу, приведённому в самом начале статьи
Основной причиной для изменения метода .hashcode() является то, что желают изменить .equals(), однако смена стандартной реализации .equals() приводит к нарушению правила из начала статьи
Заметки о реализации 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”
Как работает 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 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() и 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.