webentwicklung-frage-antwort-db.com.de

Beste Implementierung für die hashCode-Methode für eine Auflistung

Wie entscheiden wir uns für die beste Implementierung der hashCode() -Methode für eine Sammlung (vorausgesetzt, dass die Methode equals korrekt überschrieben wurde)?

288
Omnipotent

Die beste Umsetzung? Das ist eine schwierige Frage, da sie vom Nutzungsmuster abhängt.

Eine für fast alle Fälle zumutbare gute Implementierung wurde in Josh Bloch 's Effektives Java in Punkt 8 (zweite Ausgabe) vorgeschlagen. Das Beste ist, dort nachzuschlagen, weil der Autor dort erklärt, warum der Ansatz gut ist.

Eine kurze Version

  1. Erstellen Sie einen int result Und weisen Sie einen ngleich Null Wert zu.

  2. Berechnen Sie für jedes Feldf, das in der equals() -Methode getestet wurde, einen Hash-Code c mit:

    • Wenn das Feld f ein boolean ist: berechne (f ? 0 : 1);
    • Wenn das Feld f ein byte, char, short oder int ist: berechne (int)f;
    • Wenn das Feld f ein long ist: berechne (int)(f ^ (f >>> 32));
    • Wenn das Feld f ein float ist: berechne Float.floatToIntBits(f);
    • Wenn das Feld f ein double ist: berechne Double.doubleToLongBits(f) und behandle den Rückgabewert wie jeden langen Wert;
    • Wenn das Feld f ein Objekt ist: Verwenden Sie das Ergebnis der hashCode() -Methode oder 0, wenn f == null;
    • Wenn das Feld f ein Array ist: Betrachte jedes Feld als separates Element und berechne den Hash-Wert in einer rekursiven Weise und kombiniere die Werte wie nachfolgend beschrieben.
  3. Kombiniere den Hashwert c mit result:

    result = 37 * result + c
    
  4. Rückgabe result

Dies sollte für die meisten Verwendungssituationen zu einer ordnungsgemäßen Verteilung der Hash-Werte führen.

426
dmeister

Wenn Sie mit der von dmeister empfohlenen Effective Java) -Implementierung zufrieden sind, können Sie einen Bibliotheksaufruf verwenden, anstatt Ihren eigenen zu rollen:

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

Dies erfordert entweder Guave (com.google.common.base.Objects.hashCode) oder die Standardbibliothek in Java 7 (Java.util.Objects.hash) funktioniert aber genauso.

133
bacar

Es ist besser, die von Eclipse bereitgestellten Funktionen zu verwenden, die einen ziemlich guten Job machen und Sie können Ihre Anstrengungen und Energie in die Entwicklung der Geschäftslogik stecken.

58
Warrior

Obwohl dies mit Android documentation (Wayback Machine) und My own code on Github verknüpft ist, funktioniert es für Java Meine Antwort ist eine Erweiterung von dmeisters Antwort mit einfachem Code, der viel einfacher zu lesen und zu verstehen ist.

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

}

[~ # ~] edit [~ # ~]

Wenn Sie hashcode(...) überschreiben, möchten Sie in der Regel auch equals(...) überschreiben. Also für diejenigen, die equals wollen oder bereits implementiert haben, 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));
}
55

Stellen Sie zunächst sicher, dass equals korrekt implementiert ist. Aus einem IBM DeveloperWorks-Artikel :

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

Stellen Sie dann sicher, dass ihre Beziehung zu hashCode den Kontakt respektiert (aus demselben Artikel):

  • Konsistenz mit hashCode (): Zwei gleiche Objekte müssen denselben hashCode () - Wert haben

Schließlich sollte eine gute Hash-Funktion danach streben, sich der idealen Hash-Funktion anzunähern.

17
Grey Panther

about8.blogspot.com, sagten Sie

wenn equals () für zwei Objekte true zurückgibt, sollte hashCode () denselben Wert zurückgeben. Wenn equals () false zurückgibt, sollte hashCode () andere Werte zurückgeben

Da kann ich dir nicht zustimmen Wenn zwei Objekte den gleichen Hashcode haben, muss dies nicht bedeuten, dass sie gleich sind.

Wenn A gleich B ist, muss A.hashcode gleich B.hascode sein

aber

wenn A.hashcode gleich B.hascode ist, bedeutet dies nicht, dass A gleich B sein muss

11
panzupa

Es gibt eine gute Implementierung der hashcode() - und equals() -Logik von Effective Java in Apache) Commons Lang . Checkout HashCodeBuilder und EqualsBuilder .

7
Rudi Adianto

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

Source -> Generiere hashCode () und equals ().

Mit dieser Funktion können Sie festlegen, welche Felder Sie für die Berechnung von Gleichheits- und Hash-Codes verwenden möchten, und Eclipse generiert die entsprechenden Methoden.

7

Nur eine kurze Notiz zum Ausfüllen weiterer ausführlicherer Antworten (in Bezug auf den Code):

Wenn ich die Frage betrachte wie erstelle ich eine Hash-Tabelle in Java und insbesondere jGuru FAQ Eintrag = Ich glaube, einige andere Kriterien, nach denen ein Hash-Code beurteilt werden könnte, sind:

  • synchronisation (unterstützt der Algo gleichzeitigen Zugriff oder nicht)?
  • ausfallsichere Iteration (erkennt der Algo eine Sammlung, die sich während der Iteration ändert)
  • nullwert (unterstützt der Hash-Code Nullwerte in der Auflistung)
5
VonC

Wenn ich Ihre Frage richtig verstehe, haben Sie eine benutzerdefinierte Auflistungsklasse (d. H. Eine neue Klasse, die von der Auflistungsschnittstelle ausgeht) und möchten die hashCode () -Methode implementieren.

Wenn Ihre Auflistungsklasse AbstractList erweitert, müssen Sie sich darüber keine Gedanken machen. Es gibt bereits eine Implementierung von equals () und hashCode (), die alle Objekte durchläuft und ihre hashCodes () zusammenfügt.

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

Wenn Sie nun den Hash-Code für eine bestimmte Klasse am besten berechnen möchten, verwende ich normalerweise den Operator ^ (bitweises Exklusiv oder), um alle Felder zu verarbeiten, die ich in der Methode equals verwende:

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

@ about8: da ist ein ziemlich schwerwiegender Fehler.

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

gleicher Hashcode

sie wollen wahrscheinlich so etwas wie

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

(Können Sie Hashcode direkt von int in Java in diesen Tagen? Ich denke, es macht etwas Autocasting .. Wenn das der Fall ist, überspringen Sie den toString, es ist hässlich.)

2
SquareCog

Da Sie speziell nach Sammlungen gefragt haben, möchte ich einen Aspekt hinzufügen, den die anderen Antworten noch nicht erwähnt haben: Eine HashMap erwartet nicht, dass ihre Schlüssel ihren Hashcode ändern, sobald sie der Sammlung hinzugefügt werden. Würde den ganzen Zweck besiegen ...

2
Olaf Kock

Verwenden Sie die Reflektionsmethoden für Apache Commons EqualsBuilder und HashCodeBuilder .

2
Vihung

Ich benutze einen winzigen Wrapper um Arrays.deepHashCode(...) , weil er die als Parameter angegebenen Arrays korrekt behandelt

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

Die Standardimplementierung ist schwach und führt zu unnötigen Kollisionen. Stellen Sie sich vor a

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

    ...
}

Jetzt,

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

und

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

habe das gleiche hashCode, nämlich 31*(a+b) + c, wie der für List.hashCode verwendete Multiplikator hier wiederverwendet wird. Offensichtlich sind Kollisionen unvermeidlich, aber unnötige Kollisionen zu erzeugen ist einfach ... unnötig.

Die Verwendung von 31 Ist nicht besonders clever. Der Multiplikator muss ungerade sein, um Informationsverlust zu vermeiden (jeder gerade Multiplikator verliert mindestens das höchstwertige Bit, Vielfache von vier verlieren zwei usw.). Jeder ungerade Multiplikator ist verwendbar. Kleine Multiplikatoren können zu einer schnelleren Berechnung führen (die JIT kann Verschiebungen und Additionen verwenden). Da die Multiplikation bei modernen Intel/AMD-Systemen jedoch nur eine Latenz von drei Zyklen aufweist, spielt dies kaum eine Rolle. Kleine Multiplikatoren führen auch zu mehr Kollisionen bei kleinen Eingaben, was manchmal ein Problem sein kann.

Die Verwendung einer Primzahl ist sinnlos, da Primzahlen im Ring Z/(2 ** 32) keine Bedeutung haben.

Daher würde ich die Verwendung einer zufällig ausgewählten großen ungeraden Zahl empfehlen (zögern Sie nicht, eine Primzahl zu wählen). Da i86/AMD64-CPUs einen kürzeren Befehl für Operanden verwenden können, die in ein einzelnes Byte mit Vorzeichen passen, haben Multiplikatoren wie 109 einen winzigen Geschwindigkeitsvorteil. Nehmen Sie zum Minimieren von Kollisionen etwa 0x58a54cf5.

Die Verwendung verschiedener Multiplikatoren an verschiedenen Stellen ist hilfreich, reicht jedoch wahrscheinlich nicht aus, um die zusätzliche Arbeit zu rechtfertigen.

1
maaartinus

jede Hash-Methode, die den Hash-Wert gleichmäßig über den möglichen Bereich verteilt, ist eine gute Implementierung. Siehe effektive Java ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=effective+Java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxi&sz = book_result & resnum = 1 & ct = result ), es gibt einen guten Tipp für die Implementierung von Hashcode (Punkt 9, denke ich ...).

1
Chii

Hier ist eine weitere Demonstration des JDK 1.7+ -Ansatzes, bei der Logiken der Oberklasse berücksichtigt werden. Ich sehe es als ziemlich praktisch an, wenn die Objektklasse hashCode () berücksichtigt wird, reine JDK-Abhängigkeit und keine zusätzliche manuelle Arbeit. Bitte beachten Sie, dass Objects.hash() nulltolerant ist.

Ich habe keine equals() -Implementierung eingeschlossen, aber in Wirklichkeit werden Sie es 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());
    }

}
1

Ich bevorzuge die Verwendung von Dienstprogrammmethoden von m Google Collections-Bibliothek aus Klassenobjekten, die mir dabei helfen, meinen Code sauber zu halten. Sehr häufig werden die Methoden equals und hashcode aus der IDE-Vorlage erstellt, sodass sie nicht sauber lesbar sind.

1
panzupa

Beim Kombinieren von Hash-Werten verwende ich normalerweise die in der boost c ++ - Bibliothek verwendete Kombinationsmethode:

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

Dies ist ein guter Job, um eine gleichmäßige Verteilung zu gewährleisten. Eine Beschreibung der Funktionsweise dieser Formel finden Sie im Beitrag zu StackOverflow: Magische Zahl in boost :: hash_combine

Es gibt eine gute Diskussion über verschiedene Hash-Funktionen unter: http://burtleburtle.net/bob/hash/doobs.html

0
Edward Loper