Ghid pentru hashCode () în Java

1. Prezentare generală

Hashing-ul este un concept fundamental al informaticii.

În Java, algoritmii de hash eficienți stau în spatele unora dintre cele mai populare colecții pe care le avem disponibile - cum ar fi HashMap (pentru o privire aprofundată asupra HashMap , nu ezitați să verificați acest articol) și HashSet

În acest articol, ne vom concentra asupra modului în care funcționează hashCode () , cum se joacă în colecții și cum să îl implementăm corect.

2. Utilizarea hashCode () în structuri de date

Cele mai simple operațiuni pe colecții pot fi ineficiente în anumite situații.

De exemplu, aceasta declanșează o căutare liniară, care este extrem de ineficientă pentru liste de dimensiuni uriașe:

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

Java oferă o serie de structuri de date pentru rezolvarea specifică a acestei probleme - de exemplu, mai multe implementări ale interfeței Map sunt tabele hash.

Când se folosește un tabel hash, aceste colecții se calculează valoarea hash pentru o anumită cheie folosind hashCode () metoda și de a folosi această valoare pe plan intern pentru a stoca datele - astfel încât operațiunile de acces sunt mult mai eficiente.

3. Înțelegerea modului în care hashCode () Lucrări

Pur și simplu, hashCode () returnează o valoare întreagă, generată de un algoritm de hash.

Obiectele care sunt egale (conform lor este egal () ) trebuie să returneze același cod hash. Nu este necesar ca diferite obiecte să returneze coduri hash diferite.

Contractul general al hashCode () prevede:

  • Ori de câte ori este invocat pe același obiect de mai multe ori în timpul executării unei aplicații Java, hashCode () trebuie să returneze în mod consecvent aceeași valoare, cu condiția să nu fie modificată nicio informație utilizată în comparații egale pe obiect. Această valoare nu trebuie să rămână consecventă de la o execuție a unei aplicații la o altă execuție a aceleiași aplicații
  • Dacă două obiecte sunt egale conform metodei egale (Obiect) , atunci apelarea metodei hashCode () pe fiecare dintre cele două obiecte trebuie să producă aceeași valoare
  • Nu este necesar ca dacă două obiecte sunt inegale conform metodei egale (java.lang.Object) , atunci apelarea metodei hashCode pe fiecare dintre cele două obiecte trebuie să producă rezultate întregi distincte. Cu toate acestea, dezvoltatorii ar trebui să fie conștienți de faptul că producerea de rezultate întregi distincte pentru obiecte inegale îmbunătățește performanța tabelelor hash

„Atât cât este practic rezonabil, metoda hashCode () definită de clasa Object returnează numere întregi distincte pentru obiecte distincte. (Aceasta este de obicei implementată prin conversia adresei interne a obiectului într-un număr întreg, dar această tehnică de implementare nu este necesară de limbajul de programare JavaTM.) ”

4. O implementare Naive hashCode ()

Este de fapt destul de simplu să ai o implementare hashCode () naivă care să adere pe deplin la contractul de mai sus.

Pentru a demonstra acest lucru, vom defini un exemplu de clasă de utilizator care suprascrie implementarea implicită a metodei:

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 }

Utilizatorului Clasa oferă implementări personalizate pentru ambele equals () și hashCode () , care aderă pe deplin la contractele respective. Și mai mult, nu este nimic ilegitim dacă hashCode () returnează orice valoare fixă.

Cu toate acestea, această implementare degradează funcționalitatea tabelelor hash la practic zero, deoarece fiecare obiect ar fi stocat în același bucket unic.

În acest context, o căutare a tabelului hash se efectuează liniar și nu ne oferă niciun avantaj real - mai multe despre acest lucru în secțiunea 7.

5. Îmbunătățirea hashCode () de punere în aplicare

Să îmbunătățim puțin implementarea curentă hashCode () prin includerea tuturor câmpurilor clasei User , astfel încât să poată produce rezultate diferite pentru obiecte inegale:

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

Acest algoritm de hash de bază este definitiv mult mai bun decât cel anterior, deoarece calculează codul hash al obiectului prin simpla multiplicare a codurilor hash ale câmpurilor de nume și e-mail și ale id-ului .

În termeni generali, putem spune că aceasta este o implementare rezonabilă hashCode () , atâta timp cât menținem implementarea egal () în concordanță cu aceasta.

6. Implementări standard hashCode ()

Cu cât este mai bun algoritmul de hash pe care îl folosim pentru a calcula codurile hash, cu atât va fi mai bună performanța tabelelor hash.

Să aruncăm o privire la o implementare „standard” care utilizează două numere primare pentru a adăuga și mai multă unicitate codurilor hash calculate:

@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; }

Deși este esențial să înțelegem rolurile pe care le joacă metodele hashCode () și equals () , nu trebuie să le implementăm de la zero de fiecare dată, deoarece majoritatea IDE-urilor pot genera implementări hashCode () și egal () personalizate și din Java 7, am obținut o metodă de utilitate Objects.hash () pentru hashing confortabil:

Objects.hash(name, email)

IntelliJ IDEA generează următoarea implementare:

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

Și Eclipse îl produce pe acesta:

@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; }

În plus față de implementările hashCode () bazate pe IDE de mai sus , este, de asemenea, posibil să generați automat o implementare eficientă, de exemplu folosind Lombok. În acest caz, dependența lombok-maven trebuie adăugată la pom.xml :

 org.projectlombok lombok-maven 1.16.18.0 pom 

It's now enough to annotate the User class with @EqualsAndHashCode:

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

Similarly, if we want Apache Commons Lang's HashCodeBuilder class to generate a hashCode() implementation for us, the commons-lang Maven dependency must be included in the pom file:

 commons-lang commons-lang 2.6 

And hashCode() can be implemented like this:

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

In general, there's no universal recipe to stick to when it comes to implementing hashCode(). We highly recommend reading Joshua Bloch's Effective Java, which provides a list of thorough guidelines for implementing efficient hashing algorithms.

What can be noticed here is that all those implementations utilize number 31 in some form – this is because 31 has a nice property – its multiplication can be replaced by a bitwise shift which is faster than the standard multiplication:

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

7. Handling Hash Collisions

The intrinsic behavior of hash tables raises up a relevant aspect of these data structures: even with an efficient hashing algorithm, two or more objects might have the same hash code, even if they're unequal. So, their hash codes would point to the same bucket, even though they would have different hash table keys.

This situation is commonly known as a hash collision, and various methodologies exist for handling it, with each one having their pros and cons. Java's HashMap uses the separate chaining method for handling collisions:

“When two or more objects point to the same bucket, they're simply stored in a linked list. In such a case, the hash table is an array of linked lists, and each object with the same hash is appended to the linked list at the bucket index in the array.

In the worst case, several buckets would have a linked list bound to it, and the retrieval of an object in the list would be performed linearly.”

Hash collision methodologies show in a nutshell why it's so important to implement hashCode() efficiently.

Java 8 brought an interesting enhancement to HashMap implementation – if a bucket size goes beyond the certain threshold, the linked list gets replaced with a tree map. This allows achieving O(logn) look up instead of pessimistic O(n).

8. Creating a Trivial Application

To test the functionality of a standard hashCode() implementation, let's create a simple Java application that adds some User objects to a HashMap and uses SLF4J for logging a message to the console each time the method is called.

Here's the sample application's entry point:

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"); } } } 

And this is the hashCode() implementation:

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().

Ca întotdeauna, toate exemplele de cod prezentate în acest articol sunt disponibile pe GitHub.