Meilleure implémentation de la méthode hashCode pour une collection

299

Comment décidons-nous de la meilleure implémentation de la hashCode()méthode pour une collection (en supposant que la méthode equals a été remplacée correctement)?

Omnipotent
la source
2
avec Java 7+, je suppose que cela Objects.hashCode(collection)devrait être une solution parfaite!
Diablo
3
@Diablo Je ne pense pas que cela réponde à la question - cette méthode revient simplement collection.hashCode()( hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/… )
cbreezier

Réponses:

438

La meilleure mise en œuvre? C'est une question difficile car elle dépend du modèle d'utilisation.

Dans presque tous les cas, une bonne mise en œuvre raisonnable a été proposée dans Josh Bloch 's Effective Java dans le point 8 (deuxième édition). Le mieux est de le chercher là-haut car l'auteur y explique pourquoi l'approche est bonne.

Une version courte

  1. Créez un int resultet attribuez une valeur non nulle .

  2. Pour chaque champ f testé dans la equals()méthode, calculez un code de hachage cpar:

    • Si le champ f est a boolean: calculer (f ? 0 : 1);
    • Si le f champ est byte, char, shortou int: calculer (int)f;
    • Si le champ f est a long: calculer (int)(f ^ (f >>> 32));
    • Si le champ f est a float: calculer Float.floatToIntBits(f);
    • Si le champ f est a double: calculez Double.doubleToLongBits(f)et gérez la valeur de retour comme chaque valeur longue;
    • Si le champ f est un objet : utilisez le résultat de la hashCode()méthode ou 0 si f == null;
    • Si le champ f est un tableau : voyez chaque champ comme un élément distinct et calculez la valeur de hachage de manière récursive et combinez les valeurs comme décrit ci-dessous.
  3. Combinez la valeur de hachage cavec result:

    result = 37 * result + c
  4. Revenir result

Cela devrait se traduire par une distribution correcte des valeurs de hachage pour la plupart des situations d'utilisation.

dmeister
la source
45
Ouais, je suis particulièrement curieux de savoir d'où vient le numéro 37.
Kip
17
J'ai utilisé le point 8 du livre "Effective Java" de Josh Bloch.
dmeister
39
@dma_k La raison d'utiliser des nombres premiers et la méthode décrite dans cette réponse est de s'assurer que le code de hachage calculé sera unique . Lorsque vous utilisez des nombres non premiers, vous ne pouvez pas le garantir. Peu importe le nombre premier que vous choisissez, le nombre 37 n'a rien de magique (dommage 42 n'est pas un nombre premier, hein?)
Simon Forsberg
34
@ SimonAndréForsberg Eh bien, le code de hachage calculé ne peut pas toujours être unique :) Est un code de hachage. Cependant, j'ai eu l'idée: le nombre premier n'a qu'un seul multiplicateur, tandis que le non premier en a au moins deux. Cela crée une combinaison supplémentaire pour l'opérateur de multiplication pour obtenir le même hachage, c'est-à-dire provoquer une collision.
dma_k
140

Si vous êtes satisfait de l'implémentation effective de Java recommandée par dmeister, vous pouvez utiliser un appel de bibliothèque au lieu de lancer le vôtre:

@Override
public int hashCode() {
    return Objects.hashCode(this.firstName, this.lastName);
}

Cela nécessite Guava ( com.google.common.base.Objects.hashCode) ou la bibliothèque standard de Java 7 ( java.util.Objects.hash) mais fonctionne de la même manière.

bacar
la source
8
À moins que l'on ait une bonne raison de ne pas les utiliser, il faut absolument les utiliser dans tous les cas. (Formuler plus fort, car il devrait être formulé à mon humble avis.) Les arguments typiques pour l'utilisation des implémentations / bibliothèques standard s'appliquent (meilleures pratiques, bien testées, moins sujettes aux erreurs, etc.).
Kissaki
7
@ justin.hughey vous semblez confus. Le seul cas que vous devez remplacer hashCodeest si vous avez une coutume equals, et c'est précisément pour cela que ces méthodes de bibliothèque sont conçues. La documentation est assez claire sur leur comportement par rapport à equals. Une implémentation de bibliothèque ne prétend pas vous dispenser de connaître les caractéristiques d'une hashCodeimplémentation correcte - ces bibliothèques vous facilitent la mise en œuvre d'une telle implémentation conforme pour la majorité des cas où elle equalsest remplacée.
bacar
6
Pour tous les développeurs Android qui consultent la classe java.util.Objects, elle n'a été introduite que dans l'API 19, alors assurez-vous que vous exécutez sur KitKat ou supérieur, sinon vous obtiendrez NoClassDefFoundError.
Andrew Kelly
3
Meilleure réponse OMI, bien qu'à titre d'exemple j'aurais préféré choisir la java.util.Objects.hash(...)méthode JDK7 plutôt que la com.google.common.base.Objects.hashCode(...)méthode goyave . Je pense que la plupart des gens choisiraient la bibliothèque standard plutôt qu'une dépendance supplémentaire.
Malte Skoruppa,
2
S'il y a deux arguments ou plus et si l'un d'eux est un tableau, le résultat peut ne pas être ce que vous attendez car hashCode()pour un tableau est juste le sien java.lang.System.identityHashCode(...).
starikoff
59

Il est préférable d'utiliser les fonctionnalités fournies par Eclipse qui font un très bon travail et vous pouvez mettre vos efforts et votre énergie dans le développement de la logique métier.

guerrier
la source
4
+1 Une bonne solution pratique. La solution de dmeister est plus complète, mais j'ai tendance à oublier de gérer les valeurs nulles lorsque j'essaie d'écrire moi-même des codes de hachage.
Quantum7
1
+1 D'accord avec Quantum7, mais je dirais que c'est aussi très bien de comprendre ce que fait l'implémentation générée par Eclipse, et d'où elle obtient ses détails d'implémentation.
jwir3
15
Désolé, mais les réponses concernant les "fonctionnalités fournies par [certains IDE]" ne sont pas vraiment pertinentes dans le contexte du langage de programmation en général. Il existe des dizaines d'IDE et cela ne répond pas à la question ... notamment parce qu'il s'agit davantage de détermination algorithmique et directement associé à l'implémentation d'equals () - quelque chose qu'un IDE ne saura rien.
Darrell Teague
57

Bien que cela soit lié à la Androiddocumentation (Wayback Machine) et à mon propre code sur Github , cela fonctionnera pour Java en général. Ma réponse est une extension de la réponse de dmeister avec juste du code qui est beaucoup plus facile à lire et à comprendre.

@Override 
public int hashCode() {

    // Start with a non-zero constant. Prime is preferred
    int result = 17;

    // Include a hash for each field.

    // Primatives

    result = 31 * result + (booleanField ? 1 : 0);                   // 1 bit   » 32-bit

    result = 31 * result + byteField;                                // 8 bits  » 32-bit 
    result = 31 * result + charField;                                // 16 bits » 32-bit
    result = 31 * result + shortField;                               // 16 bits » 32-bit
    result = 31 * result + intField;                                 // 32 bits » 32-bit

    result = 31 * result + (int)(longField ^ (longField >>> 32));    // 64 bits » 32-bit

    result = 31 * result + Float.floatToIntBits(floatField);         // 32 bits » 32-bit

    long doubleFieldBits = Double.doubleToLongBits(doubleField);     // 64 bits (double) » 64-bit (long) » 32-bit (int)
    result = 31 * result + (int)(doubleFieldBits ^ (doubleFieldBits >>> 32));

    // Objects

    result = 31 * result + Arrays.hashCode(arrayField);              // var bits » 32-bit

    result = 31 * result + referenceField.hashCode();                // var bits » 32-bit (non-nullable)   
    result = 31 * result +                                           // var bits » 32-bit (nullable)   
        (nullableReferenceField == null
            ? 0
            : nullableReferenceField.hashCode());

    return result;

}

ÉDITER

En règle générale, lorsque vous remplacez hashcode(...), vous souhaitez également remplacer equals(...). Donc pour ceux qui le feront ou l'ont déjà implémenté equals, voici une bonne référence de mon Github ...

@Override
public boolean equals(Object o) {

    // Optimization (not required).
    if (this == o) {
        return true;
    }

    // Return false if the other object has the wrong type, interface, or is null.
    if (!(o instanceof MyType)) {
        return false;
    }

    MyType lhs = (MyType) o; // lhs means "left hand side"

            // Primitive fields
    return     booleanField == lhs.booleanField
            && byteField    == lhs.byteField
            && charField    == lhs.charField
            && shortField   == lhs.shortField
            && intField     == lhs.intField
            && longField    == lhs.longField
            && floatField   == lhs.floatField
            && doubleField  == lhs.doubleField

            // Arrays

            && Arrays.equals(arrayField, lhs.arrayField)

            // Objects

            && referenceField.equals(lhs.referenceField)
            && (nullableReferenceField == null
                        ? lhs.nullableReferenceField == null
                        : nullableReferenceField.equals(lhs.nullableReferenceField));
}
Christopher Rucinski
la source
1
La documentation Android n'inclut plus le code ci-dessus, voici donc une version mise en cache de Wayback Machine - Documentation Android (7 février 2015)
Christopher Rucinski
17

Assurez-vous d'abord qu'equals est correctement implémenté. Extrait d' un article IBM DeveloperWorks :

  • Symétrie: pour deux références, a et b, a.equals (b) si et seulement si b.equals (a)
  • Réflexivité: pour toutes les références non nulles, a.equals (a)
  • Transitivité: si a.equals (b) et b.equals (c), alors a.equals (c)

Assurez-vous ensuite que leur relation avec hashCode respecte le contact (du même article):

  • Cohérence avec hashCode (): deux objets égaux doivent avoir la même valeur hashCode ()

Enfin, une bonne fonction de hachage doit s'efforcer d'approcher la fonction de hachage idéale .

Panthère grise
la source
11

about8.blogspot.com, vous avez dit

si equals () retourne vrai pour deux objets, hashCode () devrait retourner la même valeur. Si equals () retourne false, hashCode () devrait retourner des valeurs différentes

Je ne peux pas être d'accord avec toi. Si deux objets ont le même hashcode, cela ne signifie pas nécessairement qu'ils sont égaux.

Si A est égal à B, A.hashcode doit être égal à B.hascode

mais

si A.hashcode est égal à B.hascode, cela ne signifie pas que A doit être égal à B

Attila
la source
3
Si (A != B) and (A.hashcode() == B.hashcode()), c'est ce que nous appelons collision de fonctions de hachage. C'est parce que le domaine de codage de la fonction de hachage est toujours fini, alors que son domaine ne l'est généralement pas. Plus le codomaine est grand, moins la collision doit se produire. Une bonne fonction de hachage devrait renvoyer différents hachages pour différents objets avec la plus grande possibilité réalisable étant donné la taille particulière du domaine de codage. Cependant, il peut rarement être entièrement garanti.
Krzysztof Jabłoński
Cela ne devrait être qu'un commentaire du message ci-dessus pour Gray. De bonnes informations mais cela ne répond pas vraiment à la question
Christopher Rucinski
De bons commentaires, mais soyez prudent lorsque vous utilisez le terme «différents objets» ... parce que equals () et donc l'implémentation de hashCode () ne concernent pas nécessairement différents objets dans un contexte OO mais sont généralement plus sur leurs représentations de modèle de domaine (par exemple, deux les gens peuvent être considérés comme les mêmes s'ils partagent un code de pays et un ID de pays - bien qu'il puisse s'agir de deux `` objets '' différents dans une machine virtuelle Java - ils sont considérés comme `` égaux '' et ayant un code de hachage donné) ...
Darrell Teague
7

Si vous utilisez eclipse, vous pouvez générer equals()et hashCode()utiliser:

Source -> Générer hashCode () et equals ().

En utilisant cette fonction, vous pouvez décider quels champs vous souhaitez utiliser pour l'égalité et le calcul du code de hachage, et Eclipse génère les méthodes correspondantes.

Johannes K. Lehnert
la source
7

Il y a une bonne mise en œuvre du Effective Java de hashcode()et equals()logique dans Apache Commons Lang . Commander HashCodeBuilder et EqualsBuilder .

Rudi Adianto
la source
1
L'inconvénient de cette API est que vous payez le coût de la construction d'objet chaque fois que vous appelez equals et hashcode (sauf si votre objet est immuable et que vous précalculez le hachage), ce qui peut être beaucoup dans certains cas.
James McMahon
c'était mon approche préférée, jusqu'à récemment. J'ai rencontré StackOverFlowError en utilisant un critère pour l'association SharedKey OneToOne. De plus, la Objectsclasse fournit des hash(Object ..args)& equals()méthodes à partir de Java7. Ceux-ci sont recommandés pour toutes les applications utilisant jdk 1.7+
Diablo
@Diablo Je suppose que votre problème était un cycle dans le graphique d'objet et que vous n'avez pas de chance avec la plupart des implémentations car vous devez ignorer une référence ou briser le cycle (en imposant un IdentityHashMap). FWIW J'utilise un hashCode basé sur l'ID et est égal à toutes les entités.
maaartinus
6

Juste une note rapide pour compléter une autre réponse plus détaillée (en termes de code):

Si je considère la question de savoir comment créer une table de hachage en Java et en particulier l' entrée FAQ jGuru , je pense que d'autres critères sur lesquels un code de hachage pourrait être jugé sont:

  • synchronisation (l'algo prend-il en charge l'accès simultané ou non)?
  • échec de l'itération sécurisée (l'algo détecte-t-il une collection qui change pendant l'itération)
  • valeur nulle (le code de hachage prend-il en charge la valeur nulle dans la collection)
VonC
la source
4

Si je comprends bien votre question, vous avez une classe de collection personnalisée (c'est-à-dire une nouvelle classe qui s'étend de l'interface Collection) et vous souhaitez implémenter la méthode hashCode ().

Si votre classe de collection étend AbstractList, vous n'avez pas à vous en préoccuper, il existe déjà une implémentation de equals () et hashCode () qui fonctionne en itérant à travers tous les objets et en ajoutant leurs hashCodes () ensemble.

   public int hashCode() {
      int hashCode = 1;
      Iterator i = iterator();
      while (i.hasNext()) {
        Object obj = i.next();
        hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
      }
  return hashCode;
   }

Maintenant, si ce que vous voulez est la meilleure façon de calculer le code de hachage pour une classe spécifique, j'utilise normalement l'opérateur ^ (bitwise exclusif ou) pour traiter tous les champs que j'utilise dans la méthode equals:

public int hashCode(){
   return intMember ^ (stringField != null ? stringField.hashCode() : 0);
}
Mario Ortegón
la source
2

@ about8: il y a là un bug assez sérieux.

Zam obj1 = new Zam("foo", "bar", "baz");
Zam obj2 = new Zam("fo", "obar", "baz");

même hashcode

vous voulez probablement quelque chose comme

public int hashCode() {
    return (getFoo().hashCode() + getBar().hashCode()).toString().hashCode();

(pouvez-vous obtenir hashCode directement depuis int en Java ces jours-ci? Je pense qu'il fait une diffusion automatique .. si c'est le cas, sautez la toString, c'est moche.)

SquareCog
la source
3
le bogue se trouve dans la réponse longue de about8.blogspot.com - obtenir le code de hachage à partir d'une concaténation de chaînes vous laisse une fonction de hachage qui est la même pour toute combinaison de chaînes qui s'ajoutent à la même chaîne.
SquareCog
1
C'est donc une méta-discussion et pas du tout liée à la question? ;-)
Huppie
1
Il s'agit d'une correction apportée à une réponse proposée qui présente un défaut assez important.
SquareCog
Il s'agit d'une mise en œuvre très limitée
Christopher Rucinski
Votre implémentation évite le problème et en introduit un autre; Échange fooet barconduit à la même chose hashCode. Votre toStringAFAIK ne compile pas, et si c'est le cas, alors il est terriblement inefficace. Quelque chose comme 109 * getFoo().hashCode() + 57 * getBar().hashCode()est plus rapide, plus simple et ne produit aucune collision inutile.
maaartinus
2

Comme vous l'avez spécifiquement demandé pour les collections, j'aimerais ajouter un aspect que les autres réponses n'ont pas encore mentionné: Un HashMap ne s'attend pas à ce que ses clés changent leur code de hachage une fois qu'elles sont ajoutées à la collection. Serait contraire à l'objectif ...

Olaf Kock
la source
2

Utilisez les méthodes de réflexion sur Apache Commons EqualsBuilder et HashCodeBuilder .

Vihung
la source
1
Si vous comptez l'utiliser, sachez que la réflexion coûte cher. Honnêtement, je ne l'utiliserais pas pour autre chose que de jeter du code.
James McMahon
2

J'utilise un petit wrapper Arrays.deepHashCode(...)car il gère correctement les tableaux fournis comme paramètres

public static int hash(final Object... objects) {
    return Arrays.deepHashCode(objects);
}
starikoff
la source
1

Je préfère utiliser les méthodes utilitaires de Google Collections lib de la classe Objects qui m'aident à garder mon code propre. Très souvent equals, les hashcodeméthodes sont faites à partir du modèle IDE, donc elles ne sont pas propres à lire.

nbro
la source
1

Voici une autre démonstration de l'approche JDK 1.7+ avec les logiques de superclasse prises en compte. Je le vois comme assez pratique avec la classe Object hashCode (), une pure dépendance JDK et aucun travail manuel supplémentaire. Veuillez noter que la Objects.hash()tolérance est nulle.

Je n'ai inclus aucune equals()implémentation mais en réalité vous en aurez bien sûr besoin.

import java.util.Objects;

public class Demo {

    public static class A {

        private final String param1;

        public A(final String param1) {
            this.param1 = param1;
        }

        @Override
        public int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param1);
        }

    }

    public static class B extends A {

        private final String param2;
        private final String param3;

        public B(
            final String param1,
            final String param2,
            final String param3) {

            super(param1);
            this.param2 = param2;
            this.param3 = param3;
        }

        @Override
        public final int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param2,
                this.param3);
        }
    }

    public static void main(String [] args) {

        A a = new A("A");
        B b = new B("A", "B", "C");

        System.out.println("A: " + a.hashCode());
        System.out.println("B: " + b.hashCode());
    }

}
Roman Nikitchenko
la source
1

L'implémentation standard est faible et son utilisation entraîne des collisions inutiles. Imaginez un

class ListPair {
    List<Integer> first;
    List<Integer> second;

    ListPair(List<Integer> first, List<Integer> second) {
        this.first = first;
        this.second = second;
    }

    public int hashCode() {
        return Objects.hashCode(first, second);
    }

    ...
}

Maintenant,

new ListPair(List.of(a), List.of(b, c))

et

new ListPair(List.of(b), List.of(a, c))

ont la même chose hashCode, à savoir 31*(a+b) + cque le multiplicateur utilisé pour List.hashCodeest réutilisé ici. De toute évidence, les collisions sont inévitables, mais produire des collisions inutiles est tout simplement ... inutile.

Il n'y a rien de vraiment intelligent à utiliser 31. Le multiplicateur doit être impair afin d'éviter de perdre des informations (tout multiplicateur pair perd au moins le bit le plus significatif, des multiples de quatre en perdent deux, etc.). Tout multiplicateur impair est utilisable. Les petits multiplicateurs peuvent conduire à un calcul plus rapide (le JIT peut utiliser des décalages et des ajouts), mais étant donné que la multiplication a une latence de seulement trois cycles sur Intel / AMD moderne, cela n'a guère d'importance. Les petits multiplicateurs entraînent également plus de collision pour les petites entrées, ce qui peut parfois être un problème.

L'utilisation d'un nombre premier est inutile car les nombres premiers n'ont aucune signification dans l'anneau Z / (2 ** 32).

Donc, je recommanderais d'utiliser un grand nombre impair choisi au hasard (n'hésitez pas à prendre un nombre premier). Comme les processeurs i86 / amd64 peuvent utiliser une instruction plus courte pour les opérandes s'inscrivant dans un seul octet signé, il y a un avantage de vitesse minuscule pour les multiplicateurs comme 109. Pour minimiser les collisions, prenez quelque chose comme 0x58a54cf5.

L'utilisation de multiplicateurs différents à différents endroits est utile, mais probablement pas suffisante pour justifier le travail supplémentaire.

maaartinus
la source
0

Lors de la combinaison de valeurs de hachage, j'utilise généralement la méthode de combinaison utilisée dans la bibliothèque boost c ++, à savoir:

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

Cela fait un assez bon travail pour assurer une distribution uniforme. Pour une discussion sur le fonctionnement de cette formule, voir le post StackOverflow: Nombre magique dans boost :: hash_combine

Il y a une bonne discussion sur les différentes fonctions de hachage sur: http://burtleburtle.net/bob/hash/doobs.html

Edward Loper
la source
1
C'est une question sur Java, pas sur C ++.
dano
-1

Pour une classe simple, il est souvent plus facile d'implémenter hashCode () en fonction des champs de classe qui sont vérifiés par l'implémentation equals ().

public class Zam {
    private String foo;
    private String bar;
    private String somethingElse;

    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        if (obj == null) {
            return false;
        }

        if (getClass() != obj.getClass()) {
            return false;
        }

        Zam otherObj = (Zam)obj;

        if ((getFoo() == null && otherObj.getFoo() == null) || (getFoo() != null && getFoo().equals(otherObj.getFoo()))) {
            if ((getBar() == null && otherObj. getBar() == null) || (getBar() != null && getBar().equals(otherObj. getBar()))) {
                return true;
            }
        }

        return false;
    }

    public int hashCode() {
        return (getFoo() + getBar()).hashCode();
    }

    public String getFoo() {
        return foo;
    }

    public String getBar() {
        return bar;
    }
}

La chose la plus importante est de garder cohérents hashCode () et equals (): si equals () renvoie true pour deux objets, alors hashCode () devrait retourner la même valeur. Si equals () retourne false, hashCode () devrait retourner des valeurs différentes.

Chris Carruthers
la source
1
Comme SquareCog l'ont déjà remarqué. Si hashcode est généré une fois de concaténation de deux chaînes , il est extrêmement facile de générer des masses de collisions: ("abc"+""=="ab"+"c"=="a"+"bc"==""+"abc"). C'est un défaut grave. Il serait préférable d'évaluer le code de hachage pour les deux champs, puis de calculer leur combinaison linéaire (de préférence en utilisant des nombres premiers comme coefficients).
Krzysztof Jabłoński
@ KrzysztofJabłoński Droite. De plus, l'échange fooet barproduit également une collision inutile.
maaartinus