Przewodnik po hashCode () w Javie

1. Przegląd

Haszowanie to podstawowa koncepcja informatyki.

W Javie wydajne algorytmy haszujące stoją za niektórymi z najpopularniejszych dostępnych kolekcji - takich jak HashMap (aby uzyskać dogłębne spojrzenie na HashMap , przeczytaj ten artykuł) i HashSet.

W tym artykule skupimy się na tym , jak działa funkcja hashCode () , jak działa w kolekcjach i jak poprawnie ją zaimplementować.

2. Wykorzystanie hashCode () w strukturach danych

W niektórych sytuacjach najprostsze operacje na kolekcjach mogą być nieefektywne.

Na przykład uruchamia to wyszukiwanie liniowe, które jest wysoce nieskuteczne w przypadku list o dużych rozmiarach:

List words = Arrays.asList("Welcome", "to", "Baeldung"); if (words.contains("Baeldung")) { System.out.println("Baeldung is in the list"); }

Java udostępnia wiele struktur danych do rozwiązywania tego problemu - na przykład kilka implementacji interfejsu Map to tablice mieszające.

W przypadku korzystania z tabeli mieszania, te zbiory obliczyć wartość hash dla danego klucza, używając hashCode () metodę i używać tej wartości wewnętrznie do przechowywania danych - tak, że operacje dostępu są znacznie bardziej wydajne.

3. Zrozumienie, jak działa hashCode ()

Mówiąc najprościej, hashCode () zwraca wartość całkowitą, wygenerowaną przez algorytm haszujący.

Obiekty, które są równe (według ich równości () ) muszą zwracać ten sam kod skrótu. Nie jest wymagane, aby różne obiekty zwracały różne kody skrótu.

Ogólna umowa funkcji hashCode () stwierdza:

  • Za każdym razem, gdy jest wywoływana na tym samym obiekcie więcej niż jeden raz podczas wykonywania aplikacji Java, funkcja hashCode () musi konsekwentnie zwracać tę samą wartość, pod warunkiem, że żadne informacje używane w porównaniach równości na obiekcie nie zostaną zmodyfikowane. Ta wartość nie musi pozostawać spójna od jednego wykonania aplikacji do innego wykonania tej samej aplikacji
  • Jeśli dwa obiekty są równe zgodnie z metodą equals (Object) , to wywołanie metody hashCode () na każdym z dwóch obiektów musi dać tę samą wartość
  • Nie jest wymagane, aby jeśli dwa obiekty były nierówne zgodnie z metodą equals (java.lang.Object) , to wywołanie metody hashCode na każdym z dwóch obiektów musiało dać różne wyniki w postaci liczb całkowitych. Jednak programiści powinni być świadomi, że tworzenie różnych wyników w postaci liczb całkowitych dla nierównych obiektów poprawia wydajność tabel skrótów

„O ile jest to rozsądnie praktyczne, metoda hashCode () zdefiniowana przez klasę Object zwraca odrębne liczby całkowite dla różnych obiektów. (Zazwyczaj jest to realizowane poprzez konwersję wewnętrznego adresu obiektu na liczbę całkowitą, ale ta technika implementacji nie jest wymagana przez język programowania JavaTM) ”.

4. Naiwna implementacja hashCode ()

Właściwie jest całkiem proste mieć naiwną implementację hashCode (), która jest w pełni zgodna z powyższą umową.

Aby to zademonstrować, zdefiniujemy przykładową klasę User, która przesłania domyślną implementację metody:

public class User { private long id; private String name; private String email; // standard getters/setters/constructors @Override public int hashCode() { return 1; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null) return false; if (this.getClass() != o.getClass()) return false; User user = (User) o; return id == user.id && (name.equals(user.name) && email.equals(user.email)); } // getters and setters here }

Użytkownik klasa zapewnia niestandardowe implementacje dla obu równych () i hashCode () , które w pełni przestrzegają odpowiednich umów. Co więcej, nie ma nic nielegalnego w tym, że funkcja hashCode () zwraca jakąkolwiek stałą wartość.

Jednak ta implementacja obniża funkcjonalność tabel skrótów do zera, ponieważ każdy obiekt byłby przechowywany w tym samym, pojedynczym zasobniku.

W tym kontekście przeszukiwanie tablicy skrótów jest wykonywane liniowo i nie daje nam żadnej realnej korzyści - więcej na ten temat w sekcji 7.

5. Udoskonalenie implementacji hashCode ()

Poprawmy trochę obecną implementację hashCode () , włączając wszystkie pola klasy User, tak aby mogła dawać różne wyniki dla nierównych obiektów:

@Override public int hashCode() { return (int) id * name.hashCode() * email.hashCode(); }

Ten podstawowy algorytm mieszający jest zdecydowanie lepszy niż poprzedni, ponieważ oblicza kod skrótu obiektu, po prostu mnożąc kody skrótu z pól nazwy i adresu e - mail oraz identyfikatora .

Ogólnie rzecz biorąc, możemy powiedzieć, że jest to rozsądna implementacja hashCode () , pod warunkiem, że implementacja equals () będzie z nią zgodna.

6. Standardowe implementacje hashCode ()

Im lepszy algorytm mieszający, którego używamy do obliczania kodów skrótów, tym lepsza będzie wydajność tablic mieszających.

Rzućmy okiem na „standardową” implementację, która wykorzystuje dwie liczby pierwsze w celu dodania jeszcze większej unikalności do obliczonych kodów skrótu:

@Override public int hashCode() { int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null ? 0 : name.hashCode()); hash = 31 * hash + (email == null ? 0 : email.hashCode()); return hash; }

Chociaż istotne jest zrozumienie ról odgrywanych przez metody hashCode () i equals () , nie musimy za każdym razem implementować ich od zera, ponieważ większość IDE może generować niestandardowe implementacje hashCode () i equals (), a od wersji Java 7, otrzymaliśmy metodę narzędziową Objects.hash () do wygodnego mieszania:

Objects.hash(name, email)

IntelliJ IDEA generuje następującą implementację:

@Override public int hashCode() { int result = (int) (id ^ (id >>> 32)); result = 31 * result + name.hashCode(); result = 31 * result + email.hashCode(); return result; }

A Eclipse produkuje to:

@Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((email == null) ? 0 : email.hashCode()); result = prime * result + (int) (id ^ (id >>> 32)); result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; }

Oprócz powyższych implementacji hashCode () opartych na IDE , możliwe jest również automatyczne generowanie wydajnej implementacji, na przykład przy użyciu Lombok. W tym przypadku zależność lombok-maven musi zostać dodana do pom.xml :

 org.projectlombok lombok-maven 1.16.18.0 pom 

Teraz wystarczy dodać adnotację do klasy User za pomocą @EqualsAndHashCode :

@EqualsAndHashCode public class User { // fields and methods here }

Podobnie, jeśli chcemy, aby klasa HashCodeBuilder z Apache Commons Lang generowała dla nas implementację hashCode () , zależność commons-lang Maven musi być zawarta w pliku pom:

 commons-lang commons-lang 2.6 

I hashCode () mogą być realizowane w ten sposób:

public class User { public int hashCode() { return new HashCodeBuilder(17, 37). append(id). append(name). append(email). toHashCode(); } }

Ogólnie rzecz biorąc, nie ma uniwersalnej reguły, której można by się trzymać, jeśli chodzi o implementację funkcji hashCode () . Gorąco polecamy przeczytanie książki Joshua Bloch Effective Java, która zawiera listę dokładnych wskazówek dotyczących implementacji wydajnych algorytmów haszujących.

Można tu zauważyć, że wszystkie te implementacje wykorzystują liczbę 31 w jakiejś formie - to dlatego, że 31 ma fajną właściwość - jej mnożenie można zastąpić przesunięciem bitowym, które jest szybsze niż standardowe mnożenie:

31 * i == (i << 5) - i

7. Obsługa kolizji skrótów

Wewnętrzne zachowanie tabel skrótów podnosi istotny aspekt tych struktur danych: nawet przy wydajnym algorytmie mieszania dwa lub więcej obiektów może mieć ten sam kod skrótu, nawet jeśli są nierówne. Tak więc ich kody skrótów wskazywałyby na ten sam zasobnik, mimo że miałyby różne klucze tablicy skrótów.

Sytuacja ta jest powszechnie znana jako kolizja hash i istnieją różne metodologie radzenia sobie z nią, z których każda ma swoje wady i zalety. Java's HashMap używa oddzielnej metody łańcuchowej do obsługi kolizji:

„Gdy dwa lub więcej obiektów wskazuje ten sam zasobnik, są one po prostu przechowywane na połączonej liście. W takim przypadku tabela skrótów jest tablicą połączonych list, a każdy obiekt z tym samym hashem jest dołączany do połączonej listy w indeksie zasobnika w tablicy.

W najgorszym przypadku kilka zasobników byłoby powiązanych z listą połączoną, a pobieranie obiektu z listy byłoby wykonywane liniowo ”.

Metodologie kolizji skrótów pokazują w skrócie, dlaczego tak ważne jest efektywne zaimplementowanie hashCode () .

Java 8 wprowadziła interesujące ulepszenie do implementacji HashMap - jeśli rozmiar zasobnika przekroczy określony próg, połączona lista zostanie zastąpiona mapą drzewa. Pozwala to na osiągnięcie O ( logn ) spojrzenia w górę zamiast pesymistycznego O (n) .

8. Tworzenie trywialnej aplikacji

Aby przetestować funkcjonalność standardowej implementacji hashCode () , stwórzmy prostą aplikację Java, która dodaje niektóre obiekty użytkownika do HashMap i używa SLF4J do logowania wiadomości do konsoli za każdym razem, gdy metoda jest wywoływana.

Oto punkt wejścia przykładowej aplikacji:

public class Application { public static void main(String[] args) { Map users = new HashMap(); User user1 = new User(1L, "John", "[email protected]"); User user2 = new User(2L, "Jennifer", "[email protected]"); User user3 = new User(3L, "Mary", "[email protected]"); users.put(user1, user1); users.put(user2, user2); users.put(user3, user3); if (users.containsKey(user1)) { System.out.print("User found in the collection"); } } } 

A to jest implementacja hashCode () :

public class User { // ... public int hashCode() { int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null ? 0 : name.hashCode()); hash = 31 * hash + (email == null ? 0 : email.hashCode()); logger.info("hashCode() called - Computed hash: " + hash); return hash; } }

The only detail worth stressing here is that each time an object is stored in the hash map and checked with the containsKey() method, hashCode() is invoked and the computed hash code is printed out to the console:

[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -282948472 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -1540702691 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819 User found in the collection

9. Conclusion

It's clear that producing efficient hashCode() implementations often requires a mixture of a few mathematical concepts, (i.e. prime and arbitrary numbers), logical and basic mathematical operations.

Regardless, it's entirely possible to implement hashCode() effectively without resorting to these techniques at all, as long as we make sure the hashing algorithm produces different hash codes for unequal objects and is consistent with the implementation of equals().

Jak zawsze, wszystkie przykłady kodu przedstawione w tym artykule są dostępne w serwisie GitHub.