Was ist der beste Algorithmus für ein überschriebenes System.Object.GetHashCode?
In .NET System.Object.GetHashCode
- Methode wird verwendet, in einer Menge von Orten, während der .NET base class libraries. Vor allem, wenn die Suche nach Elementen in einer Sammlung schnell oder zu bestimmen Geschlechter. Gibt es einen standard-Algorithmus/best-practice zur Umsetzung der GetHashCode
override für meine benutzerdefinierte Klassen, damit ich nicht die Leistung beeinträchtigen?
Kommentar zu dem Problem - Öffnen
Nach dem Lesen dieser Frage und die Artikel unten, könnte ich implementieren, überschreiben von
GetHashCode
. Ich hoffe, dass es für andere hilfreich. Richtlinien und Regeln für die GetHashCode-geschrieben von Eric Lippert "oder, um zu bestimmen, Gleichheit": Nein! Zwei Objekte mit gleichem hashcode sind nicht unbedingt gleich.
@ThomasLevesque Sie haben Recht, die zwei Objekte mit dem gleichen hash-code sind nicht unbedingt gleich. Aber immer noch
GetHashCode()
verwendet wird, in sehr vielen Implementierungen von Equals()
. Das ist es, was ich meinte mit dieser Aussage. GetHashCode()
in Equals()
wird oft als eine Verknüpfung, um zu bestimmen, Ungleichheit, denn wenn zwei Objekte über eine verschiedenen - hash-code, den Sie haben, um Objekte, die nicht gleich sind und der rest der equality-check nicht ausgeführt. @bitbonk in der Regel, sowohl
GetHashCode()
und Equals()
müssen sich auf alle Felder der beiden Objekte (Equals zu tun hat, wenn es die hashcodes gleich sind oder nicht-aktiviert). Weil dieser, ein Aufruf von GetHashCode()
in Equals()
ist oft redundant und könnte die Leistung reduzieren. die Equals()
kann auch in der Lage sein, um Kurzschluss, so dass es viel schneller - aber in manchen Fällen die hashcodes können zwischengespeichert werden, so dass die GetHashCode()
überprüfen Sie schneller und so lohnt sich. Siehe diese Frage für mehr. InformationsquelleAutor der Frage bitbonk | 2008-11-04
Du musst angemeldet sein, um einen Kommentar abzugeben.
Normalerweise gehe ich mit so etwas wie die Umsetzung in Josh Bloch ' s fabelhafte Effektive Java. Es ist schnell und schafft eine ziemlich gute hash-was unwahrscheinlich ist, um Kollisionen. Wählen Sie zwei verschiedene Primzahlen, z.B. 17 und 23, und tun:
Wie bereits angemerkt in den Kommentaren, können Sie finden es besser, wählen eine große Primzahl durch multiplizieren statt. Offenbar 486187739 ist gut... und obwohl die meisten Beispiele, die ich gesehen habe mit kleinen zahlen neigen dazu, Primzahlen, gibt es zumindest ähnliche algorithmen, in denen die nicht-Primzahlen werden oft verwendet. In der nicht-ganz-FNV Beispiel später, zum Beispiel, ich habe zahlen, die offenbar gut funktionieren - aber der erste Wert ist nicht eine Primzahl. (Die Multiplikation mit Konstante ist prime obwohl. Ich weiß nicht Recht, wie wichtig das ist.)
Dies ist besser als die gängige Praxis des
XOR
ing hashcodes für zwei Hauptgründe. Nehmen wir an, wir haben einen Typ mit zweiint
Felder:Durch die Art und Weise, die frühere Algorithmus wird derzeit von der C# - compiler bei anonymen Typen.
Auf dieser Seite gibt durchaus ein paar Optionen. Ich denke für die meisten Fälle, die oben ist "gut genug" und es ist unglaublich einfach, sich zu erinnern und richtig zu machen. Die FNV alternative ist ebenso einfach, verwendet jedoch verschiedene Konstanten und
XOR
stattADD
als eine Kombination von operation. Es sieht etwas wie der code unten, aber der normale FNV Algorithmus arbeitet auf einzelnen bytes, so würde dies ändern, führen Sie eine iteration pro byte, nicht pro 32-bit-hash-Wert. FNV ist auch für die variable-Längen-Daten, in der Erwägung, dass die Art und Weise, die wir verwenden, ist es hier immer für die gleiche Anzahl von Feldern. Kommentare auf diese Antwort schlagen vor, dass der code hier nicht wirklich so gut funktionieren (in der Beispiel-Fall getestet) als neben-Ansatz vor.Beachten Sie, dass eine Sache zu beachten ist, dass im Idealfall sollten Sie verhindern, dass Ihre Geschlechter-sensible (und damit hashcode- /Kleinschreibung beachten) Zustand ändern, nachdem Sie diese in einer Auflistung, abhängig vom hash-code.
Als pro die Dokumentation:
InformationsquelleAutor der Antwort Jon Skeet
Microsoft bietet bereits eine gute generische HashCode-generator: kopieren Sie Einfach Ihre Eigenschaft/Feld-Werte auf eine anonyme Art und hash:
Dies funktioniert für eine beliebige Anzahl von Eigenschaften. Es nicht mit Boxen oder zusätzliche Ressourcen. Es wird der Algorithmus bereits implementiert, die den Rahmen für die anonyme Typen.
InformationsquelleAutor der Antwort Rick Love
Hier ist mein hashcode Helfer.
Es ist Vorteil ist, dass es verwendet generische Typ die Argumente und wird daher nicht Ursache Boxen:
Auch er hat eine extension-Methode, um eine fluent-Benutzeroberfläche, so dass Sie können es verwenden, wie diese:
oder so:
InformationsquelleAutor der Antwort nightcoder
Ich habe einen Hash-Klasse in Helper-Bibliothek, die ich verwenden es für diesen Zweck.
Dann, einfach Sie können es verwenden, wie:
Ich nicht beurteilen, seine Leistung, so dass jedes feedback ist willkommen.
InformationsquelleAutor der Antwort Wahid Shalaly
Hier ist meine helper Klasse mit Jon Skeet ist die Umsetzung.
Verwendung:
Wenn Sie vermeiden möchten, schreiben Sie eine Erweiterung Methode für System.Int32:
Es ist noch generisch, noch vermeidet jegliche heap-Allokation und es ist genau die gleiche Weise:
Update nach Martin ' s Kommentar:
obj != null
verursacht Boxen so wechselte ich zu den Standard-comparer.Bearbeiten (Mai 2018):
EqualityComparer<T>.Default
get-Methode ist nun ein JIT-intrinsische - die pull-request erwähnt wird, von Stephen Toub in in diesem blog-post.InformationsquelleAutor der Antwort Şafak Gür
In den meisten Fällen, in denen Equals() vergleicht mehrere Felder ist es eigentlich egal, wenn Ihr GetHash () - hashes auf ein Feld oder auf viele. Sie müssen nur sicherstellen, dass die Berechnung der hash ist wirklich Billig (Keine Zuweisungen, bitte) und schnell (Keine schwere Berechnungen und schon gar keine Datenbank-verbindungen) und bietet eine gute Verteilung.
Die schweres heben, sollten die Equals () - Methode; die hash-sollte einen sehr günstigen Betrieb zu ermöglichen aufrufen von Equals() auf so wenige Elemente wie möglich.
Und ein letzter Tipp: verlassen Sie sich nicht auf GetHashCode() ist stabil über mehrere Anwendung läuft. Viele .Net-Typen nicht garantieren, Ihre hash-codes zu bleiben, die gleichen nach einem Neustart, so sollten Sie nur verwenden, den Wert von GetHashCode() für in-memory-Datenstrukturen.
InformationsquelleAutor der Antwort Bert Huijben
Bis vor kurzem meine Antwort gewesen wäre, sehr nahe an Jon Skeet ist hier. Allerdings habe ich vor kurzem ein Projekt gestartet, welches verwendet Kraft-der-zwei hash-Tabellen, hash-Tabellen, in denen die Größe der internen Tabelle 8, 16, 32, usw. Es gibt einen guten Grund für die Begünstigung Primzahl-Größen, aber es gibt einige Vorteile, um macht-in zwei Größen zu.
Ist und es ziemlich gestunken. So nach ein bisschen Experimentieren und zu forschen begann ich re-hashing mein hashes mit den folgenden:
Haben und dann meinen Kraft-der-zwei hash-Tabelle nicht saugen mehr.
Dies störte mich aber, weil das oben nicht funktionieren sollte. Oder genauer gesagt, sollte es nicht funktionieren, es sei denn, die ursprüngliche
GetHashCode()
arm war in einer ganz besonderen Weise.Re-mixing ein hashcode nicht verbessern kann eine große hashcode, weil die einzig mögliche Wirkung, die wir einführen, ein paar mehr Kollisionen.
Re-mixing ein hash-code kann nicht verbessern, einen schrecklichen hash-code, weil der einzig mögliche Effekt ist, ändern wir z.B. eine große Anzahl von Kollisionen auf dem Wert 53 zu einer großen Anzahl von Wert 18,3487,291.
Re-mixing ein hash-code kann nur verbessern, einen hash-code, die haben zumindest ziemlich gut in der Vermeidung von absoluten Kollisionen in seinem gesamten Verbreitungsgebiet (232 mögliche Werte), aber schlecht bei der Vermeidung von Kollisionen bei der modulo-würde nach unten für den tatsächlichen Einsatz in einer hash-Tabelle. Während die einfacheren modulo einer Kraft-der-zwei-Tabelle gemacht dies deutlicher, es wurde auch eine negative Wirkung mit dem häufigeren Primzahl-Tabellen, das war einfach nicht so offensichtlich (die zusätzliche Arbeit in der Aufbereitung würde, überwiegen die Vorteile, aber der Vorteil würde noch da sein).
Edit: ich war auch die Verwendung von open-Adressierung, der auch erhöht die Empfindlichkeit gegenüber Kollision, vielleicht um so mehr, als die Tatsache, es war die Kraft-der-zwei.
Und gut, es war verstörend, wie viel die
string.GetHashCode()
Implementierungen in .NET (oder Studie hier) verbessert werden könnte, auf diese Weise (auf die Reihenfolge der tests läuft ungefähr 20-30 mal schneller, da weniger Kollisionen) und mehr verstörend, wie viel meine eigene hash-codes verbessert werden könnte (viel mehr als das).Alle die GetHashCode () - Implementierungen, die ich hatte, codiert in die Vergangenheit, und in der Tat verwendet als Grundlage der Antworten auf dieser Seite, waren viel schlimmer als würde ich durch. Viel von der Zeit war es "gut genug" für so viel verwendet, aber ich wollte etwas besseres.
Also legte ich das Projekt auf einer Seite (es wurde ein pet-Projekt sowieso) und suchte wie eine gute, gut verteilte hash-code .NET schnell.
Am Ende ließ ich mich auf die Portierung SpookyHash.NET. Ja der obige code ist ein schnell-Weg-version mit SpookyHash zu produzieren, die eine 32-bit-Ausgabe von einem 32-bit-input.
Nun, SpookyHash ist nicht ein nettes schnell zu merken, Stück code. Mein Hafen ist es noch weniger, weil ich hand-inlined, dass es viel bessere Geschwindigkeit****. Aber das ist, was die Wiederverwendung von code ist für.
Dann lege ich , dass Projekt auf der einen Seite, denn so wie das ursprüngliche Projekt produziert hatte, die Frage, wie eine bessere hash-code, so dass Projekt produziert die Frage, wie eine bessere .NET memcpy.
Dann kam ich zurück, und produziert eine Menge von überlastungen zu leicht feed gerade über alle einheimischen Arten (außer
decimal
†) in einen hash-code.Es ist schnell, für die Bob Jenkins verdient die meisten der Kredit, weil seine ursprüngliche code, den ich portiert von ist noch schneller, vor allem auf 64-bit-Maschinen, die der Algorithmus ist optimiert für‡.
Den vollständigen code kann man sich auf https://bitbucket.org/JonHanna/spookilysharp/src aber Bedenken Sie, dass der obige code ist eine vereinfachte version des es.
Jedoch, da es jetzt schon geschrieben, kann man machen, verwenden Sie es leichter:
Es dauert auch seed-Werte, so dass, wenn Sie benötigen, um mit nicht Vertrauenswürdige Eingabe verwendet, und bewahren wollen, gegen Hash-DoS-Angriffe können Sie einen Ausgangswert basierend auf der Betriebszeit oder ähnliches, und stellen Sie die Ergebnisse unvorhersehbar, die von Angreifern:
*Eine große überraschung ist hierbei, dass hand-inlining eine Drehung Methode zurückgegeben
(x << n) | (x >> -n)
verbessert. Hätte ich mir schon sicher, dass der jitter haben würde, inline, für mich, aber profiling zeigte sonst.†
decimal
ist nicht gebürtig von der .NETTO-Perspektive, aber es ist aus dem C#. Das problem mit ihm ist, dass seine eigenenGetHashCode()
behandelt die Präzision signifikant, während seine eigenenEquals()
nicht. Beide sind gültige Möglichkeiten, aber nicht gemischt, wie die. In der Umsetzung Ihrer eigenen version, die Sie benötigen, um wählen zu gehen, oder die anderen, aber ich kann nicht wissen, was Sie wollen.‡Vergleich. Wenn verwendet on a string, der SpookyHash auf 64 bit ist wesentlich schneller als
string.GetHashCode()
auf 32 bits, die ist etwas schneller alsstring.GetHashCode()
auf 64-bit deutlich schneller als SpookyHash auf 32 bit, aber immer noch schnell genug, um eine vernünftige Wahl.InformationsquelleAutor der Antwort Jon Hanna
Dies ist ein guter:
Und hier ist, wie es zu benutzen:
InformationsquelleAutor der Antwort Magnus
Hier mein vereinfachter Ansatz. Ich bin mit dem classic-builder pattern. Es ist typesafe (kein boxing/unboxing) und auch compatbile mit .NET 2.0 (ohne Erweiterung Methoden etc.).
Es wird wie folgt verwendet:
Und hier ist der eigentliche generator Klasse:
InformationsquelleAutor der Antwort bitbonk
Hier ist ein weiterer fließend Umsetzung von der Algorithmus oben geschrieben von Jon Skeet, aber die umfasst keine Zuwendungen oder Boxen Operationen:
Verwendung:
Wird der compiler sicherstellen
HashValue
wird nicht aufgerufen, mit einer Klasse aufgrund der generische Typ-Einschränkung. Aber es gibt keine compiler-Unterstützung fürHashObject
da das hinzufügen von ein generisches argument fügt auch eine boxing-operation.InformationsquelleAutor der Antwort Scott Wegner
Als der https://github.com/dotnet/coreclr/pull/14863, es ist ein neuer Weg zur Erzeugung von hash-codes, die ist super einfach! Schreiben Sie einfach
Diese erzeugen eine Qualität, hash-code, ohne dass Sie sich sorgen über die details der Implementierung.
InformationsquelleAutor der Antwort James Ko
Meisten der meine Arbeit mit Datenbank-Konnektivität, was bedeutet, dass meine Klassen haben alle eine eindeutige id aus der Datenbank. Ich benutze immer die ID aus der Datenbank zu generieren, die den hashcode.
InformationsquelleAutor der Antwort Mark G
ReSharper Nutzer generieren können GetHashCode, Equals und andere mit
ReSharper -> Edit -> Generate Code -> Equality Members
.InformationsquelleAutor der Antwort Charles Burns
Ziemlich ähnlich nightcoder Lösung außer es ist einfacher zu erheben Primzahlen, wenn Sie möchten.
PS: Dies ist eine jener Zeiten, in denen Sie kotzt ein wenig in Ihren Mund, wohl wissend, dass dies könnte umgestaltet werden in eine Methode, mit 9 Standard -, aber es wäre langsamer, so dass Sie einfach die Augen schließen und versuchen, es zu vergessen.
InformationsquelleAutor der Antwort Dbl
Ich lief in ein Problem mit floats und Dezimalzahlen mit der Implementierung gewählt als die obige Antwort.
Dieser test fehlschlägt (Schwimmer, hash ist das gleiche, obwohl ich wechselte 2 Werte negativ sein):
Aber dieser test geht (mit int):
Änderte ich meine Umsetzung nicht zu verwenden, GetHashCode für die primitiven Typen und es scheint zu funktionieren besser
InformationsquelleAutor der Antwort HokieMike
Microsoft führen mehrere Weg von hashing...
Ich kann mir vorstellen, dass für mehrere große int können Sie verwenden:
Und das gleiche für multi-Typ: alle konvertierten erste
int
mitGetHashCode()
dann die int-Werte werden xor-verknüpft, und das Resultat ist der Hashwert.
Für diejenigen, die Verwendung von hash als ID (ich meine einen eindeutigen Wert), hash ist natürlich beschränkt sich auf eine Anzahl von Ziffern, ich glaube, es war 5 bytes für den Hash-Algorithmus, mindestens MD5.
Können Sie mehrere Werte zu einem Hash-Wert, und einige von Ihnen werden gleich sein, so benutzen Sie es nicht als id. (vielleicht eines Tages ich werde Sie Ihre Komponente)
InformationsquelleAutor der Antwort deadManN
Wenn wir nicht mehr als 8 Eigenschaften (hoffentlich), hier ist eine weitere alternative.
ValueTuple
ist ein struct, und scheint eine solideGetHashCode
Umsetzung.Das heißt, wir könnten einfach so machen:
Lassen Sie uns nehmen einen Blick auf .NET Core ist die aktuelle Umsetzung für
ValueTuple
'sGetHashCode
.Dies ist aus
ValueTuple
:- Und dies ist von
HashHelper
:In Englisch:
Wäre es schön zu wissen, mehr über die Eigenschaften dieses ROL-5-hashCode-Algorithmus.
Leider verzögern
ValueTuple
für unsere eigenenGetHashCode
möglicherweise nicht so schnell, wie wir möchten und erwarten. Dieser Kommentar in einer verwandten Diskussion zeigt, dass direkt aufrufenHashHelpers.Combine
ist schneller. Auf der anderen Seite, dass man sich intern ist, so würden wir haben, um den code zu kopieren, zu opfern vieles von dem, was wir gewonnen hatte, hier. Auch, wir wären verantwortlich für das erinnern an den erstenCombine
mit den random seed. Ich weiß nicht, was die Konsequenzen sind, wenn wir diesen Schritt überspringen.InformationsquelleAutor der Antwort Timo