Разбираемся в hashCode() и equals()

Я недавно начал заниматься программированием, и в этой области для меня много нового. Данная статья рассчитана на начинающих 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, а множество объектов ограничено только нашей фантазией. Отсюда следует утверждение: “Множество объектов мощнее множества хеш-кодов”. Из-за этого ограничения, вполне возможна ситуация, что хеш-коды разных объектов могут совпасть.

Здесь главное понять, что:

• Если хеш-коды разные, то и входные объекты гарантированно разные.
• Если хеш-коды равны, то входные объекты не всегда равны.

Ситуация, когда у разных объектов одинаковые хеш-коды называется — коллизией. Вероятность возникновения коллизии зависит от используемого алгоритма генерации хеш-кода.

Подведём итог:

Сперва, что-бы избежать путаницы, определимся с терминологией. Одинаковые объекты — это объекты одного класса с одинаковым содержимым полей.

1. для одного и того-же объекта, хеш-код всегда будет одинаковым;
2. если объекты одинаковые, то и хеш-коды одинаковые (но не наоборот, см. правило 3).
3. если хеш-коды равны, то входные объекты не всегда равны (коллизия);
4. если хеш-коды разные, то и объекты гарантированно разные;

Понятие эквивалентности. Метод 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. И в ситуации, когда в вашем классе не переопределены (@overriding) 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()
• Сравнение объектов: теория
• Сравнение объектов: практика