Guida a hashCode () in Java

1. Panoramica

L'hashing è un concetto fondamentale dell'informatica.

In Java, algoritmi di hashing efficienti stanno dietro ad alcune delle raccolte più popolari che abbiamo a disposizione, come HashMap (per uno sguardo approfondito su HashMap , non esitare a controllare questo articolo) e HashSet.

In questo articolo, ci concentreremo su come funziona hashCode () , su come viene riprodotto nelle raccolte e su come implementarlo correttamente.

2. Utilizzo di hashCode () nelle strutture dati

Le operazioni più semplici sulle raccolte possono essere inefficienti in determinate situazioni.

Ad esempio, questo innesca una ricerca lineare che è altamente inefficace per elenchi di grandi dimensioni:

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

Java fornisce una serie di strutture dati per affrontare questo problema in modo specifico, ad esempio diverse implementazioni dell'interfaccia Map sono tabelle hash.

Quando si utilizza una tabella hash, queste raccolte calcolano il valore hash per una determinata chiave utilizzando il metodo hashCode () e utilizzano questo valore internamente per archiviare i dati, in modo che le operazioni di accesso siano molto più efficienti.

3. Capire come hashCode () Opere

In poche parole, hashCode () restituisce un valore intero, generato da un algoritmo di hashing.

Gli oggetti che sono uguali (in base al loro uguale () ) devono restituire lo stesso codice hash. Non è necessario che oggetti diversi restituiscano codici hash diversi.

Il contratto generale di hashCode () afferma:

  • Ogni volta che viene invocato sullo stesso oggetto più di una volta durante l'esecuzione di un'applicazione Java, hashCode () deve restituire costantemente lo stesso valore, a condizione che non venga modificata alcuna informazione utilizzata nei confronti uguali sull'oggetto. Questo valore non deve rimanere coerente da un'esecuzione di un'applicazione a un'altra esecuzione della stessa applicazione
  • Se due oggetti sono uguali secondo il metodo equals (Object) , la chiamata al metodo hashCode () su ciascuno dei due oggetti deve produrre lo stesso valore
  • Non è necessario che se due oggetti sono diversi secondo il metodo equals (java.lang.Object) , la chiamata del metodo hashCode su ciascuno dei due oggetti deve produrre risultati interi distinti. Tuttavia, gli sviluppatori devono essere consapevoli del fatto che la produzione di risultati interi distinti per oggetti disuguali migliora le prestazioni delle tabelle hash

“Per quanto sia ragionevolmente pratico, il metodo hashCode () definito dalla classe Object restituisce interi distinti per oggetti distinti. (Questo viene in genere implementato convertendo l'indirizzo interno dell'oggetto in un numero intero, ma questa tecnica di implementazione non è richiesta dal linguaggio di programmazione JavaTM.) "

4. Naive hashCode () Attuazione

In realtà è abbastanza semplice avere un'implementazione ingenua di hashCode () che aderisce completamente al contratto di cui sopra.

Per dimostrarlo, definiremo una classe User di esempio che sovrascrive l'implementazione predefinita del metodo:

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 }

La classe User fornisce implementazioni personalizzate sia per equals () che per hashCode () che aderiscono completamente ai rispettivi contratti. Inoltre, non c'è nulla di illegittimo nell'avere hashCode () che restituisce un valore fisso.

Tuttavia, questa implementazione degrada la funzionalità delle tabelle hash praticamente a zero, poiché ogni oggetto verrebbe archiviato nello stesso singolo bucket.

In questo contesto, una ricerca in una tabella hash viene eseguita in modo lineare e non ci offre alcun vantaggio reale - maggiori informazioni su questo nella sezione 7.

5. Migliorare l' implementazione di hashCode ()

Miglioriamo un po 'l' implementazione corrente di hashCode () includendo tutti i campi della classe User in modo che possa produrre risultati diversi per oggetti disuguali:

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

Questo algoritmo di hashing di base è definitivamente molto meglio di quella precedente, come si calcola il codice hash dell'oggetto semplicemente moltiplicando i codici hash dei nome e email campi e l' id .

In termini generali, possiamo dire che questa è un'implementazione ragionevole di hashCode () , a patto di mantenere l' implementazione di equals () coerente con essa.

6. Implementazioni hashCode () standard

Migliore è l'algoritmo di hashing che utilizziamo per calcolare i codici hash, migliori saranno le prestazioni delle tabelle hash.

Diamo un'occhiata a un'implementazione "standard" che utilizza due numeri primi per aggiungere ancora più unicità ai codici hash calcolati:

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

Sebbene sia essenziale comprendere i ruoli che giocano i metodi hashCode () ed equals () , non dobbiamo implementarli da zero ogni volta, poiché la maggior parte degli IDE può generare implementazioni hashCode () ed equals () personalizzate e da Java 7, abbiamo un metodo di utilità Objects.hash () per un comodo hashing:

Objects.hash(name, email)

IntelliJ IDEA genera la seguente implementazione:

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

Ed Eclipse produce questo:

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

Oltre alle precedenti implementazioni hashCode () basate su IDE , è anche possibile generare automaticamente un'implementazione efficiente, ad esempio utilizzando Lombok. In questo caso, la dipendenza lombok-maven deve essere aggiunta a 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().

Come sempre, tutti gli esempi di codice mostrati in questo articolo sono disponibili su GitHub.