HashCode, equals i kolekcje

Nie wiem jak Wy, ale ja nigdy nie zagłębiałem się w kwestię hashCode i equals. Zawsze generowałem obydwa elementy używając IDE z uwzględniając identyczne parametry. Pozwalało mi to zachować myśl, że gdy equals obiektu zwróci wartość 'true' to hash będzie zawsze identyczny. Wiedziałem, że tak powinno być, ale nigdy nie myślałem dlaczego. Gdy zostałem ostatnio zapytany o to, okazało się, że nie mam pojęcia dlaczego i po co się tak robi. Zagłębiając się w literaturę o tym poświęconą postanowiłem przedstawić Wam wiedzę, którą powinna posiadać każda osoba korzystająca z kolekcji. Wychodzi więc, że każdy. Szkoda, że wcześniej nikt nie wyjaśnił mi, że wiedza o tym jest niezbędna.

Kontrakt

Tak jak wspomniałem we wstępie, gdy equals zwróci wartość 'true', możemy spodziewać się, że hash będzie identyczny. Nigdy jednak nie zastanawiałem się jak wygląda sytuacja odwrócona. Czy gdy hash jest identyczny to zawsze equals zwraca 'true'? I tutaj wyszło na to, że nie. W Javie występuje kontrakt pomiędzy equals'em, a hashCode. Mówi on, że gdy equals dla dwóch obiektów zwróci 'true' to hashCode musi być identyczny dla nich, ale gdy hashCode jest równe to niekoniecznie obiekty musza być identyczne w ramach metody equals. W sumie mądre posunięcie. Metoda hashCode zwraca wartość int, bylibyśmy więc ograniczeni w naszym systemie do 2^32 różnych obiektów. Niby dużo, ale ograniczenia nigdy nie są dobre.

Kolekcje

Nie wierzę, to teraz wszędzie tam, gdzie używamy HashSet, HashMap oraz innych kolekcji, gdzie używamy hash'y do przechowywania obiektów to nasze obiekty, pomimo że różne to nadpisują się? Nie wiem jak Wy, ale ja pierwsze co pomyślałem, gdy zaznajomiłem się z tą tematyką, to właśnie taki przypadek. Spokojnie, jednak nie jest tak do końca.

Owszem kolekcje korzystają z HashCode, ale w ramach optymalizacji oraz rozmieszczenia obiektów. Wykonajmy testy dla pewności jak to działa.

Testujemy

Stworzymy dwie klasy obiektów. Jedną z prawidłowymi metodami hashCode oraz equals, drugą z zmodyfikowanym equals'em.

public class TestableObject {

 private String value;

 public TestableObject(final String value) {
  this.value = value;
 }

 @Override
 public int hashCode() {
  System.out.println("HashCode method executed");
  final int prime = 31;
  int result = 1;
  result = prime * result + ((value == null) ? 0 : value.hashCode());
  return result;
 }

 @Override
 public boolean equals(Object obj) {
  System.out.println("Equals method executed");
  if (this == obj) {
   return true;
  }
  if (obj == null) {
   return false;
  }
  if (!(obj instanceof TestableObject)) {
   return false;
  }
  TestableObject other = (TestableObject) obj;
  if (value == null) {
   if (other.value != null) {
    return false;
   }
  } else if (!value.equals(other.value)) {
   return false;
  }
  return true;
 }

 @Override
 public String toString() {
  return "TestableObject [value=" + value + ", hashCode=" + hashCode() + "]";
 }

}

public class TestableObjectWithEqualsModified extends TestableObject {

 public TestableObjectWithEqualsModified(String value) {
  super(value);
 }

 @Override
 public boolean equals(Object obj) {
  System.out.println("Modified equals executed");
  return false;
 }

 @Override
 public String toString() {
  return "TestableObjectWithEqualsModified [toString()=" + super.toString() + "]";
 }
}

Posiadamy już odpowiednie obiekty. Teraz trzeba pomyśleć z jakimi przypadkami testowymi możemy się spotkać:

• Dodanie elementu do pustej kolekcji,
• Dodanie do kolekcji tego samego elementu,
• Dodanie identycznego elementu (equals zwraca true, hashCode zwraca tą samą wartość),
• Dodanie innego elementu,
• Dodanie elementu z tym samym hashCode, ale funkcja equals zwraca wartość 'false'.

Wszystkie przypadki zostały sprawdzone w poniższym teście.

@Test
public void testCollectionAdd() {
 Set<TestableObject> set = new HashSet<>();
 System.out.println("Add 'AAA'");
 TestableObject twoTimesAdded = new TestableObject("AAA");
 set.add(twoTimesAdded);
 System.out.println("Add again 'AAA'");
 set.add(twoTimesAdded);
 System.out.println("Add new 'AAA'");
 set.add(new TestableObject("AAA"));
 System.out.println("Add 'AAB'");
 set.add(new TestableObjectWithEqualsModified("AAB"));
 System.out.println("Add new 'AAB', but equals return false");
 set.add(new TestableObjectWithEqualsModified("AAB"));
 System.out.println("In set:");
 set.stream().forEach(element -> System.out.println(element));
}

Wynikiem tego testu jest:

Add 'AAA'
HashCode method executed
Add again 'AAA'
HashCode method executed
Add new 'AAA'
HashCode method executed
Equals method executed
Add 'AAB'
HashCode method executed
Add new 'AAB', but equals return false
HashCode method executed
Modified equals executed
In set:
HashCode method executed
TestableObject [value=AAA, hashCode=64576]
HashCode method executed
TestableObjectWithEqualsModified [toString()=TestableObject [value=AAB, hashCode=64577]]
HashCode method executed
TestableObjectWithEqualsModified [toString()=TestableObject [value=AAB, hashCode=64577]]

Wyniki

Co z naszych testów wynikło? Wystarczy spojrzeć na wyniki. Dodając pierwszy element zostaje obliczony hashCode. W kolekcji nie posiadamy żadnego elementu z takim hashCode'm, dlatego nie ma żadnego problemu z dodaniem tego elementu. Następnie dodajemy kolejny obiekt, tutaj obliczany jest hashCode i jest on równy poprzedniemu, ale nic więcej się ponoć nie dzieje (dzieje się, ale o tym później). Element nie zostaje dodany (tutaj też ważne jest to, że wraz z próbą dodania drugiego elementu będącego identycznymi w ramach equals i hashCode to element nie nadpisuje drugiego, ale zostaje pominięty). Następnie dodawany jest następny identyczny obiekt. I tutaj uruchomiona zastała metoda obliczająca hashCode, a zaraz po niej metoda equals.

Zatrzymajmy się na razie w tym miejscu. Co się właśnie stało? Gdy dodawaliśmy dwa razy ten sam obiekt to metoda equals nie została wywołana, a gdy drugi obiekt o tych samych wartościach to tak. Problem rozwiązuje się w przypadku, gdy pomyślimy o obiektach jako miejscach w pamięci. W ramach takich obiektów możemy zastosować operator ==. Właśnie on jest wykorzystany w tym przypadku. Skoro obiekt wskazuje na ten sam obszar pamięci tzn. jest on taki sam. W drugim przypadku operacja porównania pamięci zwraca 'false'. Została więc wywołana metoda equals do weryfikacji czy obiekty są identyczne. W tym przypadku metoda equals zwraca 'true', a więc obiekt nie zostaje dodany.

Spójrzmy jednak na następny test. Dodanie elementu z tym samym hashCode, ale funkcja equals zwraca wartość 'false'. Tutaj okazuje się, że obydwa obiekty pomimo wspólnego hashCode zostają zachowane w kolekcji. Osobiście już po zobaczeniu, że zostaje wywołana metoda equals, spodziewałem się takiego właśnie wyniku. Przed testami jednak byłem przekonany, że taki obiekt zostanie nadpisany lub ominięty.

Wiedza konieczna!

Po uświadomieniu sobie w jakim błędzie żyłem pisząc kod i operując kolekcjami żałuje, że nikt wcześniej nie zadał mi pytania o ten temat. W moich aplikacjach jednak nie znajdzie się błędu w ramach kolekcji, equals'a oraz hashCode'a. To wszystko dzięki temu, że nigdy nie odważyłem się i nie czułem takiej potrzeby napisać własnej implementacji tych metod. Jednakże, gdybym popełnił takie zmiany w moim kodzie, najprawdopodobniej zrobiłbym to źle. Nie wiem jak Wy, ale ja już chyba nigdy nie zapomnę jak to działa. Mam nadzieję, że nie tylko ja. Zapraszam do komentowania oraz obejrzenia pobrania kodu testującego ten przypadek.