Java hashCode()

Dans le Langage de programmation Java , chaque classe doit mettre en oeuvre une méthode hashCode() qui digère les données stoké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'autre code lors du stockage ou de la manipulation de l'instance - les valeurs visent à être répartie 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 classe 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 oeuvre doivent surcharger la méthode public int hashCode().

Le contrat général pour surcharger la mise en oeuvre 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 oeuvre 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 oeuvre ne requiére pas d'être une fonction de hachage parfaite).

Par exemple, la classe Employe peut mettre en oeuvre sa fonction de hachage via un 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 oeuvre rapide, les premières versions de la classe String en Java fournissait une version de la méthode hashCode() qui ne condidérait au plus 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 performandes médiocres pour les tables de hachage.

En Java 1.2, la classe java.lang.String a mis en oeuvre sa méthode hashCode() en utilisant un algorithme de somme de produits sur le texte entier de la chaîne. Si on considére une instance s de la classe java.lang.String, par exemple, elle aurait un code de hachage $h(s)$ défini par

$h(s)=\sum _{i=0}^{n-1}s[i]\cdot 31^{n-1-i}$

oû les termes sont additionnés en utilisant une addition int Java 32-bit, $s[i]$ représentant le $i$^ème caractère de la chaîne, et $n$ la longueur de s.

Références

• "Always override hashCode when you override equals" in « {{{1}}} »

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