Разбираемся с 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()
• Сравнение объектов: теория
• Сравнение объектов: практика

Автор: MaximPedich

Источник