Java hashCode()

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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 parfaite)[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[modifier | modifier le code]

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 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 ie caractère de la chaîne, et n la longueur de s[3], [4].

Références[modifier | modifier le code]

  1. java.lang.Object.hashCode() documentation, Java SE 1.5.0 documentation, Oracle Inc.
  2. a et b Joshua Bloch[réf. nécessaire]
  3. java.lang.String.hashCode() documentation, Java SE 1.5.0 documentation, Oracle Inc.
  4. Choice of hash function → The String hash function", Data Structures course notes (2006), Peter M Williams, University of Sussex School of Information

Liens externes[modifier | modifier le code]