equals & hashCode metody: dlaczego, gdzie są używane, jak działają

— Teraz omówię równie przydatne  metody equals(Object o) i hashCode() .

Jak zapewne już pamiętasz, w Javie podczas porównywania zmiennych referencyjnych porównywane są nie same obiekty, ale odniesienia do obiektów.

Integer i = new Integer(1);
Integer j = new Integer(1);
System.out.println(i==j);

Integer i = new Integer(1);
Integer j = i;
System.out.println(i==j);

— Tak, pamiętam to.

- Jest też standardowe rozwiązanie tej sytuacji -  metoda równości .

Celem  metody równości  jest określenie, czy obiekty są wewnętrznie identyczne, poprzez porównanie wewnętrznej zawartości obiektów.

- A jak on to robi?

- Wszystko jest podobne do metody toString().

Klasa Object ma własną implementację metody equals, która po prostu porównuje referencje:

public boolean equals(Object obj)
{
return (this == obj);
}

- M-tak. Z tym, z czym walczyli, wpadli na coś.

- Nie zwieszaj nosa. Wszystko tutaj jest również bardzo sprytne.

Ta metoda została stworzona, aby programiści mogli ją zastąpić w swoich klasach. W końcu tylko twórca klasy wie, jakie dane są ważne, co brać pod uwagę przy porównywaniu, a jakie nie.

Możesz podać przykład takiej metody?

- Z pewnością. Powiedzmy, że mamy klasę opisującą ułamki matematyczne, wtedy wyglądałoby to tak (dla jasności przetłumaczę angielskie nazwy na rosyjski):

class Fraction {
  private int numerator;
  private int denominator;
  Fraction(int numerator, int denominator) {
    this.numerator = numerator;
    this.denominator = denominator;
  }
  public boolean equals(Object obj) {
    if (obj == null) return false;

    if (obj.getClass() != this.getClass()) return false;

    Fraction other = (Fraction) obj;
    return this.numerator * other.denominator == this.denominator * other.numerator;
  }
}

— Dla większej przejrzystości użyłem rosyjskich nazw. Można to zrobić tylko w celach edukacyjnych.

Teraz spójrzmy na przykład.

Zastąpiliśmy  metodę equals i teraz   będzie ona miała własną implementację dla obiektów klasy Fraction .

W tej metodzie jest kilka kontroli:

1)  Jeśli obiekt przekazany do porównania ma wartość  null , to obiekty nie są równe. Obiekt, którego  metoda equals została wywołana  , zdecydowanie nie jest  null .

2)  Sprawdź porównanie klas. Jeśli obiekty są różnych klas, to nie będziemy ich porównywać, tylko od razu powiemy, że są to różne obiekty –  zwracamy fałsz .

3)  Od drugiej klasy szkoły wszyscy pamiętają, że ułamek 2/3 równa się ułamkowi 4/6. A jak to sprawdzić?

„Dlatego w trzeciej części metody  equals  konwertujemy przekazany obiekt na typ Fraction i porównujemy ułamki.

- Jest jasne. Gdybyśmy tylko porównywali licznik z licznikiem i mianownik z mianownikiem, to 2/3 nie równałoby się 4/6.

Teraz jasne jest, co miałeś na myśli, mówiąc, że tylko twórca klasy wie, jak ją właściwie porównać.

Tak, ale to dopiero połowa historii. Jest też druga metoda - hashCode()

- Przy metodzie equals wszystko jest jasne, ale po co potrzebny jest  hashCode ()?

-  Metoda hashCode  jest potrzebna do szybkiego porównania.

Metoda  równości  ma dużą wadę - jest zbyt wolna. Powiedzmy, że masz zbiór składający się z miliona elementów i musimy sprawdzić, czy zawiera on określony obiekt, czy nie. Jak to zrobić?

- Możesz przejść przez wszystkie elementy i porównać żądany obiekt z każdym obiektem zestawu. Dopóki nie znajdziemy tego właściwego.

- A jeśli go tam nie ma? Czy robimy milion porównań, aby dowiedzieć się, że tego obiektu tam nie ma? Czy to nie za dużo?

— Tak, nawet ja rozumiem, że jest zbyt wiele porównań. Co, jest inny sposób?

- Tak, do tego  służy hashCode ().

Metoda  hashCode () zwraca określoną liczbę dla każdego obiektu. Która - o tym również decyduje twórca klasy, podobnie jak w przypadku metody equals.

Spójrzmy na sytuację na przykładzie:

Wyobraź sobie, że masz milion 10-cyfrowych liczb. Następnie jako hashCode dla każdej liczby możesz wybrać resztę jej dzielenia przez 100.

Przykład:

— Tak, to zrozumiałe. I co robimy z tym numerem hashCode?

- Zamiast porównywać liczby, porównamy ich  hashCode . Więc szybciej.

I tylko wtedy, gdy  hashCode s są równe, porównaj, używając  equals .

- Tak, jest szybszy. Ale nadal musimy dokonać miliona porównań, tylko z krótszymi liczbami, a dla tych liczb, których hashCode pasuje, wywołanie jest ponownie równe.

— Nie, możesz sobie poradzić z dużo mniejszą liczbą.

Wyobraź sobie, że nasz zestaw przechowuje liczby pogrupowane według hashCode lub posortowane według  hashCode  (co jest równoznaczne z ich pogrupowaniem, ponieważ liczby z tym samym hashCode znajdują się w pobliżu). Wtedy bardzo szybko i łatwo można odrzucić niepotrzebne grupy, wystarczy raz dla każdej grupy sprawdzić czy jej hashCode pasuje do hashCode danego obiektu.

Wyobraź sobie, że jesteś studentem i szukasz przyjaciela, którego znasz z widzenia i o którym wiadomo, że mieszka w akademiku 17. Potem po prostu przechodzisz przez wszystkie akademiki uniwersytetu iw każdym akademiku pytasz „czy to akademik 17?”. Jeśli nie, odrzucasz wszystkich z tego hostelu i przechodzisz do następnego. Jeśli tak, to zaczynasz chodzić po wszystkich pokojach i szukać przyjaciela.

W tym przykładzie numer akademika to 17 - to jest kod hash.

Deweloper, który implementuje funkcję hashCode, musi wiedzieć, co następuje:

A)  dwa różne obiekty mogą mieć ten sam hashCode  (różne osoby mogą mieszkać w tym samym hostelu)

B)  identyczne obiekty  ( pod względem równości )  muszą mieć ten sam hashCode .

C)  kody skrótu muszą być dobrane w taki sposób, aby nie było dużej liczby różnych obiektów z tym samym hashCode.  To zniweczy całą ich przewagę.

A teraz najważniejsze. Jeśli zastąpisz  metodę equals , pamiętaj o zastąpieniu  metody hashCode (), pamiętając o trzech powyższych zasadach.

Rzecz w tym, że  kolekcje w Javie, przed porównaniem obiektów za pomocą równań, zawsze szukają/porównują je za pomocą metody hashCode() . A jeśli identyczne obiekty mają różne hashCody, to obiekty będą uważane za różne - porównanie z równymi po prostu nie dotrze.

W naszym przykładzie ułamka, gdybyśmy wzięli kod hash równy licznikowi, ułamki 2/3 i 4/6 miałyby różne kody hash. Ułamki są takie same, equals mówi, że są takie same, ale hashCode mówi, że są różne. A jeśli porównamy przez hashCode przed porównaniem z równymi, otrzymamy, że obiekty są różne i po prostu nie osiągniemy równych.

Przykład:

- A jak poprawnie zaimplementować hashCode dla ułamka?

- Tutaj musimy pamiętać, że te same ułamki muszą odpowiadać temu samemu hashCode.

Opcja 1 : hashCode jest równa części całkowitej dzielenia.

Dla ułamków 7/5 i 6/5 będzie to 1.

Dla ułamków 4/5 i 3/5 będzie to 0.

Ale ta opcja nie jest odpowiednia do porównywania ułamków, które są oczywiście mniejsze niż 1. Część całkowita (hashCode) zawsze będzie równa 0.

Opcja 2 : hashCode jest równa części całkowitej dzielenia mianownika przez licznik.

Ta opcja jest odpowiednia w przypadku, gdy wartość ułamka jest mniejsza niż 1. Jeśli ułamek jest mniejszy niż 1, to odwrócony ułamek jest większy niż 1. A jeśli odwrócimy wszystkie ułamki, nie wpłynie to na ich porównanie w jakikolwiek sposób.

Ostateczna wersja połączy oba rozwiązania:

public int hashCode() {
return numerator/denominator + denominator/numerator;
}

Sprawdzamy ułamki 2/3 i 4/6. Muszą mieć równy hashCode:

To wszystko.

Dzięki Ellie, to było naprawdę interesujące.