GetHashCode () Problem xor mit

Question

Mein Verständnis ist, dass Sie normalerweise mit GetHashCode verwenden xor sollen () einen int zu erzeugen Ihre Daten durch ihren Wert zu identifizieren (wie durch seine Referenz im Gegensatz zu). Hier ist ein einfaches Beispiel:

class Foo
{
    int m_a;
    int m_b;

    public int A
    {
        get { return m_a; }
        set { m_a = value; }
    }

    public int B
    {
        get { return m_b; }
        set { m_b = value; }
    }

    public Foo(int a, int b)
    {
        m_a = a;
        m_b = b;
    }

    public override int GetHashCode()
    {
        return A ^ B;
    }

    public override bool Equals(object obj)
    {
        return this.GetHashCode() == obj.GetHashCode();
    }
}

Die Idee ist, möchte ich eine Instanz von Foo zu einem anderen zu vergleichen, basierend auf dem Wert der Eigenschaften A und B. Wenn Foo1.A == Foo2.A und Foo1.B == Foo2.B, dann haben wir die Gleichheit .

Hier ist das Problem:

Foo one = new Foo(1, 2);
Foo two = new Foo(2, 1);

if (one.Equals(two)) { ... }  // This is true!

Diese beide einen Wert von 3 für GetHashCode () erzeugen, um return true Equals () verursacht. Offensichtlich ist dies ein triviales Beispiel, und mit nur zwei Eigenschaften konnte ich einfach die einzelnen Eigenschaften in dem Equals () -Methode vergleichen. Doch mit einer komplexeren Klasse würde dies schnell aus der Hand.

Ich weiß, dass manchmal ist es sinnvoll nur einmal den Hash-Code zu setzen, und immer den gleichen Wert zurück. Doch für veränderbare Objekte, wo eine Auswertung der Gleichheit notwendig ist, ich glaube nicht, dies zumutbar ist.

Was ist der beste Weg, Eigenschaftswerte zu verarbeiten, die leicht ausgetauscht werden können, wenn GetHashCode Umsetzung ()?

  

Siehe auch

     

Was ist der beste Algorithmus für eine überschriebenen System.Object.GetHashCode?

Answer 1

Als erstes - nicht umsetzen Equals () nur in Bezug auf GetHashCode () -. Hashcodes manchmal sogar kollidieren, wenn Objekte nicht gleich sind

Der Vertrag für GetHashCode () die folgenden:

• verschiedene Hashcodes bedeutet, dass Objekte sind definitiv nicht gleich
• same Hashcodes bedeutet Objekte können gleich (aber möglicherweise auch nicht)

Andrew Hare schlug ich übernehmen seine Antwort:

Ich würde empfehlen, dass Sie Lösung (von unserem eigenen Jon Skeet , übrigens) für eine „bessere“ Art und Weise zu berechnen eines Hash-Code.

  

Nein, der oben ist relativ langsam und   nicht viel helfen. Einige Leute benutzen   XOR (zB a ^ b ^ c) aber ich ziehe die   Art der Methode in Josh Bloch gezeigten   "Effective Java":

public override int GetHashCode()
{
    int hash = 23;
    hash = hash*37 + craneCounterweightID;
    hash = hash*37 + trailerID;
    hash = hash*37 + craneConfigurationTypeCode.GetHashCode();
    return hash;
}

     

Die 23 und 37 sind beliebige Zahlen   welche co-Primzahl.

     

Der Vorteil der oben über die XOR   Methode ist, dass, wenn Sie einen Typ   die zwei Werte, die   häufig die gleichen, XORing diejenigen   Werte immer das gleiche geben   (0), während der oben Willen   zwischen ihnen unterscheiden, es sei denn   Sie sind sehr unglücklich.

Wie in der obigen Schnipsel erwähnt, möchten Sie vielleicht auch sehen Joshua Blochs Buch , Effective Java, , die eine schöne Behandlung des Themas enthält (die hashcode Diskussion gilt auch für .NET).

Answer 2

Andrew ein gutes Beispiel für die Erzeugung eines besseren Hash-Code geschrieben hat, aber auch bedenken, dass Sie nicht Hash-Codes als Gleichheitsprüfung verwendet werden sollen, da sie nicht eindeutig sein garantiert.

Für ein triviales Beispiel, warum dies ein doppeltes Objekt betrachten. Es hat mehr möglichen Werte als ein int, so dass es unmöglich ist, eine einzigartige int für jedes Doppel zu haben. Hashes sind wirklich nur ein erster Durchgang, in Situationen wie ein Wörterbuch verwendet, wenn Sie den Schlüssel schnell, indem man zuerst den Vergleich Hashes ein großer Prozentsatz der möglichen Schlüssel ausgeschlossen werden kann, finden müssen und nur die Schlüssel mit passender Hashes die Kosten müssen haben einer vollständigen Gleichheitsprüfung (oder andere Kollisionsauflösung Methoden).

Answer 3

Hashing ist immer mit Kollisionen und man muss damit umgehen (F. E., Hash-Werte zu vergleichen, und wenn sie gleich sind, genau die Werte innerhalb der Klassen vergleichen, um sicherzustellen, dass die Klassen gleich sind).

ein einfaches XOR, werden Sie viele Kollisionen bekommen. Wenn Sie weniger wollen, einige mathematische Funktionen, die Werte über verschiedene Bits verteilen (Bit-Verschiebungen, mit Primzahlen Multiplikation usw.).

Answer 4

Lesen Sie Zwingende GetHashCode für veränderbare Objekte? C # und darüber nachdenken, IEquatable<T> Umsetzung

Answer 5

Eine schnelle Erzeugung und gute Verteilung der Hash

public override int GetHashCode()
{
    return A.GetHashCode() ^ B.GetHashCode();         // XOR
}

Answer 6

Aus Neugier da Hashcodes sind in der Regel eine schlechte Idee, zum Vergleich, wäre es nicht besser, nur den folgenden Code zu tun, oder bin ich etwas fehlt?

public override bool Equals(object obj)
{
    bool isEqual = false;
    Foo otherFoo = obj as Foo;
    if (otherFoo != null)
    {
        isEqual = (this.A == otherFoo.A) && (this.B == otherFoo.B);
    }
    return isEqual;
}

Answer 7

Es gibt mehrere bessere Hash-Implementierungen. FNV Hash zum Beispiel.