Java hashCode()

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

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 ${\displaystyle h(s)}$ défini par ${\displaystyle 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, ${\displaystyle s[i]}$ représentant le ${\displaystyle i}$^e caractère de la chaîne, et ${\displaystyle n}$ la longueur de s[3] - [4].

• "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