Standardimplementierung für Object.GetHashCode ()

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

Ich versuche zu entscheiden, in welchen Fällen ich meine eigenen verpacken sollte und in welchen Fällen ich mich auf die Standardimplementierung verlassen kann, um es gut zu machen. Ich will das Rad, wenn überhaupt möglich, nicht neu erfinden.

 namespace System { public class Object { [MethodImpl(MethodImplOptions.InternalCall)] internal static extern int InternalGetHashCode(object obj); public virtual int GetHashCode() { return InternalGetHashCode(this); } } } 

InternalGetHashCode ist einer ObjectNative :: GetHashCode- function in der CLR zugeordnet, die wie folgt 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 groß, daher ist es einfacher, eine Verknüpfung mit dem C ++ – Quellcode herzustellen .

Für eine class sind die Standardwerte im Wesentlichen Referenzgleichheit, und das ist normalerweise gut. 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 eine Struktur trotzdem schreiben!

Wenn Sie die Gleichheit überschreiben, sollten Sie immer eine GetHashCode() Equals() und GetHashCode() (dh für zwei Werte, wenn Equals() Wert true zurückgibt, müssen sie denselben Hash-Code zurückgeben, aber die Umkehrung ist nicht erforderlich) – und das ist üblich um auch == / != Operatoren bereitzustellen und IEquatable auch zu implementieren.

Zur Generierung des Hash-Codes wird üblicherweise eine faktorierte Summe verwendet, da dadurch Kollisionen bei gepaarten Werten vermieden werden – beispielsweise bei einem 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 identisch mit dem Hash von {2,1}
  • der Hash von {1,1} ist nicht identisch mit dem Hash von {2,2}

usw. – das kann üblich sein, wenn Sie nur eine ungewichtete Summe verwenden, oder xor ( ^ ) usw.

Die Dokumentation für die GetHashCode Methode für Object besagt, dass “die Standardimplementierung dieser Methode nicht als eindeutiger Objektbezeichner für Hash-Zwecke verwendet werden darf”. Der Wert für ValueType lautet “Wenn Sie die GetHashCode-Methode des abgeleiteten Typs aufrufen, ist der Rückgabewert wahrscheinlich nicht geeignet, um ihn als Schlüssel in einer Hash-Tabelle zu verwenden.” .

Die grundlegenden Datentypen wie byte , short , int , long , char und string implementieren eine gute GetHashCode-Methode. Einige andere classn und Strukturen, wie beispielsweise Point , implementieren eine GetHashCode Methode, die für Ihre spezifischen Anforderungen geeignet sein kann oder auch nicht. Sie müssen es nur ausprobieren, um zu sehen, ob es gut genug ist.

Die Dokumentation für jede class 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 classn oder Strukturen, die Sie selbst erstellen, an denen Sie die GetHashCode Methode verwenden müssen, sollten Sie eine eigene Implementierung erstellen, die die entsprechenden GetHashCode zur Berechnung des Hash-Codes verwendet.

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

Equals wird verwendet, wenn Foo A, B;

wenn (A == B)

Da wir wissen, dass der pointers 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 Hashtabellen verwendet. Der Hashcode, der von Ihrer class generiert wird, sollte für einen classnstatus immer derselbe sein.

Normalerweise tue ich das,

 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 damit nicht überein (und ich bin wahrscheinlich falsch).

Wenn Sie die Standardimplementierung verwenden, die von object bereitgestellt wird, sind sie nicht identisch, wenn Sie nicht denselben Verweis auf eine Ihrer classn haben. Durch Überschreiben von Equals und GetHashCode können Sie die Gleichheit basierend auf internen Werten und nicht anhand der Objektverweise melden.

Da ich keine Antwort finden konnte, die erklärt, warum wir GetHashCode und Equals für benutzerdefinierte Strukturen überschreiben sollten und warum die Standardimplementierung “wahrscheinlich nicht geeignet ist, um als Schlüssel in einer Hash-Tabelle verwendet zu werden”, überlasse ich einen Link zu Dieser Blogpost erklärt, warum mit einem Fallbeispiel ein Problem aufgetreten ist.

Ich empfehle die ganze Post zu lesen, aber hier ist eine Zusammenfassung (Hervorhebung und Klarstellungen hinzugefügt).

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

System.ValueType die CLR entworfen wurde, kann jeder Aufruf eines Members, der in System.ValueType oder System.Enum types definiert ist, [may] eine System.Enum […] verursachen.

Ein Implementierer einer Hash-function steht vor einem Dilemma: Mach eine gute Verteilung der Hash-function oder mache sie schnell. In einigen Fällen ist es möglich, beide zu erreichen, aber es ist schwierig, dies in ValueType.GetHashCode generisch zu ValueType.GetHashCode .

Die kanonische Hash-function einer Struktur “kombiniert” Hash-Codes aller Felder. Die einzige Möglichkeit, einen Hash-Code eines Felds in einer ValueType Methode zu erhalten, besteht jedoch in der Verwendung von Reflektion . Also haben die CLR-Autoren beschlossen, die Geschwindigkeit über die Distribution zu GetHashCode und die Standard- GetHashCode Version gibt nur einen Hash-Code eines ersten Nicht-Null-Feldes zurück und “munges” mit einer Typ-ID […] Dies ist ein vernünftiges Verhalten, es sei denn nicht. Wenn Sie zum Beispiel Pech haben und das erste Feld Ihrer Struktur für die meisten Instanzen den gleichen Wert hat, dann liefert eine Hash-function immer das gleiche Ergebnis . Und wie Sie sich vorstellen können, wird dies drastische Auswirkungen auf die Performance haben, wenn diese Instanzen in einem Hash-Set oder einer Hash-Tabelle gespeichert werden.

[…] Die reflektionsbasierte Implementierung ist langsam . Sehr langsam.

[…] Sowohl ValueType.Equals als auch ValueType.GetHashCode haben eine spezielle Optimierung. Wenn ein Typ keine “pointers” hat und richtig gepackt […] ist, werden optimalere Versionen verwendet: GetHashCode iteriert über eine Instanz und XORs Blöcke von 4 Bytes und die Equals Methode vergleicht zwei Instanzen mit memcmp . […] Aber die Optimierung ist sehr schwierig. Erstens ist es schwierig zu wissen, wann die Optimierung aktiviert ist. Zweitens liefert ein Speichervergleich nicht unbedingt die richtigen Ergebnisse . Hier ein einfaches Beispiel: […] -0.0 und +0.0 sind gleich, haben aber unterschiedliche Binärdarstellungen.

Real-World-Problem in der Post beschrieben:

 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 verwendeten ein Tupel, das eine benutzerdefinierte Struktur mit der Standardimplementierung der Gleichheit enthielt. Und leider hatte die Struktur ein optionales erstes Feld, das fast immer gleich [leere Zeichenfolge] war . Die performance war in Ordnung, bis die Anzahl der Elemente im Satz deutlich anstieg, was zu einem echten performancesproblem führte, wobei Minuten benötigt wurden, um eine Sammlung mit Zehntausenden von Elementen zu initialisieren.

Um also die Frage zu beantworten, “in welchen Fällen ich meine eigenen Pakete einpacken sollte und in welchen Fällen ich mich auf die Standardimplementierung verlassen kann”, sollten Sie Equals und GetHashCode , zumindest im Falle von Strukturen , immer dann überschreiben, wenn Ihre benutzerdefinierte Struktur verwendet wird als Schlüssel in einer Hash-Tabelle oder einem Dictionary .
Ich würde auch empfehlen, IEquatable in diesem Fall zu implementieren, um Boxen zu vermeiden.

Wie die anderen Antworten sagten, wenn Sie eine class schreiben, ist der Standard-Hash mit Referenzgleichheit normalerweise in Ordnung, also würde ich in diesem Fall nicht stören, außer Sie müssen Equals überschreiben (dann müssten Sie GetHashCode entsprechend überschreiben) .