Я недавно начал заниматься программированием, и в этой области для меня много нового. Данная статья рассчитана на начинающих java-программистов, и, надеюсь, поможет в освоении излюбленной темы для собеседований “hashCode
и equals
”.
Хочу сразу предостеречь, что я не являюсь экспертом в данной теме и могу что-то не так понимать, поэтому, если вы нашли ошибку или неточность — свяжитесь со мной.
Что такое хеш-код?
Если очень просто, то хеш-код — это число. На самом деле просто, не так ли? Если более точно, то это битовая строка фиксированной длины, полученная из массива произвольной длины (википедия).
Пример №1
Выполним следующий код:
public class Main {
public static void main(String[] args) {
Object object = new Object();
int hCode;
hCode = object.hashCode();
System.out.println(hCode);
}
}
В результате выполнения программы в консоль выведется целое 10-ти значное число. Это число и есть наша битовая строка фиксированной длины. В java она представлена в виде числа примитивного типа int
, который равен 4-м байтам, и может помещать числа от -2 147 483 648 до 2 147 483 647. На данном этапе важно понимать, что хеш-код это число, у которого есть свой предел, который для java ограничен примитивным целочисленным типом int.
Вторая часть объяснения гласит:
полученная из массива произвольной длины.
Под массивом произвольной длины мы будем понимать объект. В 1 примере в качестве массива произвольной длины у нас выступает объект типа Object
.
В итоге, в терминах Java, хеш-код — это целочисленный результат работы метода, которому в качестве входного параметра передан объект.
Этот метод реализован таким образом, что для одного и того-же входного объекта, хеш-код всегда будет одинаковым. Следует понимать, что множество возможных хеш-кодов ограничено примитивным типом int
, а множество объектов ограничено только нашей фантазией. Отсюда следует утверждение: “Множество объектов мощнее множества хеш-кодов”. Из-за этого ограничения, вполне возможна ситуация, что хеш-коды разных объектов могут совпасть.
Здесь главное понять, что:
- Если хеш-коды разные, то и входные объекты гарантированно разные.
- Если хеш-коды равны, то входные объекты не всегда равны.
Ситуация, когда у разных объектов одинаковые хеш-коды называется — коллизией. Вероятность возникновения коллизии зависит от используемого алгоритма генерации хеш-кода.
Подведём итог:
Сперва, что-бы избежать путаницы, определимся с терминологией. Одинаковые объекты — это объекты одного класса с одинаковым содержимым полей.
- для одного и того-же объекта, хеш-код всегда будет одинаковым;
- если объекты одинаковые, то и хеш-коды одинаковые (но не наоборот, см. правило 3).
- если хеш-коды равны, то входные объекты не всегда равны (коллизия);
- если хеш-коды разные, то и объекты гарантированно разные;
Понятие эквивалентности. Метод equals()
Начнем с того, что в java, каждый вызов оператора new
порождает новый объект в памяти. Для иллюстрации создадим какой-нибудь класс, пускай он будет называться “BlackBox”.
Пример №2
Выполним следующий код:
public class BlackBox {
int a;
int b;
BlackBox(int varA, int varB){
a = varA;
b = varB;
}
}
Создадим класс для демонстрации BlackBox
.
public class DemoBlackBox {
public static void main(String[] args) {
BlackBox object1 = new BlackBox(5, 10);
BlackBox object2 = new BlackBox(5, 10);
}
}
Во втором примере, в памяти создастся два объекта.
Но, как вы уже обратили внимание, содержимое этих объектов одинаково, то есть эквивалентно. Для проверки эквивалентности в классе Object
существует метод equals()
, который сравнивает содержимое объектов и выводит значение типа boolean true
, если содержимое эквивалентно, и false
— если нет.
object1.equals(object2);// должно быть true, поскольку содержимое объектов эквивалентно
Эквивалентность и хеш-код тесно связанны между собой, поскольку хеш-код вычисляется на основании содержимого объекта (значения полей) и если у двух объектов одного и того же класса содержимое одинаковое, то и хеш-коды должны быть одинаковые (см. правило 2).
Иными словами:
object1.equals(object2)// должно быть true
object1.hashCode() == object2.hashCode()// должно быть true
Я написал “должно быть”, потому что если вы выполните предыдущий пример, то на самом деле результатом выполнения всех операций будет false
. Для пояснения причин, заглянем в исходные коды класса Object
.
Класс Object
Как известно, все java-классы наследуются от класса Object
. В этом классе уже определены методы hashCode()
и equals()
.
Определяя свой класс, вы автоматически наследуете все методы класса Object
. И в ситуации, когда в вашем классе не переопределены ()
hashCode()
и equals()
, то используется их реализация из Object
.
Рассмотрим исходный код метода equals()
в классе Object
.
public boolean equals(Object obj) {
return (this == obj);
}
При сравнение объектов, операция “==
” вернет true
лишь в одном случае — когда ссылки указывают на один и тот-же объект. В данном случае не учитывается содержимое полей.
Выполнив приведённый ниже код, equals
вернет true
.
public class DemoBlackBox {
public static void main(String[] args) {
BlackBox object3 = new BlackBox(5, 10);
BlackBox object4 = object3;// Переменная object4 ссылается на
//тот-же объект что и переменная object3
object3.equals(object4)//true
}
}
Теперь понято, почему Object.equals()
работает не так как нужно, ведь он сравнивает ссылки, а не содержимое объектов.
Далее на очереди hashCode()
, который тоже работает не так как полагается.
Заглянем в исходный код метода hashCode()
в классе Object
:
public native int hashCode();
Вот собственно и вся реализация. Ключевое слово 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 приобретает вид:
public class BlackBox {
int a;
int b;
BlackBox(int varA, int varB){
a = varA;
b = varB;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + varA;
result = prime * result + varB;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
BlackBox other = (BlackBox) obj;
if (varA != other.varA)
return false;
if (varB != other.varB)
return false;
return true;
}
}
Теперь методы hashCode()
и equals()
работают корректно и учитывают содержимое полей объекта:
object1.equals(object2);//true
object1.hashCode() == object2.hashCode();//true
Кому интересно переопределение в ручную, можно почитать Effective Java — Joshua Bloch, chapter 3, item 8,9.
Итоги
Создавая пользовательский класс, нужно переопределять методы hashCode()
и equals()
, что бы они корректно работали и учитывали данные объекта. Кроме того, если оставить реализацию из Object
, то при использовании java.util.HashMap
возникнут проблемы, поскольку HashMap активно используют hashCode()
и equals()
в своей работе, но про это хорошо написано у tarzan82 в посте Структуры данных в картинках.HashMap.
Ссылки:
- Исходный код класса java.lang.Object
- Откуда растут ноги у hashCode
- Как сгенерировать hashCode в Java
- Эффективное и безошибочное объявление методов hashCode() и equals()
- Сравнение объектов: теория
- Сравнение объектов: практика
Автор: MaximPedich