Accélerer vos tests et vos recherches avec hashCode()
Eric Vialle | Lundi 19 mai 2008 | 8:22
Chaque objet contient la méthode boolean equals() et int hashCode(). Ces deux méthodes héritent de l’objet java.lang.Objet dont tous les objets héritent. Nous allons voir qu’est ce que le HashCode, comment on l’utilise, puis comment optimiser nos recherches et nos tests d’objets avec ce concept.
Qu’est ce que le HashCode ?
Un HashCode représente une signature d’un objet. Il s’agit d’un entier de type int (32 bits). Celui-ci est calculé selon un algorithme prenant en compte son contenu.
Chaque type d’objet a sa propre implémentation. Vous pouvez vous aussi implementer la votre dans une classe, il suffit d’implémenter cette méthode
- @Override
- int hashCode() {
- // votre implementation
- }
Par exemple, l’algorithme générant le HashCode de la classe String repose sur l’algorithme:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
Bien qu’il y ait 1 chance sur 4294967296, deux objets différents peuvent avoir le même HashCode. Cette probabilité s’agrandit si le HashCode est mal conçu…
Théoriquement, pour deux objets o1 et o2,
- Si o1.equals(o2), alors o1.hashCode() == o2.hashCode()
- Si o1.hashCode() == o2.hashCode(), alors il n’est pas sur que o1.equals(02)
- Si o1.hashCode() != o2.hashCode() , alors o1.equals(o2) n’est pas vrai
Nous allons utiliser cette propriété afin de l’utiliser lors de nos tests de recherches.
Optimiser votre recherche sur une Collection.
Petit rappel sur les Collection. Collection est une interface Java définissant les objets comme un regroupement d’autres objets. Par exemple, ArrayList, HashMap, implémentent l’interface Collection.
Notre recherche se base sur le fait que nous avons un élément et nous allons essayer de retrouver un élément identique dans une collection.
Notre principe de recherche se base sur le fait que comparer deux hashcodes (qui sont des entiers) est plus rapide que de comparer deux objets avec equals(). Si les deux hashcodes sont identiques, on s’assurera de leur égalité avec la méthode equals(). Sinon, on testera l’objet suivant.
L’exemple suivant montre une implémentation de ce principe. Nous allons vérifier si un élément existe dans une collection.
- //on crée une collection déjà remplie
- maCollection.add("Five");
- maCollection.add("Fresh");
- maCollection.add("Minutes");
- maCollection.add("IT");
- maCollection.add("Blog");
- //on selection une String à rechercher.
- String stringRechercher = "IT";
- //on calcule à l'avance son HashCode
- int hashCodeDeStringRechercher = stringRechercher.hashCode();
- //flag
- boolean exists = false;
- //boucle
- //on teste le hashcode
- if (hashCodeDeStringRechercher == aTester.hashCode()) {
- //le hashcode est le meme, on regarde si les objets sont identiques
- if (stringRechercher.equals(aTester)) {
- exists = true;
- }
- }
- }
A lire:
- 7 pages sur la méthode hashCode()
- Cours sur les Collections en Java
- Javadoc de Collection
- Javadoc de java.lang.Object
- Autres cours sur les Collections.
juste un petitvcommentaire pour te dire que c’est très agréable e lire ton bloh
HashSet permet de profiter de ce genre d’optimisation.
Sinon, pour etre plus rapide, il faudrait arrêter la boucle dès que l’objet voulu est trouvé