Equals i hashCode w Javie

Equals i hashCode to dwie metody, które zna (a przynajmniej powinien znać) każdy programista Javy. Na rozmowach kwalifikacyjnych mogą pojawić się pytania takie jak: Do czego służą metody equals i hashCode? Dlaczego są one tak ważne w kontekście kolekcji? O czym mówi kontrakt equals/hashCode? Czas aby nieco uporządkować wiedzę na ten temat, a może też nauczyć się czegoś zupełnie nowego.

Na czym polega problem z equals i hashCode?

Można by wręcz rzec: o co tyle krzyku? Otóż sprawa jest bardzo prosta. Jeśli używamy w projekcie kolekcji, które korzystają z hash tables, np. HashSet lub HashMap i nie nadpiszemy metod equals oraz hashCode w odpowiedni sposób, to mamy potencjalny problem.

Obydwie te metody są zadeklarowane i zdefiniowane w klasie Object:

public native int hashCode();

W przypadku metody hashCode słowo kluczowe native oznacza, że mamy do czynienia z natywną funkcją wirtualnej maszyny Javy. W jej starszych wersjach domyślny hashCode zwracał inną wartość dla każdego obiektu, bazując na jego miejscu w pamięci. Począwszy od Javy 8 natomiast,  wykorzystywany jest algorytm XOR-Shift używający generatora liczb pseudolosowych.

Zatem jeśli nie nadpiszemy metody hashCode , to  z góry powinniśmy założyć, że każdy obiekt będzie miał inny hashCode . Przynajmniej w teorii, ponieważ mamy tu do czynienia ze skończoną liczbą… liczb, bo korzystamy z zakresu wartości integer.

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

Natomiast jeśli chodzi o metodę equals, to jak widać w snippecie powyżej, domyślnie wykorzystywane jest porównanie referencji do obiektu, nie biorąc pod uwagę poszczególnych wartości pól.

I tu pojawia się problem. Aby go jednak zgłębić, powinniśmy najpierw omówić dwa kluczowe pojęcia: object identity oraz object equality.

---

Jeśli chcesz prześledzić zmiany krok po kroku w formie wideo, to zapraszamy na nasz kanał na YouTube.

---

Object Identity

Object identity mówi o tym, że jeśli mamy dwie referencje danego typu, które wskazują na ten sam obiekt w pamięci, to wówczas porównanie tychże referencji za pomocą podwójnego znaku równości zawsze zwróci nam wartość true.

Za przykład niech posłuży nam prosta klasa typu Cat:

public class Cat {

    private String name;
    private int age;

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

Wówczas możemy napisać:

Cat cat1 = new Cat("Susie", 3);
Cat cat2 = cat1;

System.out.println(cat1 == cat2);

i w wyniku otrzymamy wypisaną na ekran wartość true.

Oczywiście ma to sens, ponieważ w rzeczywistości nie istnieją dwie instancje obiektu typu Cat. W pamięci zostało zaalokowane miejsce na tylko jeden obiekt. W związku z tym referencje wskazujące na ten obiekt są sobie równe.

Object equality

To zdecydowanie ciekawsza część porównywania obiektów. Co tak naprawdę oznacza, że dwa obiekty są sobie równe? Otóż wszystko zależy od nas. To my tutaj decydujemy co sprawia, że dwa obiekty są sobie równe. Czy na przykład w przypadku dwóch osób wystarczy, że będą miały takie samo imię i nazwisko? A może i ten sam wiek? I numer PESEL? Numer buta? Wiecie o co chodzi…

W przypadku jakiegoś scenariusza biznesowego, zwłaszcza w środowisku korporacyjnym (np. fabryka samochodów) powinniśmy taką informację otrzymać od odpowiednio kompetentnej osoby.

A kiedy już nareszcie będziemy gotowi, możemy przystąpić do nadpisania metody equals.

Equals – kontrakt

To zbiór zasad opracowanych przez Oracle opisujący relację równości między dwoma obiektami. Na przykładzie obiektów a, b i c relacja ta powinna być (celowo zostawiam tu oryginalne nazewnictwo):

1. reflexive – co znaczy tyle, że dla każdej nie nullowej referencji a, a.equals(a) powinno zwrócić wartość true.
2. symmetric – dla każdej nie nullowej referencji a i b, a.equals(b) powinno zwrócić true wtedy i tylko wtedy, gdy b.equals(a) zwraca true.
3. transitive – dla każdej nie nullowej referencji a, b i c, jeśli a.equals(b) zwraca true i b.equals(c) zwraca true, to a.equals(c) również powinno zwrócić wartość true.
4. consistent – dla każdej nie nullowej referencji a i b, wielokrotne wywołania a.equals(b) powinny za każdym razem zwracać true lub za każdym razem zwracać false, o ile w międzyczasie dane obiekty nie zostały w jakiś sposób zmienione.
5. dla każdej nie nullowej referencji a, a.equals(null) powinno zwracać false.

Wydaje się dość proste i oczywiste, jednak szczegóły implementacyjne mogą czasami stanowić problem, zwłaszcza jeśli w grę wchodzi kwestia dziedziczenia obiektów.

Jak poprawnie zaimplementować metodę equals?

Na potrzebę tego przykładu, rozbudujemy nieco klasę Cat o pola color i hasTail:

private String name;
private String color;
private int age;
private boolean hasTail;

i zaczynamy naszą implementację! Najpierw sprawdzamy czy parametr object, który otrzymaliśmy, jest referencyjnie identyczny z naszym obiektem. Jeśli tak, to obydwie referencje wskazują na ten sam obiekt w pamięci, więc możemy je uznać za równe sobie.

@Override
public boolean equals(Object object) {
    if(this == object) {
        return true;
    }

}

Następnie sprawdzamy czy przesłany parametr jest nullem:

if(object == null) {
    return false;
}

i jeśli tak jest, to oczywiście zwracamy false, zgodnie z kontraktem equals.

W kolejnym kroku możemy już bezpiecznie (bo właśnie ustaliliśmy, że przesłany parametr nie jest nullem) wykonać sprawdzenie czy przesłany object jest typu Cat i wykonać rzutowanie:

if (object instanceof Cat) {
    Cat o = (Cat) object;

} else {
    return false;
}

Od tego momentu będziemy już operować wewnątrz tego bloku kodu. Sprawdzamy kolejno wybrane pola, które według nas stanowią o równości dwóch obiektów. Ja wybrałem pola age, color oraz hasTail:

if(color.equals(o.color) && age == o.age && hasTail == o.hasTail) {
    return true;
} else {
    return false;
}

Całość naszej gotowej metody equals prezentuje się następująco:

@Override
public boolean equals(Object object) {
    if (this == object) {
        return true;
    }
    if (object == null) {
        return false;
    }
    if (object instanceof Cat) {
        Cat o = (Cat) object;
        if (color.equals(o.color) && age == o.age && hasTail == o.hasTail) {
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
}

Często istotną rzeczą będzie dla nas optymalizacja kodu pod kątem wydajności. Zwłaszcza jeśli wiemy, że będziemy mieli bardzo dużo obiektów do porównania. Wtedy istotne jest, aby brać pod uwagę kolejność pól, które będziemy porównywać. Im większa szansa, że obiekty będą różnić się od siebie, bo (używając naszego przykładu) mają inny kolor, to właśnie to pole powinniśmy umieścić jako pierwsze w kolejce do porównania.

Stąd też na samym początku metody sprawdzamy czy referencje są sobie równe, ponieważ jeśli są, to jesteśmy w stanie od razu stwierdzić, że obiekty są sobie równe i możemy opuścić metodę. Podobnie w przypadku dalszego sprawdzenia czy parametr jest nullem oraz czy jest tego samego typu co obiekt, z którym chcemy go porównać.

HashCode – kontrakt

Czas przybliżyć kontrakt drugiej metody. Zawiera tylko trzy punkty, jednak dobrze obrazuje relacje między equals i hashCode:

1. Podczas działania danej instancji aplikacji javowej, metoda hashCode wywoływana na danym obiekcie musi zwracać ciągle tę samą wartość, o ile dany obiekt nie uległ zmianie.
2. Jeśli wywołanie na danych dwóch obiektach metody equals zwraca wartość true, to metoda hashCode musi dla tych dwóch obiektów zwracać tę samą wartość.
3. Jeśli wywołanie na dwóch obiektach metody equals zwraca wartość false, to nie jest koniecznie wymagane, aby dla tych dwóch obiektów metoda hashCode zwracała różne wartości. Jednak zwrócenie różnych wartości będzie miało pozytywny wpływ na wydajność w używaniu hash tables.

Jak zaimplementować metodę hashCode?

Może na początek warto powiedzieć jak NIE powinno się implementować metody hashCode:

@Override
public int hashCode() {
    return 1;
}

Powyższa implementacja jest najgorszą możliwą. I nie chodzi tu oczywiście o zwrócenie liczby 1, ale o zwrócenie po prostu jednej, stałej wartości dla wszystkich obiektów danego typu.

Dlaczego? Aby odpowiedzieć na to pytanie powinniśmy cofnąć się do początku tego wpisu, gdzie była mowa o kolekcjach opartych na hash tables.

Za przykład niech posłuży nam znowu klasa Cat, którą użyjemy w HashMapie, która będzie przechowywała pary <Cat,String>, gdzie String będzie oznaczał imię właściciela danego kota:

Cat susie = new Cat("Susie", "black", 3, true);
Cat lester = new Cat("Lester", "white", 5, true);
Cat tom = new Cat("Tom", "grey", 2, true);
Cat lili = new Cat("Lili", "mixed", 1, false);

Map<Cat, String> catOwners = new HashMap<>();
catOwners.put(susie, "Marek");
catOwners.put(lester, "Ania");
catOwners.put(tom, "Krzysiek");
catOwners.put(lili, "Magda");

Prosta sprawa: utworzyliśmy mapę i dodaliśmy do niej cztery koty wraz z imionami właścicieli.

Oczywiście gdy wywołamy metodę hashCode na każdym obiekcie typu Cat, to otrzymamy w wyniku wartość 1 dla każdego z nich. Sprawia to wielki problem wydajnościowy.

Kolizja hashy

Kolekcje oparte o hash tables w Javie używają do umieszczania i wyszukiwania obiektów z systemu kubełkowego. Można sobie to zobrazować w ten sposób:

Mamy tutaj cztery puste kubełki: A, B, C i D, ponieważ nasza kolekcja ma zawierać cztery elementy. Do każdego kubełka jest przypisany hashCode danego obiektu, w momencie, w którym jest on w nim umieszczany. W idealnej sytuacji każdy obiekt należałby do osobnego kubełka. Niestety w naszym przypadku, w którym metoda hashCode zwraca jedną wartość dla wszystkich obiektów, otrzymamy następującą sytuację:

Wszystkie obiekty zostaną umieszczone w jednym kubełku. Jest to nazywane kolizją hashy. Warto podkreślić, że w takiej sytuacji kolekcja w obrębie jednego kubła przyjmie postać Linked Listy.

Kolizja hashy, zwłaszcza taka jak w naszym przykładzie, powoduje ogromny problem wydajnościowy. Załóżmy, że będziemy chcieli pobrać jakiś obiekt z mapy, na przykład:

String catOwner = catOwners.get(lester);
System.out.println(catOwner);

Wtedy mechanizm najpierw wyliczy hashCode dla obiektu lester typu Cat. Następnie otrzyma w wyniku wartość 1 i sprawdzi czy w mapie istnieje kubełek z hashCode 1. Okaże się, że tak, ale znajdować tam się będzie nie jeden element, a cztery.

Teraz aby znaleźć ten właściwy obiekt, będzie trzeba wykorzystać metodę equals do porównania szukanego obiektu z każdym kolejnym z listy znajdującej się w kuble, do momentu znalezienia tego właściwego. Kolejny raz więc widać tutaj bliską relację między metodami equals i hashCode.

Warto sobie wyobrazić, że jeśli będziemy mieli pecha i szukany element będzie się akurat znajdował na końcu listy, to tym bardziej opóźni to nasz proces pobrania żądanego obiektu. W przypadku czterech obiektów oczywiście nie ma problemu, ale w przypadku tysięcy lub dziesiątek tysięcy, taki problem może już powodować poważne kłopoty wydajnościowe.

Jak temu zaradzić? Oczywiście zaimplementować hashCode w odpowiedni sposób!

Poprawna implementacja

Najlepszym rozwiązaniem jest oparcie się na równaniach hashujących, które zostały opracowane w badaniach naukowych, aby znaleźć taką kombinację, która pozwoli na jak najmniejszą ilość kolizji.

Na przykład hashCode wyliczony dla klasy Cat, wykorzystując tylko pola age oraz color, będzie wyglądał następująco:

@Override
public int hashCode() {
    int result = 7;
    result = 31 * result + age;
    result = 31 * result + (hasTail ? 1 : 0);
    return result;
}

Najpierw wybierana jest jakaś liczba pierwsza, w przykładzie powyżej będzie to 7, następnie w przypadku pola int age, mnożymy nasz tymczasowy wynik przez 31, dodajemy do niego wiek kota i przechodzimy dalej.

W kolejnym kroku również mnożymy tymczasowy wynik przez 31, dodajemy do niego wartość 0 lub 1 w zależności od tego czy wartość pola hasTail to true lub false.

Na końcu zwracamy gotowy wynik.

Może pojawić się tutaj pytanie: skąd wzięła się liczba 7 i 31? Dlaczego akurat te, a nie inne liczby?

Jak już wspomniałem wyżej, aby było jak najmniej kolizji hashy, zostały opracowane odpowiednie równania hashujące, które są stosowane także w kodzie, który jest autogenerowany przez różne IDE.

Powtarzająca się liczba 31 została wybrana, ponieważ jest nieparzystą liczbą pierwszą, która ma również tę właściwość, że mnożenie przez nią jest „tanie” w procesorach i wirtualnych maszynach, ponieważ operację mnożenia można w tym wypadku zamienić na przesunięcie bitowe i odejmowanie, aby zwiększyć wydajność i szybkość przetwarzania kodu. Ponadto w badaniach odkryto, że mnożenie przez 31 zapewnia lepszą dystrybucję hashy, przez co naturalnie powstaje mniej kolizji.

Jeśli więc powyższą implementację wdrożymy do naszego przykładu z kotami i ich właścicielami, to dla każdego obiektu w mapie otrzymamy unikalny kod hash, przez co dystrybucja obiektów w kubełkach będzie wyglądać następująco:

Dla każdego obiektu otrzymaliśmy unikalny hashCode! Dzięki temu podczas przeszukiwania mapy w celu znalezienia odpowiedniego kubełka, wystarczy znaleźć odpowiedni hashCode i od razu będziemy w stanie pobrać właściwy obiekt. Zero kolizji = świetna wydajność.

Jeśli nadpisujesz equals, to nadpisuj też hashCode!

Można poetycko powiedzieć, że equals i hashCode to papużki nierozłączki. Mówi o tym również kolejna ważna zasada: gdy nadpisujemy metodę equals, MUSIMY nadpisywać również metodę hashCode.

Dlaczego jest to takie ważne?

Wyobraźmy sobie następującą sytuację:

Cat cat1 = new Cat("Susie", "black", 3, true);
Cat cat2 = new Cat("Susie", "black", 3, true);

System.out.println(cat1.equals(cat2));

Mamy dwa obiekty typu Cat. Nadpisaliśmy metodę equals, ale nie metodę hashCode i cat1.equals(cat2) zwraca wartość true. Wówczas po dodaniu tych obiektów do HashMap:

Map<Cat, String> catStringMap = new HashMap<>();
catStringMap.put(cat1, "value1");
catStringMap.put(cat2, "value2");

przy wywołaniu:

System.out.println(catStringMap.get(cat1));
System.out.println(catStringMap.get(cat2));

otrzymamy:

value1
value2

To oczywiście niespodziewany efekt, ponieważ zakładalibyśmy, że HashMap przy próbie dodania obiektu o takim samym kluczu (cat2), jak już istniejący w kolekcji (cat1), zamieni go i w efekcie w mapie będzie dostępny tylko jeden obiekt – cat2. Bo oczywiście z naszego punktu widzenia obiekty cat1 i cat2 są identyczne.

Dzieje się tak dlatego, ponieważ podczas dodawania obiektu cat2 do mapy, wyliczany jest jego hashCode. Okazuje się wtedy, że jest on inny niż ten z obiektu cat1 i dlatego mapa umieszcza go w nowym kubełku. W efekcie kolekcja, o której myślimy, że zawiera tylko unikalne klucze, może tak naprawdę zawierać duplikaty.

IDE na ratunek!

Teorię warto oczywiście znać i wszystkie powyższe zasady oraz kontrakty są bardzo ważne. Kiedy jednak już jesteśmy z nimi zaznajomieni, nic nie stoi na przeszkodzie, aby w codziennej pracy skorzystać z pomocy, jaką niesie nam IDE takie jak Intellij, Eclipse, Netbeans oraz inne. Możemy wówczas skorzystać z odpowiedniego skrótu (w Intellij domyślnie jest to alt+insert), aby metody equals oraz hashCode zostały dla nas wygenerowane automatycznie:

Wybieramy tam pola, które chcemy aby były brane pod uwagę oraz te mogące być nullami i voilà:

Podsumowanie

Equals i hashCode to metody, które naprawdę warto znać od podszewki. Zwłaszcza jeśli chcemy zminimalizować lub całkowicie uniknąć wszelkich problemów, jakie mogą nam nastręczyć ich błędne implementacje lub też ich brak. Warto pamiętać o kontraktach każdej z metod oraz ich wspólnych relacjach. Używajmy ich z głową, nawet jeśli korzystamy z super szybkiej oraz wygodnej opcji autogenerowania, jaką prezentują nam nasze ukochane IDE.

Kod z przykładami do powyższego wpisu znajdziesz na githubie.