Java object hashcode
Хэш-код объекта, hashCode
В классе Object, который является родительским классом для объектов java, определен метод hashCode(), позволяющий получить уникальный целый номер для данного объекта. Когда объект сохраняют в коллекции типа HashSet, то данный номер позволяет быстро определить его местонахождение в коллекции и извлечь. Функция hashCode() объекта Object возвращает целое число int, размер которого равен 4-м байтам и значение которого располагается в диапазоне от -2 147 483 648 до 2 147 483 647.
Рассмотрим простой пример 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().
Вот теперь все будет корректно выполняться — для двух объектов с одинаковыми параметрами функция equals() вернет значение «true», и в коллекцию попадет только один объект. В консоль будет выведен следующий текст работы программы :
Таким образом, переопределяя методы 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() и equals()
Что такое хеш-код?
Если очень просто, то хеш-код — это число. На самом деле просто, не так ли? Если более точно, то это битовая строка фиксированной длины, полученная из массива произвольной длины (википедия).
Пример №1
Выполним следующий код:
В результате выполнения программы в консоль выведется целое 10-ти значное число. Это число и есть наша битовая строка фиксированной длины. В java она представлена в виде числа примитивного типа int , который равен 4-м байтам, и может помещать числа от -2 147 483 648 до 2 147 483 647. На данном этапе важно понимать, что хеш-код это число, у которого есть свой предел, который для java ограничен примитивным целочисленным типом int.
Вторая часть объяснения гласит:
полученная из массива произвольной длины.
Под массивом произвольной длины мы будем понимать объект. В 1 примере в качестве массива произвольной длины у нас выступает объект типа Object .
В итоге, в терминах Java, хеш-код — это целочисленный результат работы метода, которому в качестве входного параметра передан объект.
Этот метод реализован таким образом, что для одного и того-же входного объекта, хеш-код всегда будет одинаковым. Следует понимать, что множество возможных хеш-кодов ограничено примитивным типом int , а множество объектов ограничено только нашей фантазией. Отсюда следует утверждение: “Множество объектов мощнее множества хеш-кодов”. Из-за этого ограничения, вполне возможна ситуация, что хеш-коды разных объектов могут совпасть.
Здесь главное понять, что:
- Если хеш-коды разные, то и входные объекты гарантированно разные.
- Если хеш-коды равны, то входные объекты не всегда равны.
Ситуация, когда у разных объектов одинаковые хеш-коды называется — коллизией. Вероятность возникновения коллизии зависит от используемого алгоритма генерации хеш-кода.
Подведём итог:
Сперва, что-бы избежать путаницы, определимся с терминологией. Одинаковые объекты — это объекты одного класса с одинаковым содержимым полей.
- для одного и того-же объекта, хеш-код всегда будет одинаковым;
- если объекты одинаковые, то и хеш-коды одинаковые (но не наоборот, см. правило 3).
- если хеш-коды равны, то входные объекты не всегда равны (коллизия);
- если хеш-коды разные, то и объекты гарантированно разные;
Понятие эквивалентности. Метод equals()
Начнем с того, что в java, каждый вызов оператора new порождает новый объект в памяти. Для иллюстрации создадим какой-нибудь класс, пускай он будет называться “BlackBox”.
Пример №2
Выполним следующий код:
Создадим класс для демонстрации BlackBox .
Во втором примере, в памяти создастся два объекта.
Но, как вы уже обратили внимание, содержимое этих объектов одинаково, то есть эквивалентно. Для проверки эквивалентности в классе Object существует метод equals() , который сравнивает содержимое объектов и выводит значение типа boolean true , если содержимое эквивалентно, и false — если нет.
Эквивалентность и хеш-код тесно связанны между собой, поскольку хеш-код вычисляется на основании содержимого объекта (значения полей) и если у двух объектов одного и того же класса содержимое одинаковое, то и хеш-коды должны быть одинаковые (см. правило 2).
Я написал “должно быть”, потому что если вы выполните предыдущий пример, то на самом деле результатом выполнения всех операций будет false . Для пояснения причин, заглянем в исходные коды класса Object .
Класс Object
Как известно, все java-классы наследуются от класса Object . В этом классе уже определены методы hashCode() и equals() .
Определяя свой класс, вы автоматически наследуете все методы класса Object . И в ситуации, когда в вашем классе не переопределены ( @overriding ) hashCode() и equals() , то используется их реализация из Object .
Рассмотрим исходный код метода equals() в классе Object .
При сравнение объектов, операция “ == ” вернет true лишь в одном случае — когда ссылки указывают на один и тот-же объект. В данном случае не учитывается содержимое полей.
Выполнив приведённый ниже код, equals вернет true .
Теперь понято, почему Object.equals() работает не так как нужно, ведь он сравнивает ссылки, а не содержимое объектов.
Далее на очереди hashCode() , который тоже работает не так как полагается.
Заглянем в исходный код метода hashCode() в классе Object :
Вот собственно и вся реализация. Ключевое слово native означает, что реализация данного метода выполнена на другом языке, например на C, C++ или ассемблере. Конкретный native int hashCode() реализован на C++, вот исходники — http://hg.openjdk.java.net/jdk7/jdk7/hotspot/file/tip/src/share/vm/runtime/synchronizer.cpp функция get_next_hash .
При вычислении хэш-кода для объектов класса Object по умолчанию используется Park-Miller RNG алгоритм. В основу работы данного алгоритма положен генератор случайных чисел. Это означает, что при каждом запуске программы у объекта будет разный хэш-код.
Получается, что используя реализацию метода hashCode() от класса Object , мы при каждом создании объекта класса new BlackBox() , будем получать разные хеш-коды. Мало того, перезапуская программу, мы будем получать абсолютно разные значения, поскольку это просто случайное число.
Но, как мы помним, должно выполняться правило: “если у двух объектов одного и того же класса содержимое одинаковое, то и хеш-коды должны быть одинаковые ”. Поэтому, при создании пользовательского класса, принято переопределять методы hashCode() и equals() таким образом, что бы учитывались поля объекта.
Это можно сделать вручную либо воспользовавшись средствами генерации исходного кода в IDE. Например, в Eclipse это Source → Generate hashCode() and equals().
В итоге, класс BlackBox приобретает вид:
Теперь методы hashCode() и equals() работают корректно и учитывают содержимое полей объекта:
Кому интересно переопределение в ручную, можно почитать Effective Java — Joshua Bloch, chapter 3, item 8,9.
Gu >Last modified: December 24, 2019
I just announced the new Learn Spring course, focused on the fundamentals of Spring 5 and Spring Boot 2:
In the 9 years of running Baeldung, I’ve never, ever done a «sale».
But. we’ve also not been through anything like this pandemic either.
And, if making my courses more affordable for a while is going to help a company stay in business, or a developer land a new job, make rent or be able to provide for their family — then it’s well worth doing.
Effective immediately, all Baeldung courses are 33% off their normal prices!
You’ll find all three courses in the menu, above, or here.
1. Overview
Hashing is a fundamental concept of computer science.
In Java, efficient hashing algorithms stand behind some of the most popular collections we have available – such as the HashMap (for an in-depth look at HashMap, feel free to check this article) and the HashSet.
In this article, we’ll focus on how hashCode() works, how it plays into collections and how to implement it correctly.
Further reading:
Java equals() and hashCode() Contracts
Generate equals() and hashCode() with Eclipse
Introduction to Project Lombok
2. Usage of hashCode() in Data Structures
The simplest operations on collections can be inefficient in certain situations.
For example, this triggers a linear search which is highly ineffective for lists of huge sizes:
Java provides a number of data structures for dealing with this issue specifically – for example, several Map interface implementations are hash tables.
When using a hash table, these collections calculate the hash value for a given key using the hashCode() method and use this value internally to store the data – so that access operations are much more efficient.
3. Understanding How hashCode() Works
Simply put, hashCode() returns an integer value, generated by a hashing algorithm.
Objects that are equal (according to their equals()) must return the same hash code. It’s not required for different objects to return different hash codes.
The general contract of hashCode() states:
- Whenever it is invoked on the same object more than once during an execution of a Java application, hashCode() must consistently return the same value, provided no information used in equals comparisons on the object is modified. This value needs not remain consistent from one execution of an application to another execution of the same application
- If two objects are equal according to the equals(Object) method, then calling the hashCode() method on each of the two objects must produce the same value
- It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, developers should be aware that producing distinct integer results for unequal objects improves the performance of hash tables
“As much as is reasonably practical, the hashCode() method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)”
4. A Naive hashCode() Implementation
It’s actually quite straightforward to have a naive hashCode() implementation that fully adheres to the above contract.
To demonstrate this, we’re going to define a sample User class that overrides the method’s default implementation:
The User class provides custom implementations for both equals() and hashCode() that fully adhere to the respective contracts. Even more, there’s nothing illegitimate with having hashCode() returning any fixed value.
However, this implementation degrades the functionality of hash tables to basically zero, as every object would be stored in the same, single bucket.
In this context, a hash table lookup is performed linearly and does not give us any real advantage – more on this in section 7.
5. Improving the hashCode() Implementation
Let’s improve a little bit the current hashCode() implementation by including all fields of the User class so that it can produce different results for unequal objects:
This basic hashing algorithm is definitively much better than the previous one, as it computes the object’s hash code by just multiplying the hash codes of the name and email fields and the id.
In general terms, we can say that this is a reasonable hashCode() implementation, as long as we keep the equals() implementation consistent with it.
6. Standard hashCode() Implementations
The better the hashing algorithm that we use to compute hash codes, the better will the performance of hash tables be.
Let’s have a look at a “standard” implementation that uses two primes numbers to add even more uniqueness to computed hash codes:
While it’s essential to understand the roles that hashCode() and equals() methods play, we don’t have to implement them from scratch every time, as most IDEs can generate custom hashCode() and equals() implementations and since Java 7, we got an Objects.hash() utility method for comfortable hashing:
IntelliJ IDEA generates the following implementation:
And Eclipse produces this one:
In addition to the above IDE-based hashCode() implementations, it’s also possible to automatically generate an efficient implementation, for example using Lombok. In this case, the lombok-maven dependency must be added to pom.xml:
It’s now enough to annotate the User class with @EqualsAndHashCode:
Similarly, if we want Apache Commons Lang’s HashCodeBuilder class to generate a hashCode() implementation for us, the commons-lang Maven dependency must be included in the pom file:
And hashCode() can be implemented like this:
In general, there’s no universal recipe to stick to when it comes to implementing hashCode(). We highly recommend reading Joshua Bloch’s Effective Java, which provides a list of thorough guidelines for implementing efficient hashing algorithms.
What can be noticed here is that all those implementations utilize number 31 in some form – this is because 31 has a nice property – its multiplication can be replaced by a bitwise shift which is faster than the standard multiplication:
7. Handling Hash Collisions
The intrinsic behavior of hash tables raises up a relevant aspect of these data structures: even with an efficient hashing algorithm, two or more objects might have the same hash code, even if they’re unequal. So, their hash codes would point to the same bucket, even though they would have different hash table keys.
This situation is commonly known as a hash collision, and various methodologies exist for handling it, with each one having their pros and cons. Java’s HashMap uses the separate chaining method for handling collisions:
“When two or more objects point to the same bucket, they’re simply stored in a linked list. In such a case, the hash table is an array of linked lists, and each object with the same hash is appended to the linked list at the bucket index in the array.
In the worst case, several buckets would have a linked list bound to it, and the retrieval of an object in the list would be performed linearly.”
Hash collision methodologies show in a nutshell why it’s so important to implement hashCode() efficiently.
Java 8 brought an interesting enhancement to HashMap implementation – if a bucket size goes beyond the certain threshold, the linked list gets replaced with a tree map. This allows achieving O(logn) look up instead of pessimistic O(n).
8. Creating a Trivial Application
To test the functionality of a standard hashCode() implementation, let’s create a simple Java application that adds some User objects to a HashMap and uses SLF4J for logging a message to the console each time the method is called.
Here’s the sample application’s entry point:
And this is the hashCode() implementation:
The only detail worth stressing here is that each time an object is stored in the hash map and checked with the containsKey() method, hashCode() is invoked and the computed hash code is printed out to the console:
9. Conclusion
It’s clear that producing efficient hashCode() implementations often requires a mixture of a few mathematical concepts, (i.e. prime and arbitrary numbers), logical and basic mathematical operations.
Regardless, it’s entirely possible to implement hashCode() effectively without resorting to these techniques at all, as long as we make sure the hashing algorithm produce different hash codes for unequal objects and is consistent with the implementation of equals().
As always, all the code examples shown in this article are available over on GitHub.
Java object hashcode
Прежде чем пытаться понять методы equals() и hashCode(), необходимо вспомнить несколько фактов: в Java при сравнении ссылочных переменных сравниваются не сами объекты, а ссылки на объекты, и что все объекты унаследованы от класса Object, который содержит реализацию методов equals() и hashCode() по умолчанию.
Для решения задачи сравнения ссылочных переменных существует стандартное решение – метод equals(). Цель данного метода – определить идентичны ли объекты внутри, сравнив их внутреннее содержание. У класса Object есть своя реализация метода equals, которая просто сравнивает ссылки:
Порой такой реализации бывает не достаточно, поэтому, при необходимости чтобы разные объекты с одинаковым содержимым рассматривались как равные, надо переопределить метод equals() учитывая поля, которые должны участвовать в сравнении объектов. Ведь только разработчик класса знает, какие данные важны, что учитывать при сравнении, а что – нет.
У метода equals() есть большой минус – он слишком медленно работает. Для этого был придуман метод hashCode(). Для каждого объекта данный метод возвращает определенное число. Какое именно – это тоже решает разработчик класса, как и в случае с методом equals().
Стандартная реализация метода hashCode() в классе Object:
Вместо того чтобы сравнивать объекты, будем сравнивать их hashCode, и только если hashCode-ы равны, сравнивать объекты посредством equals().
Разработчик, который реализует функцию hashCode(), должен помнить следующее:
1) у двух разных объектов может быть одинаковый hashCode ;
2) у одинаковых объектов (с точки зрения equals()) должен быть одинаковый hashCode ;
3) хеш-коды должны быть выбраны таким образом, чтобы не было большого количества различных объектов с одинаковыми hashCode. Ситуация, когда у различных объектов хеш-коды совпадают называется коллизией.
Важное замечание: при переопределении метода equals(), обязательно нужно переопределить метод hashCode(), с учетом трех вышеописанных правил (Переопределил equals — переопредели и hashCode).
Дело в том, что коллекции в Java перед тем как сравнить объекты с помощью equals всегда ищут/сравнивают их с помощью метода hashCode(). И если у одинаковых объектов будут разные hashCode, то объекты будут считаться разными — до сравнения с помощью equals() просто не дойдет.
Большинство современных IDE помогают переопределять методы equals() и hashCode(). К примеру, в Intellij Idea можно набрать комбинацию клавиш Alt+Ins, и в выпадающем меню Generate выбрать пункт equals and hashCode.
