Beste Implementierung für hashCode Methode für eine Sammlung

Question

Wie wir über die beste Umsetzung der hashCode() Methode für eine Sammlung entscheiden (unter der Annahme, dass gleich Methode überschrieben wurde korrekt)?

Answer 1

Die beste Umsetzung? Das ist eine schwierige Frage, weil es auf dem Nutzungsmuster abhängt.

A für fast alle Fälle angemessen gute Umsetzung in vorgeschlagen wurde Josh Bloch 's Effective Java in Punkt 8 (zweite Auflage). Das Beste ist, es dort zu sehen, weil der Autor es erklärt, warum der Ansatz gut ist.

Eine Kurzversion

1. ein int result erstellen und Nicht-Null Wert zuweisen.

2. Für jedes Feld f im equals() Methode getestet, berechnet eine Hash-Code c durch:

   • Wenn das Feld f ein boolean: berechnen (f ? 0 : 1);
   • Wenn das Feld f ein byte, char, short oder int ist: berechnen (int)f;
   • Wenn das Feld f ein long ist: berechnen (int)(f ^ (f >>> 32));
   • Wenn das Feld f ein float ist: berechnen Float.floatToIntBits(f);
   • Wenn das Feld f ein double ist: Double.doubleToLongBits(f) berechnen und den Rückgabewert wie jeder Long-Wert behandeln;
   • Wenn das Feld f ein ist Objekt : Verwenden Sie das Ergebnis der hashCode() Methode oder 0, wenn f == null;
   • Wenn das Feld f ein array . Jedes Feld als separates Element sehen und den Hash-Wert in einem rekursiv berechnet und die Werte kombinieren, wie im Folgenden beschrieben

3. den Hash-Wert c mit result Kombinieren Sie:

   result = 37 * result + c
   

4. Zurück result

Dies sollte in einer richtigen Verteilung von Hash-Werten für die meisten Anwendungssituationen führt.

Answer 2

Wenn Sie mit dem Effective Java-Implementierung von dmeister empfohlen zufrieden sind, können Sie eine Bibliothek-Aufruf statt rollen Sie Ihre eigenen:

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

Dies erfordert entweder Guava (com.google.common.base.Objects.hashCode) oder die Standard-Bibliothek in Java 7 (java.util.Objects.hash) aber funktioniert auf die gleiche Art und Weise.

Answer 3

Es ist besser, die Funktionalität von Eclipse-zu nutzen, die einen ziemlich guten Job macht und Sie können Ihre Bemühungen und Energie in die Entwicklung der Geschäftslogik setzen.

Answer 4

Obwohl dies im Zusammenhang mit Android Dokumentation (Wayback Machine) und Mein eigener Code auf Github , wird es für Java in der Regel arbeiten. Meine Antwort ist eine Erweiterung des dmeister Antwort- mit nur Code, der viel einfacher zu lesen und zu verstehen.

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

}

Bearbeiten

Normalerweise, wenn Sie hashcode(...) außer Kraft setzen, möchten Sie auch equals(...) außer Kraft zu setzen. Also für diejenigen, die wird oder bereits equals umgesetzt hat, ist hier eine gute Referenz von meinem 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));
}

Answer 5

Stellen Sie zunächst sicher, dass gleich richtig umgesetzt wird. Aus einen IBM Developer Artikel :

  

  
• Symmetry: Für zwei Referenzen, a und b, a.equals (b) wenn und nur wenn b.equals (a)
  
• Reflexivität: Für alle Nicht-Null-Referenzen, a.equals (a)
  
• Transitivität: Wenn a.equals (b) und b.equals (c), dann a.equals (c)
  

Dann stellen Sie sicher, dass ihre Beziehung mit hashCode den Kontakt respektiert (aus dem gleichen Artikel):

  

  
• Konsistenz mit hashCode (): Zwei gleiche Objekte müssen die gleiche hashCode () Wert
  

Endlich eine gute Hash-Funktion sollte sich bemühen, die ideale Hashfunktion zu nähern.

Answer 6

about8.blogspot.com, sagen Sie

  

, wenn equals () liefert true für zwei Objekte, dann hashCode () sollte den gleichen Wert zurück. Wenn equals () false zurückgibt, dann hashCode () sollten unterschiedliche Werte zurückgeben

Ich kann Ihnen nicht zustimmen. Wenn zwei Objekte den gleichen Hash-Code haben muss es nicht bedeuten, dass sie gleich sind.

Wenn A gleich B muss A.hashcode zu B.hascode gleich

und

Wenn A.hashcode gleich B.hascode es bedeutet nicht, dass A muss gleich B

Answer 7

Wenn Sie Eclipse verwenden, können Sie erzeugen equals() und hashCode() mit:

  

Quelle -> Generate hashCode () und equals ().

Mit dieser Funktion können Sie entscheiden, , welche Felder Sie wollen für die Gleichstellung und Hash-Code-Berechnung verwenden, und Eclipse generiert die entsprechenden Methoden.

Answer 8

Es gibt eine gute Umsetzung der Effective Java 's hashcode() und equals() Logik in Apache Commons Lang . Kasse HashCodeBuilder und Equals .

Answer 9

Nur eine kurze Notiz für andere ausführlichere Antwort Abschluss (in der Bezeichnung des Code):

Wenn ich halte die Frage wie-do-i- Create-A-hash-table-in-Java und vor allem der jGuru FAQ-Eintrag , ich glaube, einige andere Kriterien, nach denen ein Hash-Code sind beurteilt werden könnte:

• Synchronisation (funktioniert die algo Unterstützung gleichzeitigen Zugriff oder nicht)?
• fail safe Iteration (nicht die algo eine Sammlung erfassen, die während der Iteration ändert)
• Null-Wert (funktioniert der Hash-Code Unterstützung Nullwert in der Sammlung)

Answer 10

Wenn ich Ihre Frage richtig verstanden hat, haben Sie eine benutzerdefinierte Auflistungsklasse (das heißt eine neue Klasse, die von der Collection-Schnittstelle erweitert), und Sie wollen die hashCode () -Methode implementieren.

Wenn Sie Ihre Sammlung Klasse AbstractList erstreckt, dann müssen Sie nicht darum kümmern, gibt es bereits eine Implementierung von equals () und hashCode (), die durch Iteration durch alle Objekte funktioniert und ihre Hashcodes Zugabe () zusammen.

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

Nun, wenn was Sie wollen, ist der beste Weg ist, den Hash-Code für eine bestimmte Klasse zu berechnen, verwende ich normalerweise die ^ (bitweise Exklusiv oder) Operator alle Felder zu verarbeiten, die ich in der equals-Methode verwenden:

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

Answer 11

@ about8: Es gibt einen ziemlich ernst es Fehler.

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

gleicher Hash-Code

Sie wollen wahrscheinlich etwas wie

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

(können Sie hashCode direkt von int in Java bekommen in diesen Tagen? Ich denke, es ist etwas autocasting tut .. wenn das der Fall ist, lassen Sie die toString, es ist hässlich.)

Answer 12

Wie Sie speziell für Sammlungen gefragt, würde Ich mag einen Aspekt hinzufügen, dass die anderen Antworten noch nicht erwähnt: A HashMap erwartet nicht ihre Schlüssel ihren Hash-Code zu ändern, nachdem sie zu der Sammlung hinzugefügt werden. Niederlage würde der ganze Zweck ...

Answer 13

Mit den Reflexionsmethoden auf Apache Commons Equals und HashCodeBuilder .

Answer 14

Jede Hashing-Methode, die gleichmäßig den Hash-Wert über den möglichen Bereich verteilt ist eine gute Umsetzung. Siehe Effective Java ( 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 ) gibt es einen guten Tipp dort für hashcode Umsetzung (Punkt 9 ich denke, ...).

Answer 15

Ich ziehe Nutzen Methoden Fromm Google Kollektionen lib von Klasse Objects , die mir meinen Code sauber zu halten hilft. Sehr oft equals und hashcode Methoden werden von IDE Vorlage vorgenommen, so dass ihre nicht sauber zu lesen.

Answer 16

Ich verwende einen kleinen Wrapper um Arrays.deepHashCode(...) weil sie behandelt Arrays als Parameter geliefert richtig

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

Answer 17

Hier ist eine andere JDK 1.7+ Ansatz Demonstration mit Super Logiken bilanziert. Ich sehe es als ziemlich convinient mit Objektklasse hashCode () ausmachen, reine JDK-Abhängigkeit und keine zusätzliche manuelle Arbeit. Bitte beachten Sie Objects.hash() null tolerant ist.

I enthalten habe keine equals() Umsetzung aber in Wirklichkeit werden Sie natürlich brauchen.

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

}

Answer 18

Die Standardimplementierung ist schwach und dessen Verwendung führt zu unnötigen Kollisionen. Stellen Sie sich ein

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

    ...
}

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

und

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

haben die gleiche hashCode, nämlich 31*(a+b) + c als die für List.hashCode verwendet Multiplikator hier wiederverwendet wird. Offensichtlich sind Kollisionen unvermeidbar, aber es ist unnötig Kollisionen produzieren ist nur ... überflüssig.

Es gibt nichts im Wesentlichen smart über 31 verwenden. Der Multiplikator muss, um ungerade Informationen zu verlieren (jeder selbst Multiplikator verliert zumindest das signifikanteste Bit, ein Vielfaches von vier zwei verlieren, etc.). Jeder ungeradeer Multiplikator ist verwendbar. Kleine Multiplikatoren zu einer schnelleren Berechnung führen können (der JIT-Verschiebungen und Ergänzungen können), aber wenn man bedenkt, dass die Multiplikation Latenzzeit von nur drei Zyklen auf modernen Intel / AMD hat dies kaum eine Rolle. Kleine Multiplikatoren führen auch zu mehr Kollision für kleine Eingänge, die manchmal ein Problem sein können.

ein erstklassige Verwendung ist sinnlos, da Primzahlen keine Bedeutung im Ring hat Z / (2 ** 32).

Also, ich würde empfehlen, eine zufällig ausgewählte große ungerade Zahl mit (auch gerne selber eine Primzahl nehmen). Als i86 / amd64 CPUs eine kürzere Anweisung für Operanden Einpassen in einem einzigen Byte mit Vorzeichen verwenden kann, gibt es einen kleinen Geschwindigkeitsvorteil für Multiplikatoren wie 109. Kollisionen Zur Minimierung, so etwas wie 0x58a54cf5 nehmen.

Mit verschiedenen Multiplikatoren an verschiedenen Orten ist hilfreich, aber wahrscheinlich nicht genug, um die zusätzliche Arbeit zu rechtfertigen.

Answer 19

Wenn Hash-Werte kombiniert, ich in der Regel die Kombination Methode verwenden, die C ++ Bibliothek im Boost verwendet wird, nämlich:

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

Dies macht einen ziemlich guten Job eine gleichmäßige Verteilung zu gewährleisten. Seit einiger Diskussion darüber, wie diese Formel funktioniert, finden Sie in den Stackoverflow Beitrag: Magic-Nummer in boost :: hash_combine

Es gibt eine gute Diskussion verschiedener Hash-Funktionen an: http://burtleburtle.net/bob /hash/doobs.html

Answer 20

Für eine einfache Klasse ist es oft am einfachsten hashCode () basierend auf den Klassenfeldern zu implementieren, die durch die equals () Umsetzung geprüft werden.

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

Das Wichtigste ist hashCode zu halten () und equals () konsistent: wenn equals () für zwei Objekte true zurückgibt, dann hashCode () sollte den gleichen Wert zurück. Wenn equals () false zurückgibt, dann hashCode () sollten unterschiedliche Werte zurückgeben.