Java Language Méthode hashCode ()


Exemple

Lorsqu'une classe Java remplace la méthode equals , elle devrait également remplacer la méthode hashCode . Comme défini dans le contrat de la méthode :

  • Chaque fois qu'il est appelé sur le même objet plus d'une fois lors de l'exécution d'une application Java, la méthode hashCode doit systématiquement renvoyer le même entier, à condition qu'aucune information utilisée dans les comparaisons d'égal à égal sur l'objet ne soit modifiée. Cet entier ne doit pas nécessairement rester cohérent d'une exécution d'une application à une autre exécution de la même application.
  • Si deux objets sont égaux selon la méthode equals(Object) , alors l'appel de la méthode hashCode sur chacun des deux objets doit produire le même résultat entier.
  • Il n'est pas obligatoire que si deux objets sont inégaux selon la méthode equals(Object) , alors l'appel de la méthode hashCode sur chacun des deux objets doit produire des résultats entiers distincts. Cependant, le programmeur doit savoir que produire des résultats entiers distincts pour des objets inégaux peut améliorer les performances des tables de hachage.

Les codes de hachage sont utilisés dans les implémentations de hachage telles que HashMap , HashTable et HashSet . Le résultat de la fonction hashCode détermine le compartiment dans lequel un objet sera placé. Ces implémentations de hachage sont plus efficaces si l'implémentation hashCode fournie est bonne. Une propriété importante de l'implémentation de hashCode est que la distribution des valeurs hashCode est uniforme. En d'autres termes, il existe une faible probabilité que de nombreuses instances soient stockées dans le même compartiment.

Un algorithme de calcul d'une valeur de code de hachage peut être similaire à celui-ci:

public class Foo {
    private int field1, field2;
    private String field3;

    public Foo(int field1, int field2, String field3) {
        this.field1 = field1;
        this.field2 = field2;
        this.field3 = field3;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }

        Foo f = (Foo) obj;
        return field1 == f.field1 &&
               field2 == f.field2 &&
               (field3 == null ? f.field3 == null : field3.equals(f.field3);
    }

    @Override
    public int hashCode() {
        int hash = 1;
        hash = 31 * hash + field1;
        hash = 31 * hash + field2;
        hash = 31 * hash + (field3 == null ? 0 : field3.hashCode());
        return hash;
    }
}

Utiliser Arrays.hashCode () comme raccourci

Java SE 1.2

Dans Java 1.2 et versions ultérieures, au lieu de développer un algorithme pour calculer un code de hachage, vous pouvez en générer un en utilisant java.util.Arrays#hashCode en fournissant un tableau Object ou primitives contenant les valeurs de champ:

@Override
public int hashCode() {
    return Arrays.hashCode(new Object[] {field1, field2, field3});
}
Java SE 7

Java 1.7 a introduit la classe java.util.Objects qui fournit une méthode pratique, hash(Object... objects) , qui calcule un code de hachage basé sur les valeurs des objets qui lui sont fournis. Cette méthode fonctionne comme java.util.Arrays#hashCode .

@Override
public int hashCode() {
    return Objects.hash(field1, field2, field3);
}

Remarque: cette approche est inefficace et produit des objets indésirables chaque fois que votre hashCode() personnalisée est appelée:

  • Un Object[] temporaire Object[] est créé. (Dans la version Objects.hash() , le tableau est créé par le mécanisme "varargs".)
  • Si l'un des champs est de type primitif, il doit être encadré et créer plus d'objets temporaires.
  • Le tableau doit être rempli.
  • Le tableau doit être itéré par la méthode Arrays.hashCode ou Objects.hash .
  • Les appels à Object.hashCode() Arrays.hashCode ou Objects.hash doit effectuer (probablement) ne peuvent pas être intégrés.

Mise en cache interne des codes de hachage

Étant donné que le calcul du code de hachage d'un objet peut être coûteux, il peut être intéressant de mettre en cache la valeur du code de hachage dans l'objet la première fois qu'il est calculé. Par exemple

public final class ImmutableArray {
    private int[] array;
    private volatile int hash = 0;

    public ImmutableArray(int[] initial) {
        array = initial.clone();
    }

    // Other methods

    @Override
    public boolean equals(Object obj) {
         // ...
    }

    @Override
    public int hashCode() {
        int h = hash;
        if (h == 0) {
            h = Arrays.hashCode(array);
            hash = h;
        }
        return h;
    }
}

Cette approche permet d'échanger le coût de (répétition) du calcul du code de hachage par rapport à la surcharge d'un champ supplémentaire pour mettre en cache le code de hachage. Que cela soit rentable en tant qu'optimisation des performances dépendra de la fréquence à laquelle un objet donné est haché (recherché) et d'autres facteurs.

Vous remarquerez également que si le vrai hashcode d'un ImmutableArray arrive à zéro (une chance sur 2 32), le cache est inefficace.

Enfin, cette approche est beaucoup plus difficile à implémenter correctement si l’objet que nous sommes en train de hacher est mutable. Cependant, il y a de plus grandes préoccupations si les codes de hachage changent; voir le contrat ci-dessus.