Meilleure implémentation pour la méthode hashCode

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

    La meilleure implémentation? C’est une question difficile car cela dépend du modèle d’utilisation.

    Dans presque tous les cas, une bonne mise en œuvre raisonnable a été proposée dans le document Java efficace de Josh Bloch , au point 8 (deuxième édition). La meilleure chose est de chercher là-bas parce que l’auteur explique pourquoi l’approche est bonne.

    Une version courte

    1. Créez un int result et atsortingbuez une valeur différente de zéro .

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

      • Si le champ f est un boolean : calculer (f ? 0 : 1) ;
      • Si le champ f est un byte , char , short ou int : calculate (int)f ;
      • Si le champ f est un long : calculate (int)(f ^ (f >>> 32)) ;
      • Si le champ f est un float : calculer Float.floatToIntBits(f) ;
      • Si le champ f est un double : calculez Double.doubleToLongBits(f) et gérez la valeur de retour comme toute valeur longue;
      • Si le champ f est un object : Utilisez le résultat de la hashCode() ou 0 si f == null ;
      • Si le champ f est un tableau : voir chaque champ comme un élément distinct et calculer la valeur de hachage de manière récursive et combiner les valeurs comme décrit ci-après.
    3. Combinez la valeur de hachage c avec le result :

       result = 37 * result + c 
    4. result retour

    Cela devrait entraîner une dissortingbution correcte des valeurs de hachage pour la plupart des situations d’utilisation.

    Si vous êtes satisfait de l’implémentation Java efficace recommandée par dmeister, vous pouvez utiliser un appel de bibliothèque au lieu de lancer votre propre appel:

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

    Cela nécessite soit guava ( com.google.common.base.Objects.hashCode(...) ) ou JDK7 ( java.util.Objects.hash(...) ) mais fonctionne de la même manière.

    Il est préférable d’utiliser les fonctionnalités fournies par Eclipse, qui fait du très bon travail et vous pouvez consacrer vos efforts et votre énergie au développement de la logique métier.

    Bien que cela soit lié à la documentation Android (Wayback Machine) et à mon propre code sur Github , cela fonctionnera pour Java en général. Ma réponse est une extension de dmeister’s Answer avec juste un code 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; } 

    MODIFIER

    En règle générale, lorsque vous remplacez le hashcode(...) , vous souhaitez également remplacer equals(...) . Donc, pour ceux qui vont ou ont déjà mis en œuvre des 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)); } 

    Assurez-vous d’abord que égal est mis en œuvre correctement. A partir d’ un article IBM DeveloperWorks :

    • Symésortinge: 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 objects égaux doivent avoir la même valeur hashCode ()

    Enfin, une bonne fonction de hachage devrait s’appliquer à la fonction de hachage idéale .

    about8.blogspot.com, vous avez dit

    Si equals () renvoie true pour deux objects, hashCode () doit renvoyer la même valeur. Si equals () renvoie false, hashCode () doit renvoyer des valeurs différentes

    Je ne peux pas être d’accord avec vous. Si deux objects ont le même code de hachage, cela ne signifie pas nécessairement qu’ils sont égaux.

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

    mais

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

    Il existe une bonne implémentation de la logique hashcode() et equals() Java Efficace dans Apache Commons Lang . Checkout HashCodeBuilder et EqualsBuilder .

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

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

    A l’aide de cette fonction, vous pouvez choisir les champs que vous souhaitez utiliser pour l’égalité et le calcul du code de hachage, et Eclipse génère les méthodes correspondantes.

    Juste un petit mot pour compléter d’autres réponses plus détaillées (en terme de code):

    Si je considère la question comment-do-i-créer-un-hash-table-en-java et en particulier l’ entrée de la FAQ jGuru , je pense que d’autres critères sur lesquels un code de hachage pourrait être jugé sont:

    • la synchronisation (l’algo prend-il en charge l’access simultané ou non)?
    • 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 null dans la collection)

    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, alors vous n’avez pas à vous en préoccuper, il existe déjà une implémentation de equals () et hashCode () qui fonctionne en parcourant tous les objects et en ajoutant leurs hashCodes ().

      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 le meilleur moyen 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 égale:

     public int hashCode(){ return intMember ^ (ssortingngField != null ? ssortingngField.hashCode() : 0); } 

    @ about8: il y a un bug assez grave.

     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()).toSsortingng().hashCode(); 

    (pouvez-vous obtenir le hashCode directement depuis int en Java ces temps-ci? Je pense qu’il fait un autocasting .. si c’est le cas, passez le toSsortingng, c’est moche.)

    Comme vous l’avez demandé spécifiquement pour les collections, j’aimerais append un aspect que les autres réponses n’ont pas encore mentionné: Un HashMap ne s’attend pas à ce que ses clés modifient leur hashcode une fois qu’elles sont ajoutées à la collection. Vaincrait tout le but …

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

    toute méthode de hachage qui dissortingbue uniformément la valeur de hachage sur la plage possible est une bonne implémentation. Voir java efficace ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxiZw&hl=en&sa=X&oi=book_result&resnum=1&ct=result ), il y a un bon conseil là pour l’implémentation du hashcode (item 9 je pense …).

    Je préfère utiliser les méthodes utilitaires de Google Collections lib à partir d’objects de classe qui m’aident à garder mon code propre. Très souvent, les méthodes equals et les méthodes de hashcode sont hashcode partir du modèle de l’IDE, de sorte qu’elles ne sont pas propres à lire.

    J’utilise un petit wrapper autour d’ Arrays.deepHashCode(...) car il gère correctement les tableaux fournis en tant que parameters

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

    Voici une autre démonstration d’approche JDK 1.7+ avec des logiques de superclasses sockets en compte. Je le vois très pratique avec la classe Object hashCode () prise en compte, une dépendance JDK pure et aucun travail manuel supplémentaire. S’il vous plaît noter Objects.hash() est tolérant null.

    Je n’ai inclus aucune implémentation d’ equals() mais en réalité, vous en aurez bien besoin.

     import java.util.Objects; public class Demo { public static class A { private final Ssortingng param1; public A(final Ssortingng param1) { this.param1 = param1; } @Override public int hashCode() { return Objects.hash( super.hashCode(), this.param1); } } public static class B extends A { private final Ssortingng param2; private final Ssortingng param3; public B( final Ssortingng param1, final Ssortingng param2, final Ssortingng 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(Ssortingng [] 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()); } } 

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

     class ListPair { List first; List second; ListPair(List first, List second) { this.first = first; this.second = second; } public int hashCode() { return Objects.hashCode(first, second); } ... } 

    À présent,

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

    et

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

    avoir le même hashCode , à savoir 31*(a+b) + c car le multiplicateur utilisé pour List.hashCode est 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 à propos de l’utilisation de 31 . Le multiplicateur doit être impair pour éviter de perdre des informations (tout multiplicateur pair perd au moins le bit le plus significatif, des multiples de quatre 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 importe peu. Les petits multiplicateurs entraînent également davantage de collisions pour les petites entrées, ce qui peut parfois poser problème.

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

    Donc, je recommande d’utiliser un grand nombre impair choisi au hasard (n’hésitez pas à prendre un prime). Comme les processeurs i86 / amd64 peuvent utiliser une instruction plus courte pour les opérandes se trouvant dans un seul octet signé, il existe un avantage de vitesse minime pour les multiplicateurs tels que 109. Pour minimiser les collisions, prenez quelque chose comme 0x58a54cf5.

    Utiliser différents multiplicateurs à différents endroits est utile, mais probablement pas suffisant pour justifier le travail supplémentaire.

    En combinant des 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 dissortingbution uniforme. Pour plus d’informations sur le fonctionnement de cette formule, voir l’article de StackOverflow: Magic number in boost :: hash_combine

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

    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 Ssortingng foo; private Ssortingng bar; private Ssortingng 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 Ssortingng getFoo() { return foo; } public Ssortingng getBar() { return bar; } } 

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