Why do I need to override the equals and hashCode methods in Java?

Недавно я прочитал этот документ Developer Works.

Весь документ посвящен эффективному и корректному определению hashCode() и equals(), однако я не могу понять, зачем нам нужно переопределять эти два метода.

Как я могу принять решение для эффективной реализации этих методов?

Джошуа Блох рассказывает об эффективной Java

Вы должны переопределить hashCode() в каждом классе, который переопределяет equals() . Невыполнение этого требования приведет к нарушению общего контракта для Object.hashCode() , что не позволит вашему классу должным образом функционировать совместно со всеми коллекциями на основе хэша, включая HashMap, HashSet и Hashtable .

Давайте попробуем понять это на примере того, что произойдет, если мы переопределим equals() без переопределения hashCode() и попытаемся использовать Map.

Допустим, у нас есть такой класс, и что два объекта из MyClass равны, если их importantField равно (с hashCode() и equals() генерируется eclipse)

public class MyClass {
    private final String importantField;
    private final String anotherField;

    public MyClass(final String equalField, final String anotherField) {
        this.importantField = equalField;
        this.anotherField = anotherField;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result
                + ((importantField == null) ? 0 : importantField.hashCode());
        return result;
    }

    @Override
    public boolean equals(final Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final MyClass other = (MyClass) obj;
        if (importantField == null) {
            if (other.importantField != null)
                return false;
        } else if (!importantField.equals(other.importantField))
            return false;
        return true;
    }
}

Представьте, что у вас есть это

MyClass first = new MyClass("a","first");
MyClass second = new MyClass("a","second");

Только переопределение equals

Если переопределен только equals, то при вызове myMap.put(first,someValue) first будет хэшироваться в некоторую корзину, а при вызове myMap.put(second,someOtherValue) он будет хэшироваться в какую-то другую корзину (поскольку у них разные hashCode). Итак, хотя они равны, поскольку они не хэшируют в одном и том же сегменте, карта не может это реализовать, и они оба остаются на карте.

Хотя нет необходимости переопределять, equals() если мы переопределяем hashCode(), давайте посмотрим, что произойдет в этом конкретном случае, когда мы знаем, что два объекта из MyClass равны, если их importantField равно, но мы не переопределяем equals().

Только переопределение hashCode

Если вы только переопределяете, hashCode то при вызове myMap.put(first,someValue) он принимает first , вычисляет его hashCode и сохраняет в заданном сегменте. Тогда при вызове myMap.put(second,someOtherValue) он должен заменить first на second согласно документации Map, потому что они равны (в соответствии с бизнес-требованиями).

Но проблема в том, что equals не было переопределено, поэтому, когда map хэширует second и выполняет итерации по корзине, ища, есть ли объект, k такой, что second.equals(k) является true, он не найдет ни одного, как second.equals(first) будетfalse.

Надеюсь, это было понятно

Collections such as HashMap and HashSet use a hashcode value of an object to determine how it should be stored inside a collection, and the hashcode is used again in order to locate the object
in its collection.

Hashing retrieval is a two-step process:

1. Find the right bucket (using hashCode())


2. Search the bucket for the right element (using equals() )

Here is a small example on why we should overrride equals() and hashcode().

Consider an Employee class which has two fields: age and name.

public class Employee {

    String name;
    int age;

    public Employee(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this)
            return true;
        if (!(obj instanceof Employee))
            return false;
        Employee employee = (Employee) obj;
        return employee.getAge() == this.getAge()
                && employee.getName() == this.getName();
    }

    // commented    
    /*  @Override
        public int hashCode() {
            int result=17;
            result=31*result+age;
            result=31*result+(name!=null ? name.hashCode():0);
            return result;
        }
     */
}

Now create a class, insert Employee object into a HashSet and test whether that object is present or not.

public class ClientTest {
    public static void main(String[] args) {
        Employee employee = new Employee("rajeev", 24);
        Employee employee1 = new Employee("rajeev", 25);
        Employee employee2 = new Employee("rajeev", 24);

        HashSet<Employee> employees = new HashSet<Employee>();
        employees.add(employee);
        System.out.println(employees.contains(employee2));
        System.out.println("employee.hashCode():  " + employee.hashCode()
        + "  employee2.hashCode():" + employee2.hashCode());
    }
}

It will print the following:

false
employee.hashCode():  321755204  employee2.hashCode():375890482

Now uncomment hashcode() method , execute the same and the output would be:

true
employee.hashCode():  -938387308  employee2.hashCode():-938387308

Now can you see why if two objects are considered equal, their hashcodes must
also be equal? Otherwise, you'd never be able to find the object since the default
hashcode method in class Object virtually always comes up with a unique number
for each object, even if the equals() method is overridden in such a way that two
or more objects are considered equal. It doesn't matter how equal the objects are if
their hashcodes don't reflect that. So one more time: If two objects are equal, their
hashcodes must be equal as well.

You must override hashCode() in every
class that overrides equals(). Failure
to do so will result in a violation of
the general contract for
Object.hashCode(), which will prevent
your class from functioning properly
in conjunction with all hash-based
collections, including HashMap,
HashSet, and Hashtable.

   from Effective Java, by Joshua Bloch

By defining equals() and hashCode() consistently, you can improve the usability of your classes as keys in hash-based collections. As the API doc for hashCode explains: "This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable."

The best answer to your question about how to implement these methods efficiently is suggesting you to read Chapter 3 of Effective Java.

Why we override equals() method

In Java we can not overload how operators like ==, +=, -+ behave. They are behaving a certain way. So let's focus on the operator == for our case here.

How operator == works.

It checks if 2 references that we compare point to the same instance in memory. Operator == will resolve to true only if those 2 references represent the same instance in memory.

So now let's consider the following example

public class Person {

      private Integer age;
      private String name;
    
      ..getters, setters, constructors
      }

So let's say that in your program you have built 2 Person objects on different places and you wish to compare them.

Person person1 = new Person("Mike", 34);
Person person2 = new Person("Mike", 34);
System.out.println ( person1 == person2 );  --> will print false!

Those 2 objects from business perspective look the same right? For JVM they are not the same. Since they are both created with new keyword those instances are located in different segments in memory. Therefore the operator == will return false

But if we can not override the == operator how can we say to JVM that we want those 2 objects to be treated as same. There comes the .equals() method in play.

You can override equals() to check if some objects have same values for specific fields to be considered equal.

You can select which fields you want to be compared. If we say that 2 Person objects will be the same if and only if they have the same age and same name, then the IDE will create something like the following for automatic generation of equals()

@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);
    }

Давайте вернемся к нашему предыдущему примеру

    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() (она же override) в нашем классе, то предопределенные .equals() from Object class и == оператор будут вести себя точно так же.

По умолчанию equals() метод, который наследуется от Object, проверяет, совпадают ли оба сравниваемых экземпляра в памяти!

Почему мы переопределяем hashCode() метод

Некоторые структуры данных в Java, такие как HashSet, HashMap, хранят свои элементы на основе хэш-функции, которая применяется к этим элементам. Функция хэширования - это hashCode()

Если у нас есть выбор переопределяющего .equals() метода, то у нас также должен быть выбор переопределяющего hashCode() метода. Для этого есть причина.

Реализация по умолчанию hashCode(), которая наследуется от Object, считает все объекты в памяти уникальными!

Давайте вернемся к этим хэш-структурам данных. Для этих структур данных существует правило.

HashSet не может содержать повторяющихся значений, а HashMap не может содержать повторяющихся ключей

HashSet реализован с помощью HashMap за кулисами, где каждое значение HashSet хранится как ключ в HashMap.

Итак, мы должны понять, как работает HashMap.

Проще говоря, HashMap - это собственный массив, содержащий несколько сегментов. У каждого сегмента есть LinkedList . В этом LinkedList хранятся наши ключи. HashMap находит правильный LinkedList для каждого ключа, применяя hashCode() метод, и после этого он перебирает все элементы этого LinkedList и применяет equals() метод к каждому из этих элементов, чтобы проверить, содержится ли этот элемент там уже. Дублирующиеся ключи не допускаются.

Когда мы помещаем что-либо внутрь HashMap , ключ сохраняется в одном из этих LinkedLists . В каком LinkedList этот ключ будет сохранен, показывает результат hashCode() метода для этого ключа. Итак, если key1.hashCode() имеет в результате 4, то этот ключ1 будет сохранен в 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<Person, String> map = new HashMap();
map.put(person1, "1");
map.put(person2, "2");

В классе Person мы не переопределили hashCode метод, но у нас есть переопределенный equals метод. Поскольку по умолчанию hashCode предоставляет разные результаты для разных экземпляров Java person1.hashCode() и person2.hashCode() есть большие шансы получить разные результаты.

Наша карта может заканчиваться этими людьми в разных LinkedLists.

Это противоречит логике 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() {
        return Objects.hash(name, age);
    }

      }

Теперь давайте попробуем еще раз сохранить эти ключи в нашей HashMap

Map<Person, String> map = new HashMap();
map.put(person1, "1");
map.put(person2, "2");

person1.hashCode() и person2.hashCode() определенно будет таким же. Допустим, это 0.

HashMap перейдет в корзину 0, и в этом LinkedList сохранит person1 как ключ со значением "1". Во-вторых, put HashMap достаточно умен, и когда он снова переходит в корзину 0, чтобы сохранить ключ person2 со значением "2", он увидит, что там уже существует другой ключ equal. Таким образом, он перезапишет предыдущий ключ. Итак, в итоге в нашей HashMap будет существовать только ключ person2.

Теперь мы согласны с правилом Hash Map, которое гласит, что несколько равных ключей недопустимы!