Почему при переопределении Equals советуют также переопределять GetHashCode
Дело в том, что любой объект в .NET можно положить в хеш-таблицу.
Допустим теперь, что у вас есть класс X , в котором переопределён метод Equals , но не переопределён GetHashCode . Что будет в этом случае?
Пусть у вас есть два объекта x1 и x2 типа X , которые совпадают согласно функции Equals . Поскольку вы не переопределили GetHashCode , то скорее всего их хэшкоды будут разными.
Если вы положите в HashSet значение x1 , а потом будете искать там x2 , то при этом это значение не будет найдено, несмотря на то, что x1 и x2 у вас равны. Это произойдёт потому, что при поиске в HashSet сначала ищется hash bucket, соответствующий хэшкоду, и лишь в нём ищется сам элемент — это базовый принцип работы хэш-таблицы, обеспечивающий её эффективность. Таким образом, элементы класса X нельзя будет нормально хранить в хэш-таблицах.
То же относится и к Dictionary , который точно так же основан на хэш-таблице и пользуется методом GetHashCode .
По поводу правильного определения GetHashCode , совет с MSDN не очень хорош. Дело в том, что если у объекта есть два поля, то часто это маленькие числа, которые также часто бывают равны. Поэтому при таком определении будет слишком мало различных значений хэшкода, и много экземпляров X будут попадать в тот же самый hash bucket (что снижает эффективность хэш-таблиц).
Рекомендованный метод, судя по всему, такой (обновлено в 2023):
public override int GetHashCode() => HashCode.Combine(x, y); (подсмотрено здесь, будет работать не только для целочисленных полей) или, более изящно,
public override int GetHashCode() => (x, y).GetHashCode(); (подсмотрено здесь, в текущей реализации «под капотом» всё равно будет вызван метод HashCode.Combine ).
Для старых версий .NET, где не было удобного метода HashCode.Combine , можно комбинировать хэшкоды вручную:
public override int GetHashCode() < var hash = 19; // избегаем хэш-коллизий, используем (небольшое) простое число hash = hash * 37 + x.GetHashCode(); hash = hash * 37 + y.GetHashCode(); // обобщается на произвольное число полей return hash; >(19 и 37 — небольшие разные простые числа) Здесь типы полей неважны, т. к. на каждом из них берётся хэшкод.
Чего делать не стоит, так это использовать для хэшкода тяжеловесные методы наподобие вызова MD5: вычисление хэшкода для объектов в хэш-таблице может вызываться очень часто, и поэтому обязано быть быстрым.
Обязательно придерживайтесь правила: если объекты равны по Equals , у них обязаны быть одинаковые хэшкоды.
Ещё одно важное замечание: если вы кладёте в HashSet элемент, вы не должны менять его состояние (значения полей) таким образом, чтобы его хэшкод изменился! Лучше всего, разумеется, вовсе не менять его. Иначе при поиске этого элемента он просто не будет найден.
Дополнительное чтение по теме:
- Хешкод, переопределение метода GetHashCode
- What is the best algorithm for an overridden System.Object.GetHashCode?
- Why is it important to override GetHashCode when Equals method is overridden?
- Eric Lippert: Guidelines and rules for GetHashCode (перевод на русский: Правила и рекомендации по переопределению GetHashCode)
- Обзор альтернативных методов хэширования
Методы .equals и .hashcode в Java. Отличия реализации по умолчанию от реализации на практике
Сразу же скажу, что статья во многом опирается базовые понятия алгебры, которые к великому счастью легко и быстро осознаются при помощи всего-лишь метода внимательного разглядывания. Поехали.
В Java так устроено, что любой класс, который вы определяете, наследуется от класса Object. Таким образом класс Object является суперклассом любого класса в любой программе.
Это означает, что абсолютно любой класс содержит методы, которые определены в классе Object. Методы .equals() и .hashcode() — одни из них.
Прежде всего я должен описать главные правила для любых реализаций этих двух методов, которые нужно обязательно соблюдать, запомнить как аксиому:
1). Если x.equals(y) == true, то обязательно hashcode(x) == hashcode(y)
2) Если hashcode(x) == hashcode(y), то не обязательно x.equals(y) == true
Метод .equals()
Отношение эквивалентности (алгебра)
Прежде чем поговорить о методе .equals, я бы хотел рассказать, что такое отношение эквивалентности с точки зрения алгебры (пока-что забудьте про программирование).
Отношение эквивалентности — это бинарное (бинарное — значит между двумя) отношение, которое является:
Таким образом, если на множестве определено отношение эквивалентности, множество можно разделить на подмножества — классы эквивалентности.
Каждый класс эквивалентности содержит внутри себя только те элементы, которые эквиваленты (более формально — находятся в отношении эквивалентности) между собой.
Реализация .equals() по умолчанию
Метод .equals() в классе Object реализован примерно следующим образом:
public boolean equals(Object x)
Фактически он делает следующее: Он принимает в качестве аргумента ссылочную переменную и проверяет, ссылается ли они на тот же объект (ту же область памяти, если быть точнее), что и объект, к которому мы применили метод .equals().
Таким образом, стандартная реализация .equals() выстраивает отношение эквивалентности, которое можно описать так: две ссылки эквивалентны, если они ссылаются на одну и ту же область памяти.
Такая реализация не противоречит математической идеологии, описанной выше. Однако на практике метод .equals() часто переопределяют в подклассах.
Как и зачем переопределяют метод .equals()?
Очевидно, гораздо более применимой будет возможность сравнивать объекты по какому-нибудь другому критерию. Часто метод .equals() переопределяют так, чтобы он сравнивал объекты по значениям их полей.
К примеру, если классы двух объектов, на которые указывают ссылки, совпадают и все значения их полей совпадают, то эти два объекта эквивалентны между собой. Легко проследить, что такое определение не противоречит математической идеологии.
Конкретную кодовую реализацию я приводить не буду, потому что она не так важна, как сама идея
Это и другие возможные переопределения метода .equals() мало того, что расширяют круг наших возможностей, так ещё и не лишают старых, ведь мы по прежнему имеем возможность проверять, ссылаются ли две ссылки на одну область памяти, используя операнд ==, вместо прежнего .equals()
return(ob1 == ob2);Метод .hashcode()
Сюръекция (алгебра)
Сюръекция — сопоставление элементам множества X элементов второго множества Y, при котором для любого элемента из Y есть хотя-бы один сопоставленный элемент из X.
Если немного более подробно разобрать это определение, то мы увидим следующее:
- Даже несколько элементов из X могут быть сопоставлены одному и тому же элементу из Y (это называется коллизией).
- Возможно есть такое элемент из X, и даже возможно не один, что он не сопоставлен никакому элементу из Y. (см. рисунок, всё интуитивно)
Что происходит в java?
Метод .hashcode() как-раз осуществляет сюръекцию. Множеством X выступает множество всевозможных объектов которые мы можем создать, множеством Y выступает область значений типа данных int. Метод .hashcode() вычисляет каким-то скрытым от нас способом целое число, опираясь на объект, к которому применяется.
Единственное отличие метода .hashcode() от сюръекции в том, что любой объект может быть обработан методом .hashcode()
Реализация .hashcode() по умолчанию?
Насколько я понял, точно так никто в этом и не разобрался. Есть много версий:
- Значение .hashcode() — это область памяти, где лежит объект
- Значение .hashcode() — это число, создаваемое генератором случайных чисел в какой-то момент
- Сама функция написана не на Java а вообще на C.
И многие другие. В общем каким-то образом она всё же устроена, но самое главное в том, что стандартная реализация .hashcode() со стандартной реализацией .equals() подчиняются правилу, приведённому в самом начале статьи
Как и зачем переопределяют метод .hashcode()?
Основной причиной для изменения метода .hashcode() является то, что желают изменить .equals(), однако смена стандартной реализации .equals() приводит к нарушению правила из начала статьи
Второстепенной причиной для изменения метода .hashcode() является то, что желают изменить вероятность коллизии (эта причина встречается реже)
Конец 🙂
Переопределение метода equals() в Java
Методы equals() и hashCode() помогают сравнивать объекты. Без них пришлось бы использовать много if-ов, чтобы сравнить по отдельности поля каждого объекта. А благодаря equals() и hashCode() вы делаете код проще для чтения и понимания — никаких лишних конструкций.
Метод equals() нужен для того, чтобы сравнивать между собой объекты.В стандартной реализации он берёт один объект и сравнивает его с текущим объектом. Если ссылки на них равны, возвращается True, если не равны — возвращается False.
В свою очередь, hashCode() генерирует целочисленный код экземпляра класса. Если вы делаете переопределение equals() в Java, то необходимо переопределять hashCode() , иначе вы можете столкнуться с ошибками.
Стандартная реализация equals()
В стандартной реализации equals() выглядит так:
public boolean equals(Object obj) return (this == obj);
>Посмотрим на практике, как это работает. В следующем примере представлен класс User с двумя переменными nickname и rating. Мы создаём два экземпляра, передаём в них одинаковые значения и сравниваем их:
class User private String nickname;
private int rating;
User(String nickname, int rating) this.nickname = nickname;
this.rating = rating;
>
>
public class Difference public static void main(String[] args) User user1 = new User("Andrew", 250);
User user2 = new User("Andrew", 250);
//Сравниваем два объекта и выводим результат
boolean bool = user1.equals(user2);
System.out.println(bool);
>
>По умолчанию метод equals() возвращает True, только если ссылки двух объектов равны. Поэтому программа из примера выше вернёт False — фактически ссылки у них разные.
Проблема в том, что при такой реализации мы не решаем реальную задачу. Допустим, бизнес-логика приложения требует, чтобы выполнялась проверка состояния объектов. Визуально понятно, что поля совпадают. Это один и тот же пользователь с одним и тем же рейтингом. Однако стандартное поведение приводит к тому, что результат получается противоположным.
Исправить этот недостаток помогает переопределение метода equals() в Java . Суть этого механизма в изменении поведения метода equals() родительского класса в дочернем классе. Проще разобраться на примере.
Переопределение equals()
Переопределим equals() и напишем собственную логику сравнения состояний:
class Complex private double number1, number2;
public Complex(double number1, double number2) this.number1 = number1;
this.number2 = number2;
>
@Override
public boolean equals(Object obj) if (obj == this) return true;
>
if (obj.getClass() != this.getClass()) return false;
>
Complex c = (Complex) obj;
return Double.compare(number1, c.number1) == 0
&& Double.compare(number2, c.number2) == 0;
>
>
public class Main
public static void main(String[] args) Complex example1 = new Complex(20, 15);
Complex example2 = new Complex(20, 15);
if (example1.equals(example2)) System.out.println("Equal ");
> else System.out.println("Not Equal ");
>
>
>Output:
Equal Аннотация @Override говорит компилятору, что нужно переопределить метод в процессе компиляции. Стоит учесть, что без аннотации переопределение метода также будет работать, если компилятор найдет в родительском классе метод с такой же сигнатурой. Однако наличие аннотации полезно для контроля этого действия и читаемости кода. Если же мы повесим аннотацию над методом, которого нет в родительском классе, то получим ошибку при сборке приложения.
Сам метод теперь состоит из трёх частей. Рассмотрим их подробнее.
Если объект сравнивается с самим собой, должно вернуться True:
if (obj == this) return true;
>Смотрим, относится ли объект к классу Complex. Возвращаем False, если это не так:
if (obj.getClass() != this.getClass()) return false;
>Приводим тип экземпляра к Complex, сравниваем элементы и возвращаем соответствие:
Complex c = (Complex) obj;
return Double.compare(number1, c.number1) == 0
&& Double.compare(number2, c.number2) == 0;
>Правила переопределения
При изменении работы метода нужно придерживаться правил переопределения equals() в Java:
- Если объект сравнивается сам с собой, должно возвращаться True.
- Если объект сравнивается с null, должно возвращаться False.
- При равенстве двух объектов Obj1.equals(Obj2) и Obj2.equals(Obj1) должны возвращать True.
- При сравнении трёх объектов Obj1.equals(Obj2) и Obj2.equals(Obj3) возвращают True, то и Obj1.equals(Obj3) должно вернуть True.
- При многократных вызовах метода должен возвращаться один и тот же результат, пока не изменятся свойства объекта, используемые в вашей реализации.
Существуют также некоторые ограничения на переопределение equals(). Например, переопределять метод нет смысла, если каждый объект уникален. Кроме того, это относится к классам, которые предназначены не для работы с данными, а для предоставления определённого поведения.
Ещё одна ситуация, когда метод не переопределяют, — использование класса, экземпляры которого сравнивать бессмысленно. Наглядный пример — java.util.Random. Суть этого класса в том, чтобы возвращать случайные последовательности чисел. Экземпляры этого класса не должны быть равными, иначе в них нет смысла.
Переопределение hashCode()
Когда вы меняете логику работы equals(), настоятельно рекомендуется также переопределять логику работы hashCode(). Если вы не сделаете это, у одинаковых объектов могут оказаться разные хэш-коды. По этой причине, например, коллекции на основе хэшей не будут работать так, как от них ожидают.
Благодаря тому, что hashCode() генерирует уникальный идентификатор, сравнивать состояния объектов становится проще. Если идентификаторы отличаются, equals() можно вообще не запускать. Если идентификаторы одинаковые, нужно выполнить equals() и проверить свойства объектов.
Плохой пример переопределения hashCode() — возврат константы. Например, вот так:
@Override
public int hashCode() return 35;
>На практике это создаёт огромные проблемы. Хэш-значение не будет меняться при изменении состояния. Допустим, вы измените значения полей. Хэш-код останется прежним.
В определении хэш-значения должны принимать участие только те поля, которые используются в equals(). Кроме того, нужна база — основу для вычисления хэша. Обычно базой делают число 31, но вы можете установить любое другое значение.
- Переменной result присваивается ненулевое значение — например, число 31.
- Для каждого значимого поля экземпляра вычисляется хэш. Правила вычислений отличаются в зависимости от типа поля:
- для boolean — (f ? 1 : 0);
- для byte, char, short или int — (int) f;
- для long — (int)(f ^ (f >>> 32));
- для float — Float.floatToIntBits(f);
- для double — Double.doubleToLongBits(f), а затем как с long;
- для полей, которые представляют собой ссылку на другой объект — рекурсивный вызов hashCode();
- для null — вернуть 0;
- для массива — обработайте так, будто каждый элемент представляет собой отдельное поле объекта.
После обработки каждого поля вы должны прибавлять полученный результат к базе и предыдущим результатам. После прохождения по всем полям верните итоговый хэш-код.
Допустим, вы хотите переопределить hashCode() для класса Person:
public class Person private int age;
private int number;
private double salary;
private String name;
private CarKey carKey;
public Person(int age, int number, String name, double salary, CarKey carKey) this.age = age;
this.number = number;
this.name = name;
this.salary = salary;
this.carKey = carKey;
>
@Override
public int hashCode() int result = 31;
result = result * 17 + age;
result = result * 17 + number;
long lnum = Double.doubleToLongBits(salary);
result = result * 17 + (int)(lnum ^ (lnum >>> 32));
result = result * 17 + name.hashCode();
result = result * 17 + carKey.hashCode();
return result;
>
// Здесь уже можно переопределить equals()
// …
>Начиная с Java 7 доступы вспомогательные методы для создания собственной реализации hashCode(). Например, для того же класса Person достаточно выполнить:
@Override
public int hashCode() return Objects.hash(age, number, salary, name, carKey);
>Строгие правила переопределения разработаны и для hashCode():
- Многократные вызовы hashCode() возвращают одно и то же целочисленное значение, пока не изменится одно из свойств, использованных в вашей версии equals(). Однако после остановки и запуска приложения хэш-код может изменяться.
- Если экземпляры класса одинаковы по методу equals(), то их хэш-коды тоже должны быть одинаковыми.
- Если экземпляры не одинаковы по equals(), метод hashCode() не обязательно вернёт отличающиеся значения. Однако возврат отличающихся значений для разных объектов — это хорошая практика, которая положительно влияет на производительность хэш-таблиц.
Придерживайтесь этих правил при написании своих версий equals() и hashCode(). Помните, что методы нужно переопределять вместе, иначе вы можете столкнуться с тем, что экземпляры с одинаковым состоянием будут определены как разные.
Что запомнить
- Метод equals() можно переопределить так, чтобы он сравнивал значения полей, сопоставляя между собой состояния экземпляров.
- Если сравнение двух хэш-кодов даёт False, то и результат выполнения equals() должен возвращать False.
- Если вы создаёте собственную реализацию equals(), то измените реализацию hashCode().
- Если при использовании коллекций, использующих хэш-таблицы, не переопределить оба метода, то в коллекции могут быть повторяющиеся элементы.
Кофе-брейк #168. Зачем переопределять методы equals и hashcode в Java?
Зачем переопределять методы equals и hashcode в Java?
Источник: Medium Содержание этой статьи посвящено двум тесно связанным между собой методам: equals() и hashcode() . Вы узнаете, как они взаимодействуют друг с другом и как их правильно переопределять.
Почему мы переопределяем метод equals()?
В Java мы не можем перегружать поведение таких операторов, как == , += , -+ . Они работают согласно заданному процессу. Для примера рассмотрим работу оператора == .
Как работает оператор ==?
Он проверяет, указывают ли две сравниваемые ссылки на один и тот же экземпляр в памяти. Оператор == будет иметь значение true только в том случае, если эти две ссылки представляют один и тот же экземпляр в памяти. Давайте взглянем на пример кода:
public class Person
Допустим, в вашей программе вы создали два объекта Person в разных местах и хотите их сравнить.
Person person1 = new Person("Mike", 34); Person person2 = new Person("Mike", 34); System.out.println( person1 == person2 ); --> will print false!С точки зрения бизнеса эти два объекта выглядят одинаково, верно? Но для JVM они не совпадают. Поскольку они оба созданы с помощью ключевого слова new , эти экземпляры расположены в разных сегментах памяти. Поэтому оператор == вернет false. Но если мы не можем переопределить оператор == , то как нам сказать JVM, что мы хотим, чтобы эти два объекта обрабатывались одинаково? Здесь в игру вступает метод .equals() . Вы можете переопределить equals() , чтобы проверить, имеют ли некоторые объекты одинаковые значения для определенных полей, чтобы считать их равными. Вы можете выбрать, какие поля нужно сравнить. Если мы говорим, что два объекта Person будут одинаковыми только тогда, когда они имеют одинаковый возраст и одно и то же имя, то в этом случае IDE сгенерирует для автоматического создания equals() что-то такое:
@Override public boolean equals(Object o)
Вернемся к нашему предыдущему примеру.
Person person1 = new Person("Mike", 34); Person person2 = new Person("Mike", 34); System.out.println ( person1 == person2 ); --> will print false! System.out.println ( person1.equals(person2) ); --> will print true!Да, мы не можем перегрузить оператор == для сравнения объектов так, как мы хотим, но Java дает нам другой способ — метод equals() , который мы можем переопределить по своему усмотрению. Имейте в виду, что если мы не предоставим нашу пользовательскую версию .equals() (также известную как переопределение) в нашем классе, то предопределенный .equals() из класса Object и оператор == будут вести себя одинаково. Метод по умолчанию equals() , унаследованный от Object , будет проверять, совпадают ли оба сравниваемых экземпляра в памяти!
Почему мы переопределяем метод hashCode()?
Некоторые структуры данных в Java, такие как HashSet и HashMap , хранят свои элементы на основе хеш-функции, которая применяется к этим элементам. Хеш-функцией является hashCode() . Если у нас есть выбор в переопределении метода .equals() , то у нас также должен быть выбор в переопределении метода hashCode() . Для этого есть причина. Ведь реализация по умолчанию hashCode() , унаследованная от Object , считает все объекты в памяти уникальными! Но вернемся к этим структурам хеш-данных. Для этих структур данных существует правило. HashSet не может содержать повторяющиеся значения, а HashMap не может содержать повторяющиеся ключи. HashSet реализован с помощью HashMap таким образом, что каждое значение HashSet хранится как ключ в HashMap . Как работает HashMap ? HashMap — это собственный массив с несколькими сегментами. Каждый сегмент имеет связанный список ( linkedList ). В этом связанном списке хранятся наши ключи. HashMap находит правильный linkedList для каждого ключа, применяя метод hashCode() , а затем выполняет итерацию по всем элементам этого linkedList и применяет метод equals() к каждому из этих элементов, чтобы проверить, содержится ли там этот элемент. Дубликаты ключей не допускаются. Когда мы помещаем что-то внутрь HashMap , то ключ сохраняется в одном из этих связанных списков. В каком связанном списке будет храниться этот ключ, показывает результат метода hashCode() для этого ключа. То есть, если key1.hashCode() в результате получается 4, то этот key1 будет храниться в 4-м сегменте массива в существующем там LinkedList . По умолчанию метод hashCode() возвращает разные результаты для каждого экземпляра. Если у нас есть значение по умолчанию equals() , которое ведет себя как == , рассматривая все экземпляры в памяти как разные объекты, то проблем не будет. Как вы помните, в нашем предыдущем примере было сказано, что мы хотим, чтобы экземпляры Person считались равными, если их возраст и имена совпадают.
Person person1 = new Person("Mike", 34); Person person2 = new Person("Mike", 34); System.out.println ( person1.equals(person2) ); --> will print true!Теперь давайте создадим карту (map) для хранения этих экземпляров в виде ключей с определенной строкой в качестве парного значения.
Map map = new HashMap(); map.put(person1, "1"); map.put(person2, "2");
В классе Person мы не переопределили метод hashCode , но у нас есть переопределенный метод equals . Поскольку значение по умолчанию hashCode дает разные результаты для разных Java-экземпляров person1.hashCode() и person2.hashCode() , есть большие шансы получить разные результаты. Наша карта может заканчиваться разными person в разных связанных списках. Это противоречит логике HashMap . Ведь HashMap не может иметь несколько одинаковых ключей! Дело в том, что по умолчанию hashCode() , унаследованного от класса Object , недостаточно. Даже после того, как мы переопределили метод equals() класса Person . Вот почему мы должны переопределить метод hashCode() после того, как мы переопределили метод equals . Теперь давайте это исправим. Нам нужно переопределить наш метод hashCode() , чтобы он учитывал те же поля, что и equals() , а именно age и name .
public class Person < private Integer age; private String name; ..getters, setters, constructors @Override public boolean equals(Object o) < if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Person person = (Person) o; return age == person.age && name.equals(person.name); >@Override public int hashCode()
В методе hashCode() мы использовали простое значение (вы можете использовать любые другие значения). Тем не менее, предлагается использовать простые числа, чтобы создавать меньше проблем. Давайте попробуем еще раз сохранить эти ключи в нашем HashMap :
Map map = new HashMap(); map.put(person1, "1"); map.put(person2, "2");
person1.hashCode() и person2.hashCode() будут одинаковы. Допустим, равны 0. HashMap перейдет в сегмент 0 и в нем LinkedList сохранит person1 как ключ со значением “1”. Во втором случае, когда HashMap снова перейдет к корзине 0, чтобы сохранить ключ person2 со значением “2”, он увидит, что там уже существует другой равный ему ключ. Таким образом он перезапишет предыдущий ключ. И в нашем HashMap будет существовать только ключ person2 . Так мы узнали, как работает правило HashMap , которое гласит, что нельзя использовать несколько одинаковых ключей! Однако имейте в виду, что неравные экземпляры могут иметь одинаковый хэшкод, а одинаковые экземпляры должны возвращать одинаковый хэшкод.