Standardimplementierung für Object.GetHashCode ()

162

Wie funktioniert die Standardimplementierung für GetHashCode()? Und handhabt es Strukturen, Klassen, Arrays usw. effizient und gut genug?

Ich versuche zu entscheiden, in welchen Fällen ich meine eigenen packen soll und in welchen Fällen ich mich sicher darauf verlassen kann, dass die Standardimplementierung gut funktioniert. Ich möchte das Rad nicht neu erfinden, wenn es überhaupt möglich ist.

Fung
quelle
Schauen Sie sich den Kommentar an, den ich zu dem Artikel hinterlassen habe
Paul Westcott
34
Abgesehen: Sie erhalten den Standard - Hash - Code (auch wenn GetHashCode()schon außer Kraft gesetzt wird) unter VerwendungSystem.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(obj)
Marc GRA
@MarcGravell, danke, dass du dazu beigetragen hast. Ich habe genau nach dieser Antwort gesucht.
Andrew Savinykh
@MarcGravell Aber wie würde ich das mit einer anderen Methode machen?
Tomáš Zato - Wiedereinsetzung Monica

Antworten:

86
namespace System {
    public class Object {
        [MethodImpl(MethodImplOptions.InternalCall)]
        internal static extern int InternalGetHashCode(object obj);

        public virtual int GetHashCode() {
            return InternalGetHashCode(this);
        }
    }
}

InternalGetHashCode wird einer ObjectNative :: GetHashCode- Funktion in der CLR zugeordnet, die folgendermaßen aussieht:

FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {  
    CONTRACTL  
    {  
        THROWS;  
        DISABLED(GC_NOTRIGGER);  
        INJECT_FAULT(FCThrow(kOutOfMemoryException););  
        MODE_COOPERATIVE;  
        SO_TOLERANT;  
    }  
    CONTRACTL_END;  

    VALIDATEOBJECTREF(obj);  

    DWORD idx = 0;  

    if (obj == 0)  
        return 0;  

    OBJECTREF objRef(obj);  

    HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);        // Set up a frame  

    idx = GetHashCodeEx(OBJECTREFToObject(objRef));  

    HELPER_METHOD_FRAME_END();  

    return idx;  
}  
FCIMPLEND

Die vollständige Implementierung von GetHashCodeEx ist ziemlich umfangreich, sodass es einfacher ist, nur eine Verknüpfung zum C ++ - Quellcode herzustellen .

David Brown
quelle
5
Dieses Dokumentationszitat muss aus einer sehr frühen Version stammen. Es wird in aktuellen MSDN-Artikeln nicht mehr so ​​geschrieben, wahrscheinlich weil es völlig falsch ist.
Hans Passant
4
Sie haben den Wortlaut geändert, ja, aber es heißt im Grunde immer noch dasselbe: "Folglich darf die Standardimplementierung dieser Methode nicht als eindeutige Objektkennung für Hashing-Zwecke verwendet werden."
David Brown
7
Warum wird in der Dokumentation behauptet, dass die Implementierung für das Hashing nicht besonders nützlich ist? Wenn ein Objekt sich selbst und nichts anderem entspricht, gibt es eine Hash-Code-Methode, die immer den gleichen Wert für eine bestimmte Objektinstanz zurückgibt und im Allgemeinen unterschiedliche Werte für verschiedene Instanzen zurückgibt. Was ist das Problem?
Supercat
3
@ ta.speot.is: Wenn Sie feststellen möchten, ob eine bestimmte Instanz bereits zu einem Wörterbuch hinzugefügt wurde, ist die Referenzgleichheit perfekt. Wie Sie bemerken, interessiert man sich bei Zeichenfolgen normalerweise mehr dafür, ob bereits eine Zeichenfolge mit derselben Zeichenfolge hinzugefügt wurde. Deshalb stringüberschreibt GetHashCode. Angenommen, Sie möchten zählen, wie oft verschiedene Steuerelemente PaintEreignisse verarbeiten. Sie könnten ein verwenden Dictionary<Object, int[]>(jedes int[]gespeicherte würde genau ein Element enthalten).
Supercat
6
@ It'sNotALie. Dann danke Archive.org für die Kopie ;-)
RobIII
88

Für eine Klasse sind die Standardeinstellungen im Wesentlichen Referenzgleichheit, und das ist normalerweise in Ordnung. Wenn Sie eine Struktur schreiben, ist es üblicher, die Gleichheit zu überschreiben (nicht zuletzt, um das Boxen zu vermeiden), aber es ist sehr selten, dass Sie trotzdem eine Struktur schreiben!

Wenn Sie die Gleichheit überschreiben, sollten Sie immer eine Übereinstimmung haben Equals()und GetHashCode()(dh für zwei Werte, wenn Equals()true zurückgegeben wird, müssen sie denselben Hash-Code zurückgeben, aber die Umkehrung ist nicht erforderlich) - und es ist üblich, auch ==/ !=operator bereitzustellen , und häufig zu auch implementieren IEquatable<T>.

Zum Generieren des Hash-Codes wird häufig eine faktorisierte Summe verwendet, da dadurch Kollisionen mit gepaarten Werten vermieden werden - beispielsweise für einen einfachen 2-Feld-Hash:

unchecked // disable overflow, for the unlikely possibility that you
{         // are compiling with overflow-checking enabled
    int hash = 27;
    hash = (13 * hash) + field1.GetHashCode();
    hash = (13 * hash) + field2.GetHashCode();
    return hash;
}

Dies hat den Vorteil, dass:

  • Der Hash von {1,2} ist nicht der gleiche wie der Hash von {2,1}
  • Der Hash von {1,1} ist nicht der gleiche wie der Hash von {2,2}

etc - was häufig vorkommt, wenn nur eine ungewichtete Summe oder xor ( ^) usw. verwendet wird.

Marc Gravell
quelle
Hervorragender Punkt über den Nutzen eines Faktorsummenalgorithmus; etwas, das ich vorher nicht realisiert hatte!
Schlupfloch
Verursacht die faktorisierte Summe (wie oben beschrieben) nicht gelegentlich Überlaufausnahmen?
Sinelaw
4
@sinelaw ja, es sollte durchgeführt werden unchecked. Glücklicherweise uncheckedist dies die Standardeinstellung in C #, aber es ist besser, sie explizit zu machen. bearbeitet
Marc Gravell
7

In der Dokumentation zur GetHashCodeMethode für Object heißt es: "Die Standardimplementierung dieser Methode darf nicht als eindeutige Objektkennung für Hashing-Zwecke verwendet werden." und der für ValueType lautet: "Wenn Sie die GetHashCode-Methode des abgeleiteten Typs aufrufen, ist der Rückgabewert wahrscheinlich nicht für die Verwendung als Schlüssel in einer Hash-Tabelle geeignet." .

Die grundlegenden Datentypen wie byte, short, int, long, charund stringein gutes GetHashCode - Methode implementieren. Einige andere Klassen und Strukturen, wie Pointzum Beispiel, implementieren eine GetHashCodeMethode, die für Ihre spezifischen Anforderungen geeignet sein kann oder nicht. Sie müssen es nur ausprobieren, um zu sehen, ob es gut genug ist.

Die Dokumentation für jede Klasse oder Struktur kann Ihnen sagen, ob sie die Standardimplementierung überschreibt oder nicht. Wenn es nicht überschrieben wird, sollten Sie Ihre eigene Implementierung verwenden. Für alle Klassen oder Strukturen, die Sie selbst erstellen und in denen Sie die GetHashCodeMethode verwenden müssen, sollten Sie eine eigene Implementierung erstellen , die die entsprechenden Elemente zur Berechnung des Hash-Codes verwendet.

Guffa
quelle
2
Ich würde nicht zustimmen, dass Sie routinemäßig Ihre eigene Implementierung hinzufügen sollten . Einfach gesagt, die überwiegende Mehrheit der Klassen (insbesondere) wird niemals auf Gleichheit geprüft - oder wo sie sich befinden, ist die eingebaute Referenzgleichheit in Ordnung. Bei der (bereits seltenen) Gelegenheit, eine Struktur zu schreiben, wäre dies häufiger der Fall.
Marc Gravell
@ Marc Gravel: Das habe ich natürlich nicht so gemeint. Ich werde den letzten Absatz anpassen. :)
Guffa
Grundlegende Datentypen implementieren zumindest in meinem Fall keine gute GetHashCode-Methode. Zum Beispiel gibt GetHashCode für int die Nummer selbst zurück: (123) .GetHashCode () gibt 123 zurück.
fdermishin
5
@ user502144 Und was ist daran falsch? Es ist eine perfekte eindeutige Kennung, die einfach zu berechnen ist, ohne falsch positive
Richard Rast
@ Richard Rast: Es ist in Ordnung, außer dass Schlüssel schlecht verteilt werden können, wenn sie in einer Hashtabelle verwendet werden. Schauen Sie sich diese Antwort an: stackoverflow.com/a/1388329/502144
fdermishin
5

Da ich keine Antwort finden konnte, die erklärt, warum wir überschreiben sollten GetHashCodeund Equalsfür benutzerdefinierte Strukturen und warum die Standardimplementierung "wahrscheinlich nicht als Schlüssel in einer Hash-Tabelle geeignet ist", werde ich einen Link zu diesem Blog hinterlassen Beitrag , der erklärt, warum mit einem realen Beispiel eines aufgetretenen Problems.

Ich empfehle, den gesamten Beitrag zu lesen, aber hier ist eine Zusammenfassung (Hervorhebung und Klarstellung hinzugefügt).

Grund, warum der Standard-Hash für Strukturen langsam und nicht sehr gut ist:

Die Art und Weise der CLR ausgeführt ist, jeder Anruf an ein Mitglied der Definition in System.ValueTypeoder System.EnumTypen [kann] Ursache einer Box - Zuordnung [...]

Ein Implementierer einer Hash-Funktion steht vor einem Dilemma: Machen Sie eine gute Verteilung der Hash-Funktion oder machen Sie sie schnell. In einigen Fällen ist es möglich , sie beide zu erreichen, aber es ist schwer , dies zu tun allgemein in ValueType.GetHashCode.

Die kanonische Hash-Funktion einer Struktur "kombiniert" Hash-Codes aller Felder. Der einzige Weg, um einen Hash-Code eines Feldes in einer ValueTypeMethode zu erhalten, ist die Verwendung von Reflektion . Also, um den Handel Geschwindigkeit über die Verteilung der CLR Autoren entschieden und die Standard - GetHashCodeVersion gibt nur einen Hash - Code eines ersten Nicht-Null - Feld und „munges“ es mit einem Typ - ID [...] Dies ist ein vernünftiges Verhalten , wenn es nicht ist . Zum Beispiel, wenn Sie Pech haben , und das erste Feld Ihrer Struktur sind den gleichen Wert für die meisten Fälle, wird eine Hash - Funktion das gleiche Ergebnis liefert die ganze Zeit. Und wie Sie sich vorstellen können, führt dies zu drastischen Auswirkungen auf die Leistung, wenn diese Instanzen in einem Hash-Set oder einer Hash-Tabelle gespeichert werden.

[...] Die reflexionsbasierte Implementierung ist langsam . Sehr langsam.

[...] Beide ValueType.Equalsund ValueType.GetHashCodehaben eine spezielle Optimierung. Wenn ein Typ keine "Zeiger" hat und [...] ordnungsgemäß gepackt ist, werden optimalere Versionen verwendet: GetHashCodeIteriert über eine Instanz und XORs-Blöcke mit 4 Bytes, und die EqualsMethode vergleicht zwei Instanzen mit memcmp. [...] Die Optimierung ist jedoch sehr schwierig. Erstens ist es schwer zu wissen, wann die Optimierung aktiviert ist [...] Zweitens liefert ein Speichervergleich nicht unbedingt die richtigen Ergebnisse . Hier ist ein einfaches Beispiel: [...] -0.0und +0.0sind gleich, haben aber unterschiedliche binäre Darstellungen.

In der Post beschriebenes Problem der realen Welt:

private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
    // Empty almost all the time
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

Wir haben ein Tupel verwendet, das eine benutzerdefinierte Struktur mit Standard-Gleichheitsimplementierung enthielt. Und leider hatte die Struktur ein optionales erstes Feld, das fast immer gleich [leere Zeichenfolge] war . Die Leistung war in Ordnung, bis die Anzahl der Elemente im Satz erheblich anstieg, was zu einem echten Leistungsproblem führte. Die Initialisierung einer Sammlung mit Zehntausenden von Elementen dauerte Minuten.

Um die Frage zu beantworten, "in welchen Fällen ich meine eigene packen sollte und in welchen Fällen ich mich sicher auf die Standardimplementierung verlassen kann", sollten Sie zumindest bei Strukturen überschreiben Equalsund GetHashCodewann immer Ihre benutzerdefinierte Struktur als verwendet werden könnte Geben Sie eine Hash-Tabelle ein oder Dictionary.
Ich würde auch empfehlen, IEquatable<T>in diesem Fall zu implementieren , um Boxen zu vermeiden.

Wie die anderen Antworten sagten, ist beim Schreiben einer Klasse der Standard-Hash mit Referenzgleichheit normalerweise in Ordnung, daher würde ich mich in diesem Fall nicht darum kümmern, es sei denn, Sie müssen überschreiben Equals(dann müssten Sie GetHashCodeentsprechend überschreiben ).

Geekley
quelle
1

Wenn Sie Equals überschreiben, möchten Sie im Allgemeinen GetHashCode überschreiben. Der Grund dafür ist, dass beide verwendet werden, um die Gleichheit Ihrer Klasse / Struktur zu vergleichen.

Gleich wird verwendet, wenn Foo A, B überprüft wird;

if (A == B)

Da wir wissen, dass der Zeiger wahrscheinlich nicht übereinstimmt, können wir die internen Mitglieder vergleichen.

Equals(obj o)
{
    if (o == null) return false;
    MyType Foo = o as MyType;
    if (Foo == null) return false;
    if (Foo.Prop1 != this.Prop1) return false;

    return Foo.Prop2 == this.Prop2;
}

GetHashCode wird im Allgemeinen von Hash-Tabellen verwendet. Der von Ihrer Klasse generierte Hashcode sollte für einen Klassen-Status immer der gleiche sein.

Ich mache normalerweise,

GetHashCode()
{
    int HashCode = this.GetType().ToString().GetHashCode();
    HashCode ^= this.Prop1.GetHashCode();
    etc.

    return HashCode;
}

Einige werden sagen, dass der Hashcode nur einmal pro Objektlebensdauer berechnet werden sollte, aber ich stimme dem nicht zu (und ich liege wahrscheinlich falsch).

Wenn Sie die von object bereitgestellte Standardimplementierung verwenden, sind diese nicht gleich, es sei denn, Sie haben denselben Verweis auf eine Ihrer Klassen. Durch Überschreiben von Equals und GetHashCode können Sie Gleichheit basierend auf internen Werten und nicht auf der Objektreferenz melden.

Bennett Dill
quelle
2
Der ^ = -Ansatz ist kein besonders guter Ansatz zum Generieren eines Hashs - er führt tendenziell zu vielen häufigen / vorhersehbaren Kollisionen - zum Beispiel, wenn Prop1 = Prop2 = 3.
Marc Gravell
Wenn die Werte gleich sind, sehe ich kein Problem mit der Kollision, da die Objekte gleich sind. Der 13 * Hash + NewHash scheint allerdings interessant zu sein.
Bennett Dill
2
Ben: versuchen Sie es für Obj1 {Prop1 = 12, Prop2 = 12} und Obj2 {Prop1 = 13, Prop2 = 13}
Tomáš Kafka
0

Wenn Sie nur mit POCOs zu tun haben, können Sie dieses Dienstprogramm verwenden, um Ihr Leben etwas zu vereinfachen:

var hash = HashCodeUtil.GetHashCode(
           poco.Field1,
           poco.Field2,
           ...,
           poco.FieldN);

...

public static class HashCodeUtil
{
    public static int GetHashCode(params object[] objects)
    {
        int hash = 13;

        foreach (var obj in objects)
        {
            hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
        }

        return hash;
    }
}
Daniel Marshall
quelle