In .NET wird die GetHashCode Methode wird an vielen Stellen in den .NET-Basisklassenbibliotheken verwendet. Die korrekte Implementierung ist besonders wichtig, um Elemente schnell in einer Sammlung zu finden oder um Gleichheit zu bestimmen.
Gibt es einen Standardalgorithmus oder eine bewährte Praxis für die Umsetzung GetHashCode für meine benutzerdefinierten Klassen, damit ich die Leistung nicht beeinträchtige?
Normalerweise verwende ich so etwas wie die Implementierung in Josh Blochs märchenhaft Leistungsfähiges Java . Es ist schnell und erzeugt einen ziemlich guten Hash, bei dem es kaum zu Kollisionen kommen kann. Wählen Sie zwei verschiedene Primzahlen, z.B. 17 und 23, und tun Sie das:
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = 17;
// Suitable nullity checks etc, of course :)
hash = hash * 23 + field1.GetHashCode();
hash = hash * 23 + field2.GetHashCode();
hash = hash * 23 + field3.GetHashCode();
return hash;
}
}Wie in den Kommentaren erwähnt, ist es vielleicht besser, eine große Primzahl zu wählen, mit der man multipliziert. Anscheinend ist 486187739 gut... und obwohl die meisten Beispiele, die ich mit kleinen Zahlen gesehen habe, dazu neigen, Primzahlen zu verwenden, gibt es zumindest ähnliche Algorithmen, bei denen häufig Nicht-Primzahlen verwendet werden. In der Nicht-ganz- FNV Beispiel später habe ich zum Beispiel Zahlen verwendet, die offensichtlich gut funktionieren - aber der Anfangswert ist keine Primzahl. (Die Multiplikationskonstante est Aber prima. Ich weiß nicht genau, wie wichtig das ist.)
Dies ist besser als die gängige Praxis der XOR ing Hashcodes aus zwei Hauptgründen. Angenommen, wir haben einen Typ mit zwei int Felder:
XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, yÜbrigens ist der frühere Algorithmus derjenige, der derzeit vom C#-Compiler für anonyme Typen verwendet wird.
Diese Seite bietet eine ganze Reihe von Optionen. Ich denke, in den meisten Fällen ist das oben Genannte "gut genug" und es ist unglaublich einfach, es sich zu merken und richtig zu machen. Die FNV Alternative ist ähnlich einfach, verwendet aber andere Konstanten und XOR anstelle von ADD als eine kombinierende Operation. Sie sieht etwas wie der nachstehende Code, aber der normale FNV-Algorithmus arbeitet mit einzelnen Bytes, so dass eine Änderung erforderlich wäre, um eine Iteration pro Byte statt pro 32-Bit-Hash-Wert durchzuführen. FNV ist auch für variable Datenlängen ausgelegt, während wir ihn hier immer für dieselbe Anzahl von Feldwerten verwenden. Die Kommentare zu dieser Antwort deuten darauf hin, dass der Code hier (im getesteten Beispielfall) nicht so gut funktioniert wie der obige Additionsansatz.
// Note: Not quite FNV!
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = (int) 2166136261;
// Suitable nullity checks etc, of course :)
hash = (hash * 16777619) ^ field1.GetHashCode();
hash = (hash * 16777619) ^ field2.GetHashCode();
hash = (hash * 16777619) ^ field3.GetHashCode();
return hash;
}
}Beachten Sie, dass Sie idealerweise verhindern sollten, dass sich Ihr gleichheitssensitiver (und damit hashcode-sensitiver) Zustand ändert, nachdem Sie ihn zu einer Sammlung hinzugefügt haben, die vom Hashcode abhängt.
Gemäß der Dokumentation :
Sie können GetHashCode für unveränderliche Referenztypen außer Kraft setzen. Im Allgemeinen sollten Sie GetHashCode für veränderbare Referenztypen nur überschreiben, wenn:
- Sie können den Hash-Code aus Feldern berechnen, die nicht veränderbar sind; oder
- Sie können sicherstellen, dass sich der Hash-Code eines veränderlichen Objekts nicht ändert, während das Objekt in einer Sammlung enthalten ist, die auf seinen Hash-Code angewiesen ist.
Der Link zum FNV Artikel ist defekt, aber hier ist eine Kopie im Internet Archive: Ewig verwirrt - Die Kunst des Hashings
Wie @cactuaroid in den Kommentaren erwähnt, kann ein Wertetupel verwendet werden. Dies spart ein paar Tastenanschläge und, was noch wichtiger ist, es wird nur auf dem Stapel ausgeführt (kein Garbage):
(PropA, PropB, PropC, PropD).GetHashCode();(Anmerkung: Die ursprüngliche Technik, die anonyme Typen verwendet, scheint ein Objekt auf dem Heap zu erzeugen, d.h. Müll, da anonyme Typen als Klassen implementiert sind, obwohl dies vom Compiler optimiert werden könnte. Es wäre interessant, diese Optionen zu vergleichen, aber die Tupel-Option sollte besser sein).
Microsoft bietet bereits einen guten generischen HashCode-Generator: Kopieren Sie einfach Ihre Eigenschafts-/Feldwerte in einen anonymen Typ und verschlüsseln Sie ihn:
new { PropA, PropB, PropC, PropD }.GetHashCode();Dies funktioniert für eine beliebige Anzahl von Immobilien. Es wird kein Boxing verwendet. Es wird lediglich der bereits im Framework implementierte Algorithmus für anonyme Typen verwendet.
System.HashCodeWenn Sie .NET Standard 2.1 oder höher verwenden, können Sie die System.HashCode Struktur. Bei früheren Frameworks ist sie über die Microsoft.Bcl.HashCode Paket. Es gibt zwei Methoden, es zu verwenden:
El Combine kann zur Erstellung eines Hash-Codes mit bis zu acht Objekten verwendet werden.
public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);El Add Methode hilft Ihnen bei der Bearbeitung von Sammlungen:
public override int GetHashCode()
{
var hashCode = new HashCode();
hashCode.Add(this.object1);
foreach (var item in this.collection)
{
hashCode.Add(item);
}
return hashCode.ToHashCode();
}Eine Alternative zu System.HashCode das super einfach zu bedienen und trotzdem schnell ist. Sie können den vollständigen Blogbeitrag lesen ' GetHashCode leicht gemacht ' für weitere Einzelheiten und Kommentare.
public class SuperHero
{
public int Age { get; set; }
public string Name { get; set; }
public List<string> Powers { get; set; }
public override int GetHashCode() =>
HashCode.Of(this.Name).And(this.Age).AndEach(this.Powers);
}public struct HashCode : IEquatable<HashCode>
{
private const int EmptyCollectionPrimeNumber = 19;
private readonly int value;
private HashCode(int value) => this.value = value;
public static implicit operator int(HashCode hashCode) => hashCode.value;
public static bool operator ==(HashCode left, HashCode right) => left.Equals(right);
public static bool operator !=(HashCode left, HashCode right) => !(left == right);
public static HashCode Of<T>(T item) => new HashCode(GetHashCode(item));
public static HashCode OfEach<T>(IEnumerable<T> items) =>
items == null ? new HashCode(0) : new HashCode(GetHashCode(items, 0));
public HashCode And<T>(T item) =>
new HashCode(CombineHashCodes(this.value, GetHashCode(item)));
public HashCode AndEach<T>(IEnumerable<T> items)
{
if (items == null)
{
return new HashCode(this.value);
}
return new HashCode(GetHashCode(items, this.value));
}
public bool Equals(HashCode other) => this.value.Equals(other.value);
public override bool Equals(object obj)
{
if (obj is HashCode)
{
return this.Equals((HashCode)obj);
}
return false;
}
public override int GetHashCode() => this.value.GetHashCode();
private static int CombineHashCodes(int h1, int h2)
{
unchecked
{
// Code copied from System.Tuple a good way to combine hashes.
return ((h1 << 5) + h1) ^ h2;
}
}
private static int GetHashCode<T>(T item) => item?.GetHashCode() ?? 0;
private static int GetHashCode<T>(IEnumerable<T> items, int startHashCode)
{
var temp = startHashCode;
var enumerator = items.GetEnumerator();
if (enumerator.MoveNext())
{
temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
while (enumerator.MoveNext())
{
temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
}
}
else
{
temp = CombineHashCodes(temp, EmptyCollectionPrimeNumber);
}
return temp;
}
}Der Algorithmus, der einen Hash-Code berechnet, muss schnell sein. Ein einfacher Algorithmus ist in der Regel der schnellere. Ein Algorithmus, der keinen zusätzlichen Speicher zuweist, verringert auch den Bedarf an Garbage Collection, was wiederum die Leistung verbessert.
Speziell in C#-Hash-Funktionen verwenden Sie oft die unchecked Schlüsselwort, das die Überlaufprüfung beendet, um die Leistung zu verbessern.
Der Hashing-Algorithmus muss sein deterministisch d.h. bei gleichem Input muss er immer den gleichen Output produzieren.
Der Algorithmus, der einen Hash-Code berechnet, muss die Hash-Kollisionen auf ein Minimum reduziert werden. Eine Hash-Kollision ist eine Situation, die eintritt, wenn zwei Aufrufe von GetHashCode bei zwei verschiedenen Objekten identische Hash-Codes ergeben. Beachten Sie, dass Kollisionen zulässig sind (manche glauben fälschlicherweise, dass sie es nicht sind), aber sie sollten auf ein Minimum beschränkt werden.
Viele Hash-Funktionen enthalten magische Zahlen wie 17 o 23 . Diese sind besonders Primzahlen die aufgrund ihrer mathematischen Eigenschaften dazu beitragen, Hash-Kollisionen im Vergleich zur Verwendung von Nicht-Primzahlen zu verringern.
Eine gute Hash-Funktion sollte die erwarteten Eingaben so gleichmäßig wie möglich auf ihren Ausgabebereich abbilden, d. h. sie sollte einen breiten Bereich von Hashes auf der Grundlage ihrer Eingaben ausgeben, die gleichmäßig verteilt sind. Sie sollte eine Hash-Uniformität aufweisen.
In .NET Core erhalten Sie bei jedem Neustart einer Anwendung unterschiedliche Hash-Codes. Dies ist eine Sicherheitsfunktion, um Denial-of-Service-Angriffe (DoS) zu verhindern. Bei .NET Framework können Sie devrait aktivieren Sie diese Funktion, indem Sie die folgende App.config-Datei hinzufügen:
<?xml version ="1.0"?>
<configuration>
<runtime>
<UseRandomizedStringHashAlgorithm enabled="1" />
</runtime>
</configuration>Aufgrund dieser Eigenschaft sollten Hash-Codes niemals außerhalb der Anwendungsdomäne, in der sie erstellt wurden, verwendet werden, sie sollten niemals als Schlüsselfelder in einer Sammlung verwendet werden und sie sollten niemals persistiert werden.
Lesen Sie mehr darüber ici .
Der Algorithmus muss nicht zwangsläufig ein Kryptographische Hash-Funktion . Das bedeutet, dass sie die folgenden Bedingungen nicht erfüllen muss:
Hier ist mein Hashcode-Helfer.
Ihr Vorteil ist, dass sie Argumente vom generischen Typ verwendet und daher kein Boxing verursacht:
public static class HashHelper
{
public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
{
unchecked
{
return 31 * arg1.GetHashCode() + arg2.GetHashCode();
}
}
public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
{
unchecked
{
int hash = arg1.GetHashCode();
hash = 31 * hash + arg2.GetHashCode();
return 31 * hash + arg3.GetHashCode();
}
}
public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3,
T4 arg4)
{
unchecked
{
int hash = arg1.GetHashCode();
hash = 31 * hash + arg2.GetHashCode();
hash = 31 * hash + arg3.GetHashCode();
return 31 * hash + arg4.GetHashCode();
}
}
public static int GetHashCode<T>(T[] list)
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + item.GetHashCode();
}
return hash;
}
}
public static int GetHashCode<T>(IEnumerable<T> list)
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + item.GetHashCode();
}
return hash;
}
}
/// <summary>
/// Gets a hashcode for a collection for that the order of items
/// does not matter.
/// So {1, 2, 3} and {3, 2, 1} will get same hash code.
/// </summary>
public static int GetHashCodeForOrderNoMatterCollection<T>(
IEnumerable<T> list)
{
unchecked
{
int hash = 0;
int count = 0;
foreach (var item in list)
{
hash += item.GetHashCode();
count++;
}
return 31 * hash + count.GetHashCode();
}
}
/// <summary>
/// Alternative way to get a hashcode is to use a fluent
/// interface like this:<br />
/// return 0.CombineHashCode(field1).CombineHashCode(field2).
/// CombineHashCode(field3);
/// </summary>
public static int CombineHashCode<T>(this int hashCode, T arg)
{
unchecked
{
return 31 * hashCode + arg.GetHashCode();
}
}Außerdem verfügt es über eine Erweiterungsmethode, um eine fließende Schnittstelle bereitzustellen, so dass Sie es wie folgt verwenden können:
public override int GetHashCode()
{
return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}oder so:
public override int GetHashCode()
{
return 0.CombineHashCode(Manufacturer)
.CombineHashCode(PartN)
.CombineHashCode(Quantity);
}
Ich habe eine Hashing-Klasse in Helper-Bibliothek, dass ich es für diesen Zweck verwenden.
/// <summary>
/// This is a simple hashing function from Robert Sedgwicks Hashing in C book.
/// Also, some simple optimizations to the algorithm in order to speed up
/// its hashing process have been added. from: www.partow.net
/// </summary>
/// <param name="input">array of objects, parameters combination that you need
/// to get a unique hash code for them</param>
/// <returns>Hash code</returns>
public static int RSHash(params object[] input)
{
const int b = 378551;
int a = 63689;
int hash = 0;
// If it overflows then just wrap around
unchecked
{
for (int i = 0; i < input.Length; i++)
{
if (input[i] != null)
{
hash = hash * a + input[i].GetHashCode();
a = a * b;
}
}
}
return hash;
}Dann können Sie es einfach als verwenden:
public override int GetHashCode()
{
return Hashing.RSHash(_field1, _field2, _field3);
}Ich habe seine Leistung nicht bewertet, daher ist jedes Feedback willkommen.
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
