Java hashCode()
Dans le langage de programmation Java, chaque classe doit mettre en œuvre une méthode hashCode()
qui digère les données stockées dans une instance de la classe dans une valeur de hachage (en un entier signé 32-bit). Cette valeur de hachage est utilisée par d'autres codes lors du stockage ou de la manipulation de l'instance - les valeurs visent à être réparties de manière homogène pour différentes entrées de manière à être utilisées en agglomération. Cette propriété est importante pour les performances des tables de hachage et autres structures de données qui stockent des objets en groupes ("agglomérats") en fonction de leurs valeurs de hachage.
hashCode() en général
Toutes les classes héritent d'un schéma basique de hachage de la classe de base java.lang.Object, mais beaucoup le surchargent afin de fournir une fonction de hachage qui gère mieux leurs données spécifiques. Les classes fournissant leur propre mise en œuvre doivent redéfinir la méthode public int hashCode().
Le contrat général pour redéfinir la mise en œuvre de cette méthode est qu'elle se comporte de manière homogène avec la méthode equals() du même objet : un objet donné doit retourner la même valeur de hachage (à moins qu'il ait subi des modifications impliquant que la nouvelle version ne soit plus considérée comme "égale" à la précédente), et que deux objets pour lesquels la méthode equals() renvoie true doivent renvoyer la même valeur de hachage. Il n'y a aucune exigence à ce que les valeurs de hachage soient cohérentes entre des mises en œuvre Java différentes, ou même entre deux exécutions successives du même programme, et même s'il est souhaitable que deux objets distincts aient des valeurs de hachage distinctes, cela n'est pas obligatoire (c'est-à-dire que la fonction de hachage mise en œuvre ne requiert pas d'être une fonction de hachage parfait)[1].
Par exemple, la classe Employe peut mettre en œuvre sa fonction de hachage via une composition des valeurs de hachage de ses membres :
public class Employe {
int idEmploye;
String nom;
Departement dept;
// d'autres méthodes sont normalement présentes ici
@Override
public int hashCode() {
int hash = 1;
hash = hash * 17 + idEmploye;
hash = hash * 31 + nom.hashCode();
hash = hash * 13 + (dept == null ? 0 : dept.hashCode());
return hash;
}
}
La fonction de hachage de la classe java.lang.String
Visant à fournir une mise en œuvre rapide, les premières versions de la classe String en Java fournissait une version de la méthode hashCode() qui ne considérait au plus que 16 caractères choisis parmi la chaîne. Pour certaines données standard cela fonctionnait mal, générant de manière inacceptable des résultats agglomérés et par conséquent des performances médiocres pour les tables de hachage[2].
En Java 1.2, la classe java.lang.String a mis en œuvre sa méthode hashCode() en utilisant un algorithme de somme de produits sur le texte entier de la chaîne[2]. Si on considère une instance s
de la classe java.lang.String
, par exemple, elle aurait un code de hachage défini par
où les termes sont additionnés en utilisant une addition int
Java 32-bit, représentant le e caractère de la chaîne, et la longueur de s
[3],
[4].
Références
- java.lang.Object.hashCode() documentation, Java SE 1.5.0 documentation, Oracle Inc.
- Joshua Bloch[réf. nécessaire]
- java.lang.String.hashCode() documentation, Java SE 1.5.0 documentation, Oracle Inc.
- Choice of hash function → The String hash function", Data Structures course notes (2006), Peter M Williams, University of Sussex School of Information
Liens externes
- "Java theory and practice: Hashing it out", Brian Goetz, IBM Developer Works article, 27 May 2003
- "How the String hash function works (and implications for other hash functions)", Neil Coffey, Javamex