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.
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):
- reflexive – co znaczy tyle, że dla każdej nie nullowej referencji a,
a.equals(a)
powinno zwrócić wartośćtrue
. - symmetric – dla każdej nie nullowej referencji a i b,
a.equals(b)
powinno zwrócićtrue
wtedy i tylko wtedy, gdyb.equals(a)
zwracatrue
. - transitive – dla każdej nie nullowej referencji a, b i c, jeśli
a.equals(b)
zwracatrue
ib.equals(c)
zwraca true, toa.equals(c)
również powinno zwrócić wartośćtrue
. - 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. - 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:
- 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.
- 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ść. - 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 jedną wartość dla danego klucza, będzie zawierała ich dwie.
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.
Super, jak dla mnie jako początkującego bardzo fajnie wytłumaczone zwłaszcza w kontekscie użycia w HashMap czy HashSet 🙂
Dzięki serdeczne, bardzo się cieszę, że post się spodobał i przydał 🙂