Guide de hashCode () en Java

1. Vue d'ensemble

Le hachage est un concept fondamental de l'informatique.

En Java, des algorithmes de hachage efficaces se cachent derrière certaines des collections les plus populaires dont nous disposons - telles que HashMap (pour un examen approfondi de HashMap , n'hésitez pas à consulter cet article) et HashSet.

Dans cet article, nous allons nous concentrer sur le fonctionnement de hashCode () , comment il joue dans les collections et comment l'implémenter correctement.

2. Utilisation de hashCode () dans les structures de données

Les opérations les plus simples sur les collections peuvent être inefficaces dans certaines situations.

Par exemple, cela déclenche une recherche linéaire qui est très inefficace pour des listes de très grandes tailles:

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

Java fournit un certain nombre de structures de données pour traiter spécifiquement ce problème - par exemple, plusieurs implémentations d'interface Map sont des tables de hachage.

Lorsque vous utilisez une table de hachage, ces collections calculer la valeur de hachage pour une clé donnée en utilisant la hashCode () méthode et utiliser cette valeur en interne pour stocker les données - afin que les opérations d'accès sont beaucoup plus efficaces.

3. Comprendre comment hashCode () Travaux

En termes simples, hashCode () renvoie une valeur entière, générée par un algorithme de hachage.

Les objets qui sont égaux (selon leur égal () ) doivent renvoyer le même code de hachage. Il n'est pas nécessaire que différents objets renvoient des codes de hachage différents.

Le contrat général de hashCode () stipule:

  • Chaque fois qu'il est invoqué sur le même objet plus d'une fois au cours d'une exécution d'une application Java, hashCode () doit systématiquement renvoyer la même valeur, à condition qu'aucune information utilisée dans les comparaisons égales sur l'objet ne soit modifiée. Cette valeur n'a pas besoin de rester cohérente d'une exécution d'une application à une autre exécution de la même application
  • Si deux objets sont égaux selon la méthode equals (Object) , alors l'appel de la méthode hashCode () sur chacun des deux objets doit produire la même valeur
  • Il n'est pas nécessaire que si deux objets sont inégaux selon la méthode equals (java.lang.Object) , l'appel de la méthode hashCode sur chacun des deux objets doit produire des résultats entiers distincts. Cependant, les développeurs doivent être conscients que la production de résultats entiers distincts pour des objets inégaux améliore les performances des tables de hachage

«Autant que cela soit raisonnablement pratique, la méthode hashCode () définie par la classe Object renvoie des entiers distincts pour des objets distincts. (Ceci est généralement implémenté en convertissant l'adresse interne de l'objet en un entier, mais cette technique d'implémentation n'est pas requise par le langage de programmation JavaTM.) »

4. Une implémentation naïve de hashCode ()

Il est en fait assez simple d'avoir une implémentation naïve de hashCode () qui adhère pleinement au contrat ci-dessus.

Pour illustrer cela, nous allons définir un exemple de classe User qui remplace l'implémentation par défaut de la méthode:

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 fournit des implémentations personnalisées pour equals () et hashCode () qui adhèrent pleinement aux contrats respectifs. De plus, il n'y a rien d'illégitime à avoir hashCode () renvoyant une valeur fixe.

Cependant, cette implémentation dégrade la fonctionnalité des tables de hachage à pratiquement zéro, car chaque objet serait stocké dans le même compartiment unique.

Dans ce contexte, une recherche de table de hachage est effectuée de manière linéaire et ne nous donne aucun avantage réel - plus à ce sujet dans la section 7.

5. Amélioration de l' implémentation de hashCode ()

Améliorons un peu l' implémentation actuelle de hashCode () en incluant tous les champs de la classe User afin qu'elle puisse produire des résultats différents pour des objets inégaux:

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

Cet algorithme de hachage de base est définitivement bien meilleur que le précédent, car il calcule le code de hachage de l'objet en multipliant simplement les codes de hachage des champs nom et e - mail et l' id .

En termes généraux, nous pouvons dire que c'est une implémentation raisonnable de hashCode () , tant que nous gardons l' implémentation equals () cohérente avec elle.

6. Implémentations standard de hashCode ()

Plus l'algorithme de hachage que nous utilisons pour calculer les codes de hachage est performant, meilleures seront les performances des tables de hachage.

Jetons un coup d'œil à une implémentation «standard» qui utilise deux nombres premiers pour ajouter encore plus d'unicité aux codes de hachage calculés:

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

Bien qu'il soit essentiel de comprendre les rôles que jouent les méthodes hashCode () et equals () , nous n'avons pas à les implémenter à partir de zéro à chaque fois, car la plupart des IDE peuvent générer des implémentations personnalisées de hashCode () et equals () et depuis Java 7, nous avons une méthode utilitaire Objects.hash () pour un hachage confortable:

Objects.hash(name, email)

IntelliJ IDEA génère l'implémentation suivante:

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

Et Eclipse produit celui-ci:

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

En plus des implémentations hashCode () basées sur l'IDE ci-dessus , il est également possible de générer automatiquement une implémentation efficace, par exemple en utilisant Lombok. Dans ce cas, la dépendance lombok-maven doit être ajoutée à 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().

Comme toujours, tous les exemples de code présentés dans cet article sont disponibles à l'adresse over sur GitHub.