Accélerer vos tests et vos recherches avec hashCode()

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
		Collection maCollection = new ArrayList();
		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
		for (String aTester: maCollection) {
			//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;
				}
			}
		}
		System.out.println("L'element est présent? " + exists);

A lire:

  • juste un petitvcommentaire pour te dire que c’est très agréable e lire ton bloh 🙂

  • fred

    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é