Was ist der beste Algorithmus zum Überschreiben von GetHashCode?

1449

In .NET wird die GetHashCodeMethode an vielen Stellen in den .NET-Basisklassenbibliotheken verwendet. Die ordnungsgemäße Implementierung ist besonders wichtig, um Elemente in einer Sammlung schnell zu finden oder um die Gleichheit zu bestimmen.

Gibt es einen Standardalgorithmus oder eine bewährte Methode für die Implementierung GetHashCodefür meine benutzerdefinierten Klassen, damit die Leistung nicht beeinträchtigt wird?

Bitbonk
quelle
38
Nachdem ich diese Frage und den folgenden Artikel gelesen hatte, konnte ich das Überschreiben von implementieren GetHashCode. Ich hoffe es wäre hilfreich für andere. Richtlinien und Regeln für GetHashCode geschrieben von Eric Lippert
rene
4
"oder Gleichheit bestimmen": nein! Zwei Objekte mit demselben Hashcode sind nicht unbedingt gleich.
Thomas Levesque
1
@ThomasLevesque Sie haben Recht, zwei Objekte mit demselben Hash-Code sind nicht unbedingt gleich. Wird aber immer GetHashCode()noch in sehr vielen Implementierungen von verwendet Equals(). Das habe ich mit dieser Aussage gemeint. GetHashCode()inside Equals()wird häufig als Verknüpfung zur Bestimmung der Ungleichung verwendet , da zwei Objekte, die einen unterschiedlichen Hash-Code haben, Objekte sein müssen, die nicht gleich sind, und der Rest der Gleichheitsprüfung nicht ausgeführt werden muss.
Bitbonk
3
@bitbonk Normalerweise sind beide GetHashCode()und Equals()müssen alle Felder beider Objekte betrachten (Equals muss dies tun, wenn die Hashcodes gleich oder nicht aktiviert sind). Aus diesem Grund ist ein Anruf nach GetHashCode()innen Equals()häufig redundant und kann die Leistung beeinträchtigen. Equals()Möglicherweise kann es auch zu einem Kurzschluss kommen, wodurch es viel schneller wird. In einigen Fällen werden die Hashcodes jedoch zwischengespeichert, wodurch die GetHashCode()Überprüfung schneller und lohnender wird. Weitere Informationen finden Sie in dieser Frage .
NotEnoughData
UPDATE JAN 2020: Eric Lipperts Blog unter: docs.microsoft.com/en-us/archive/blogs/ericlippert/…
Rick Davin

Antworten:

1604

Normalerweise gehe ich mit so etwas wie der Implementierung in Josh Blochs fabelhaftem Effective Java um . Es ist schnell und erzeugt einen ziemlich guten Hash, der wahrscheinlich keine Kollisionen verursacht. Wählen Sie zwei verschiedene Primzahlen, z. B. 17 und 23, und tun Sie Folgendes:

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 möglicherweise besser, stattdessen eine große Primzahl auszuwählen, mit der multipliziert werden soll. Anscheinend ist 486187739 gut ... und obwohl die meisten Beispiele, die ich mit kleinen Zahlen gesehen habe, Primzahlen verwenden, gibt es zumindest ähnliche Algorithmen, bei denen häufig Nicht-Primzahlen verwendet werden. In dem nicht ganz FNV- Beispiel später habe ich zum Beispiel Zahlen verwendet, die anscheinend gut funktionieren - aber der Anfangswert ist keine Primzahl. (Die Multiplikationskonstante ist jedoch eine Primzahl. Ich weiß nicht genau, wie wichtig das ist.)

Dies ist XORaus zwei Hauptgründen besser als die übliche Praxis, Hashcodes zu verwenden. Angenommen, wir haben einen Typ mit zwei intFeldern:

XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y

Der frühere Algorithmus wird übrigens derzeit vom C # -Compiler für anonyme Typen verwendet.

Diese Seite bietet einige Optionen. Ich denke, für die meisten Fälle ist das oben Genannte "gut genug" und es ist unglaublich einfach, sich zu erinnern und richtig zu machen. Die FNV- Alternative ist ähnlich einfach, verwendet jedoch unterschiedliche Konstanten und XORnicht ADDals Kombinationsoperation. Es sieht ungefähr so ​​aus wie der folgende Code, aber der normale FNV-Algorithmus arbeitet mit einzelnen Bytes, sodass eine Änderung erforderlich wäre, um eine Iteration pro Byte anstelle eines 32-Bit-Hashwerts durchzuführen. FNV ist auch für variable Datenlängen ausgelegt, während wir es hier immer für die gleiche Anzahl von Feldwerten verwenden. Kommentare zu dieser Antwort deuten darauf hin, dass der Code hier nicht so gut funktioniert (im getesteten Beispielfall) wie der oben beschriebene 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 im Idealfall verhindern sollten, dass sich Ihr gleichheitsempfindlicher (und damit hashcodeempfindlicher) Status ändert, nachdem Sie ihn einer Sammlung hinzugefügt haben, die vom Hashcode abhängt.

Gemäß Dokumentation :

Sie können GetHashCode für unveränderliche Referenztypen überschreiben. Im Allgemeinen sollten Sie für veränderbare Referenztypen GetHashCode 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 seinem Hash-Code basiert.
Jon Skeet
quelle
8
Der in dem von Ihnen erwähnten Buch beschriebene Algorithmus ist tatsächlich etwas detaillierter und beschreibt insbesondere, was für verschiedene Datentypen der Felder zu tun ist. Beispiel: Verwenden Sie für Felder vom Typ long (int) (Feld ^ f >>> 32), anstatt einfach GetHashcode aufzurufen. Ist long.GetHashCodes so implementiert?
Bitbonk
13
Ja, Int64.GetHashCode macht genau das. In Java würde das natürlich Boxen erfordern. Das erinnert mich - Zeit, einen Link zum Buch hinzuzufügen ...
Jon Skeet
77
23 ist keine gute Wahl, da (ab .net 3.5 SP1) eine Dictionary<TKey,TValue>gute Verteilung modulo bestimmter Primzahlen vorausgesetzt wird. Und 23 ist einer von ihnen. Wenn Sie also ein Wörterbuch mit Kapazität 23 haben, GetHashCodebeeinflusst nur der letzte Beitrag den zusammengesetzten Hashcode. Also würde ich lieber 29 statt 23 verwenden.
CodesInChaos
23
@CodeInChaos: Nur der letzte Beitrag beeinflusst den Bucket - daher muss er im schlimmsten Fall alle 23 Einträge im Wörterbuch durchsehen . Es wird immer noch der tatsächliche Hash-Code jedes Eintrags überprüft, was billig sein wird. Wenn Sie ein so kleines Wörterbuch haben, ist es unwahrscheinlich, dass es viel ausmacht.
Jon Skeet
20
@Vajda: Normalerweise verwende ich 0 als effektiven Hash-Code für null- was nicht gleichbedeutend ist mit dem Ignorieren des Feldes.
Jon Skeet
431

Anonymer Typ

Microsoft bietet bereits einen guten generischen HashCode-Generator: Kopieren Sie einfach Ihre Eigenschafts- / Feldwerte in einen anonymen Typ und hashen Sie ihn:

new { PropA, PropB, PropC, PropD }.GetHashCode();

Dies funktioniert für eine beliebige Anzahl von Eigenschaften. Es wird kein Boxen verwendet. Es wird nur der Algorithmus verwendet, der bereits im Framework für anonyme Typen implementiert ist.

ValueTuple - Update für C # 7

Wie @cactuaroid in den Kommentaren erwähnt, kann ein Wertetupel verwendet werden. Dies spart ein paar Tastenanschläge und wird vor allem nur auf dem Stapel ausgeführt (kein Müll):

(PropA, PropB, PropC, PropD).GetHashCode();

(Hinweis: Die ursprüngliche Technik, bei der anonyme Typen verwendet werden, scheint ein Objekt auf dem Heap zu erstellen, dh Garbage, da anonyme Typen als Klassen implementiert werden, obwohl dies möglicherweise vom Compiler optimiert wird. Es wäre interessant, diese Optionen zu vergleichen, aber die Die Tupeloption sollte überlegen sein.)

Rick Love
quelle
85
Ja, die anonyme GetHashCodeImplementierung ist sehr effektiv (übrigens die gleiche wie in der Antwort von Jon Skeet), aber das einzige Problem bei dieser Lösung ist, dass Sie bei jedem GetHashCodeAufruf eine neue Instanz generieren .
Dies kann
5
@digEmAll Guter Punkt, ich habe nicht über den Aufwand beim Erstellen eines neuen Objekts nachgedacht. Jon Skeets Antwort ist die effizienteste und verwendet kein Boxen. (@Kumba Um das ungeprüfte in VB zu lösen, verwenden Sie einfach ein Int64 (lang) und schneiden Sie es nach den Berechnungen ab.)
Rick Love
42
nur könnte sagen new { PropA, PropB, PropC, PropD }.GetHashCode()zu
sehe
17
VB.NET muss Key bei der Erstellung anonymer Typen verwenden: New With {Key PropA}.GetHashCode()Andernfalls gibt GetHashCode nicht denselben Hashcode für verschiedene Objekte mit denselben 'identifizierenden' Eigenschaften zurück.
David Osborne
4
@Keith In diesem Fall würde ich in Betracht ziehen, die IEnumerable irgendwo als Listenwert zu speichern, anstatt sie jedes Mal aufzulisten, wenn der Hashcode berechnet wird. Das erneute Berechnen der ToList in GetHashCode kann in vielen Situationen die Leistung beeinträchtigen.
Rick Love
105

Hier ist mein Hashcode-Helfer.
Der Vorteil ist, dass generische Typargumente verwendet werden und daher kein Boxen verursacht wird:

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 flüssige Schnittstelle bereitzustellen, sodass Sie sie folgendermaßen 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);
}
Nachtcodierer
quelle
5
Keine Notwendigkeit für T[]separat, wie es bereits istIEnumerable<T>
nawfal
5
Sie könnten diese Methoden umgestalten und die Kernlogik auf eine Funktion beschränken
nawfal
12
Übrigens ist 31 eine Verschiebung und Subtraktion auf der CPU, was außerordentlich schnell ist.
Chui Tey
4
@nightcoder Sie könnten params verwenden .
Aneves
6
@ChuiTey Dies ist etwas, das alle Mersenne Primes gemeinsam haben.
Pharap
63

Ich habe eine Hashing-Klasse in der Helper-Bibliothek, die ich für diesen Zweck verwende.

/// <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 verwenden als:

public override int GetHashCode()
{
    return Hashing.RSHash(_field1, _field2, _field3);
}

Ich habe die Leistung nicht bewertet, daher ist jedes Feedback willkommen.

Wahid Shalaly
quelle
26
Nun, es wird Boxen verursachen, wenn Felder Werttypen sind.
Nightcoder
5
"kann später durch Abfangen der OverflowException erweitert werden" Der springende Punkt uncheckedist, Ausnahmen beim Überlauf zu vermeiden, die bei gewünscht werden GetHashCode. Es ist also nicht falsch, wenn der Wert überläuft intund es überhaupt nicht weh tut.
Tim Schmelter
1
Ein Problem mit diesem Algorithmus ist, dass jedes Array voller Nullen immer 0 zurückgibt, unabhängig von seiner Länge
Nathan Adams
2
Diese Hilfsmethode weist auch ein neues Objekt zu []
James Newton-King
1
Wie @NathanAdams erwähnt, kann die Tatsache, dass nulles vollständig übersprungen wird, zu unerwarteten Ergebnissen führen. Anstatt sie zu überspringen, sollten Sie nur einen konstanten Wert verwenden, anstatt input[i].GetHashCode()wann input[i]null ist.
David Schwartz
58

Hier ist meine Hilfsklasse mit Jon Skeets Implementierung .

public static class HashCode
{
    public const int Start = 17;

    public static int Hash<T>(this int hash, T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked((hash * 31) + h);
    }
}

Verwendungszweck:

public override int GetHashCode()
{
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)
        .Hash(_field3);
}

Wenn Sie vermeiden möchten, eine Erweiterungsmethode für System.Int32 zu schreiben:

public readonly struct HashCode
{
    private readonly int _value;

    public HashCode(int value) => _value = value;

    public static HashCode Start { get; } = new HashCode(17);

    public static implicit operator int(HashCode hash) => hash._value;

    public HashCode Hash<T>(T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked(new HashCode((_value * 31) + h));
    }

    public override int GetHashCode() => _value;
}

Es vermeidet weiterhin jede Heap-Zuordnung und wird genauso verwendet:

public override int GetHashCode()
{
    // This time `HashCode.Start` is not an `Int32`, it's a `HashCode` instance.
    // And the result is implicitly converted to `Int32`.
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)     
        .Hash(_field3);
}

Bearbeiten (Mai 2018): EqualityComparer<T>.DefaultGetter ist jetzt ein JIT-Intrinsic - die Pull-Anfrage wird von Stephen Toub in diesem Blog-Beitrag erwähnt .

Şafak Gür
quelle
1
Ich würde die Linie mit dem tertiären Betreiber ändern, um zu sein:var h = Equals(obj, default(T)) ? 0 : obj.GetHashCode();
Bill Barry
Ich glaube, dass der ternäre Operator mit obj != nullzu einer boxAnweisung kompiliert wird, die Speicher zuweist, wenn Tes sich um einen Werttyp handelt. Stattdessen können Sie verwenden, obj.Equals(null)was zu einem virtuellen Aufruf der EqualsMethode kompiliert wird.
Martin Liversage
Weil this.hashCode != h. Es würde nicht den gleichen Wert zurückgeben.
Şafak Gür
Entschuldigung, es gelingt mir, meinen Kommentar zu entfernen, anstatt ihn zu bearbeiten. Ist es vorteilhafter, eine neue Struktur zu erstellen, als den HashCode in nicht schreibgeschützt zu ändern und Folgendes zu tun: "ungeprüft {this.hashCode ^ = h * 397;} return this;" zum Beispiel?
Erik Karlsson
Unveränderlichkeit hat ihre Vorteile ( Warum sind veränderbare Strukturen böse? ). Was die Leistung betrifft, ist das, was ich mache, ziemlich billig, da es keinen Speicherplatz auf dem Heap zuweist.
Şafak Gür
30

.NET Standard 2.1 und höher

Wenn Sie .NET Standard 2.1 oder höher verwenden, können Sie die System.HashCode- Struktur verwenden. Es gibt zwei Methoden, um es zu verwenden:

HashCode.Combine

Die CombineMethode kann verwendet werden, um einen Hash-Code mit bis zu acht Objekten zu erstellen.

public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);

HashCode.Add

Die AddMethode hilft Ihnen beim Umgang mit 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();
}

GetHashCode leicht gemacht

Sie können den vollständigen Blog-Beitrag ' GetHashCode Made Easy ' für weitere Details und Kommentare lesen .

Anwendungsbeispiel

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);
}

Implementierung

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;
    }
}

Was macht einen guten Algorithmus aus?

Geschwindigkeit

Der Algorithmus, der einen Hash-Code berechnet, muss schnell sein. Ein einfacher Algorithmus wird normalerweise schneller sein.

Deterministisch

Der Hashing-Algorithmus muss deterministisch sein, dh bei gleicher Eingabe muss er immer dieselbe Ausgabe erzeugen.

Kollisionen reduzieren

Der Algorithmus, der einen Hash-Code berechnet, muss die Hash-Kollisionen auf ein Minimum beschränken. Eine Hash-Kollision ist eine Situation, die auftritt, wenn zwei Aufrufe GetHashCodevon zwei verschiedenen Objekten identische Hash-Codes erzeugen. Beachten Sie, dass Kollisionen zulässig sind (einige haben die falschen Vorstellungen, dass dies nicht der Fall ist), sie sollten jedoch auf ein Minimum beschränkt werden.

Eine gute Hash-Funktion sollte die erwarteten Eingaben über ihren Ausgabebereich so gleichmäßig wie möglich abbilden. Es sollte einheitlich sein.

Verhindern Sie DoS

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. Für .NET Framework sollten Sie diese Funktion aktivieren, indem Sie die folgende App.config-Datei hinzufügen:

<?xml version ="1.0"?>  
<configuration>  
   <runtime>  
      <UseRandomizedStringHashAlgorithm enabled="1" />  
   </runtime>  
</configuration>

Aufgrund dieser Funktion sollten Hash-Codes niemals außerhalb der Anwendungsdomäne verwendet werden, in der sie erstellt wurden. Sie sollten niemals als Schlüsselfelder in einer Sammlung verwendet werden und niemals beibehalten werden.

Lesen Sie mehr dazu hier .

Kryptographisch sicher?

Der Algorithmus muss keine kryptografische Hash-Funktion sein . Das heißt, es muss nicht die folgenden Bedingungen erfüllen:

  • Es ist nicht möglich, eine Nachricht zu generieren, die einen bestimmten Hashwert ergibt
  • Es ist nicht möglich, zwei verschiedene Nachrichten mit demselben Hashwert zu finden
  • Eine kleine Änderung an einer Nachricht sollte den Hash-Wert so stark ändern, dass der neue Hash-Wert nicht mit dem alten Hash-Wert korreliert erscheint (Lawineneffekt).
Muhammad Rehan Saeed
quelle
29

In den meisten Fällen, in denen Equals () mehrere Felder vergleicht, spielt es keine Rolle, ob GetHash () auf einem oder mehreren Feldern hascht. Sie müssen nur sicherstellen, dass die Berechnung des Hashs wirklich billig ( bitte keine Zuordnungen ) und schnell ( keine umfangreichen Berechnungen und sicherlich keine Datenbankverbindungen) ist und eine gute Verteilung bietet.

Das schwere Heben sollte Teil der Equals () -Methode sein. Der Hash sollte eine sehr billige Operation sein, um das Aufrufen von Equals () für so wenige Elemente wie möglich zu ermöglichen.

Und noch ein letzter Tipp: Verlassen Sie sich nicht darauf, dass GetHashCode () über mehrere Anwendungsläufe hinweg stabil ist . Viele .Net-Typen garantieren nicht, dass ihre Hash-Codes nach einem Neustart gleich bleiben. Daher sollten Sie den Wert von GetHashCode () nur für Speicherdatenstrukturen verwenden.

Bert Huijben
quelle
10
"In den meisten Fällen, in denen Equals () mehrere Felder vergleicht, spielt es keine Rolle, ob GetHash () auf einem oder mehreren Feldern hascht." Dies ist ein gefährlicher Ratschlag, da bei Objekten, die sich nur in den nicht gehashten Feldern unterscheiden, Hash-Kollisionen auftreten. Wenn dies häufig vorkommt, wird die Leistung von Hash-basierten Sammlungen (HashMap, HashSet usw.) beeinträchtigt (im schlimmsten Fall bis zu O (n)).
Sleske
10
Dies geschah tatsächlich in Java: In früheren Versionen des JDK String.hashCode () wurde nur der Anfang des Strings berücksichtigt; Dies führte zu Leistungsproblemen, wenn Sie Strings als Schlüssel in HashMaps verwendeten, die sich nur am Ende unterschieden (was z. B. für URLs üblich ist). Der Algorithmus wurde daher geändert (in JDK 1.2 oder 1.3 glaube ich).
Sleske
3
Wenn dieses eine Feld 'eine gute Verteilung liefert' (letzter Teil meiner Antwort), reicht ein Feld aus. Wenn es keine gute Verteilung liefert , brauchen Sie (und gerade dann) eine andere Berechnung. (Verwenden Sie
zB
Ich glaube nicht, dass es ein Problem gibt GetHashCode, Speicherzuweisungen durchzuführen, vorausgesetzt, dies geschieht nur bei der ersten Verwendung (bei nachfolgenden Aufrufen wird einfach ein zwischengespeichertes Ergebnis zurückgegeben). Wichtig ist nicht, dass man große Anstrengungen unternimmt, um Kollisionen zu vermeiden, sondern dass man "systemische" Kollisionen vermeidet. Wenn ein Typ zwei intFelder hat oldXund sich newXhäufig um eins unterscheiden, würde ein Hashwert von oldX^newX90% solcher Datensätze Hashwerte von 1, 2, 4 oder 8 zuweisen. Die Verwendung von oldX+newX[nicht
aktivierte
1
... als eine ausgefeiltere Funktion, aber eine Sammlung von 1.000.000 Dingen mit 500.000 verschiedenen Hashwerten ist sehr gut, wenn jedem Hashwert zwei Dinge zugeordnet sind, und sehr schlecht, wenn ein Hashwert 500.001 Dinge hat und die anderen jeweils einen.
Supercat
23

Bis vor kurzem wäre meine Antwort Jon Skeets hier sehr nahe gekommen. Ich habe jedoch kürzlich ein Projekt gestartet, das Zweierpotenz-Hash-Tabellen verwendet, dh Hash-Tabellen, bei denen die Größe der internen Tabelle 8, 16, 32 usw. beträgt. Es gibt einen guten Grund, Primzahlengrößen zu bevorzugen, aber dort sind auch einige Vorteile für Zweierpotenzgrößen.

Und es saugte ziemlich viel. Nach einigem Experimentieren und Nachforschen begann ich, meine Hashes mit den folgenden Schritten neu zu hashen:

public static int ReHash(int source)
{
  unchecked
  {
    ulong c = 0xDEADBEEFDEADBEEF + (ulong)source;
    ulong d = 0xE2ADBEEFDEADBEEF ^ c;
    ulong a = d += c = c << 15 | c >> -15;
    ulong b = a += d = d << 52 | d >> -52;
    c ^= b += a = a << 26 | a >> -26;
    d ^= c += b = b << 51 | b >> -51;
    a ^= d += c = c << 28 | c >> -28;
    b ^= a += d = d << 9 | d >> -9;
    c ^= b += a = a << 47 | a >> -47;
    d ^= c += b << 54 | b >> -54;
    a ^= d += c << 32 | c >> 32;
    a += d << 25 | d >> -25;
    return (int)(a >> 1);
  }
}

Und dann saugte meine Zwei-Potenz-Hash-Tabelle nicht mehr.

Das hat mich allerdings gestört, weil das oben genannte nicht funktionieren sollte. Genauer gesagt sollte es nicht funktionieren, es sei denn, das Original GetHashCode()war auf ganz besondere Weise schlecht.

Das erneute Mischen eines Hashcodes kann einen großartigen Hashcode nicht verbessern, da der einzig mögliche Effekt darin besteht, dass wir einige weitere Kollisionen einführen.

Das erneute Mischen eines Hash-Codes kann einen schrecklichen Hash-Code nicht verbessern, da der einzig mögliche Effekt darin besteht, dass wir beispielsweise eine große Anzahl von Kollisionen auf Wert 53 in eine große Anzahl von Wert 18.3487.291 ändern.

Das erneute Mischen eines Hash-Codes kann nur einen Hash-Code verbessern, der zumindest ziemlich gut absolute Kollisionen in seinem gesamten Bereich (2 32 mögliche Werte) vermeidet, aber Kollisionen schlecht vermeidet, wenn er für die tatsächliche Verwendung in einer Hash-Tabelle heruntergefahren wird. Das einfachere Modulo einer Zweierpotenztabelle machte dies deutlicher, wirkte sich jedoch auch negativ auf die häufigeren Primzahltabellen aus, was jedoch nicht so offensichtlich war (die zusätzliche Arbeit beim Aufwärmen würde den Vorteil überwiegen , aber der Nutzen wäre immer noch da).

Bearbeiten: Ich habe auch Open-Addressing verwendet, was auch die Kollisionsempfindlichkeit erhöht hätte, vielleicht mehr als die Tatsache, dass es sich um eine Zweierpotenz handelt.

Und nun, es war beunruhigend, um wie viel die string.GetHashCode()Implementierungen in .NET (oder hier zu studieren ) auf diese Weise verbessert werden konnten (in der Größenordnung von Tests, die aufgrund weniger Kollisionen etwa 20 bis 30 Mal schneller ablaufen) und beunruhigender, wie viel meine eigenen Hash-Codes könnte verbessert werden (viel mehr als das).

Alle GetHashCode () -Implementierungen, die ich in der Vergangenheit codiert und tatsächlich als Grundlage für die Antworten auf dieser Site verwendet hatte, waren viel schlechter als ich . Die meiste Zeit war es "gut genug" für viele Zwecke, aber ich wollte etwas Besseres.

Also legte ich dieses Projekt beiseite (es war sowieso ein Lieblingsprojekt) und begann zu überlegen, wie man schnell einen guten, gut verteilten Hash-Code in .NET erstellt.

Am Ende habe ich mich entschlossen , SpookyHash nach .NET zu portieren . In der Tat ist der obige Code eine Fast-Path-Version der Verwendung von SpookyHash, um eine 32-Bit-Ausgabe von einer 32-Bit-Eingabe zu erzeugen.

Jetzt ist SpookyHash kein guter, schnell zu merkender Code. Mein Port davon ist noch weniger, weil ich viel von Hand für eine bessere Geschwindigkeit * eingefügt habe. Aber dafür ist die Wiederverwendung von Code gedacht.

Dann habe ich dieses Projekt beiseite gelegt, weil genau wie das ursprüngliche Projekt die Frage aufgeworfen hatte, wie ein besserer Hash-Code erzeugt werden kann, so hat dieses Projekt die Frage aufgeworfen, wie ein besserer .NET-Speicher erstellt werden kann.

Dann kam ich zurück und erzeugte viele Überladungen, um fast alle nativen Typen (außer decimal†) einfach in einen Hash-Code einzugeben.

Es ist schnell, wofür Bob Jenkins den größten Teil der Anerkennung verdient, da sein ursprünglicher Code, von dem ich portiert habe, noch schneller ist, insbesondere auf 64-Bit-Computern, für die der Algorithmus optimiert ist.

Der vollständige Code kann unter https://bitbucket.org/JonHanna/spookilysharp/src eingesehen werden. Beachten Sie jedoch, dass der obige Code eine vereinfachte Version davon ist.

Da es jetzt bereits geschrieben ist, kann man es leichter verwenden:

public override int GetHashCode()
{
  var hash = new SpookyHash();
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

Es werden auch Startwerte verwendet. Wenn Sie also mit nicht vertrauenswürdigen Eingaben umgehen müssen und sich vor Hash-DoS-Angriffen schützen möchten, können Sie einen Startwert basierend auf der Verfügbarkeit oder ähnlichem festlegen und die Ergebnisse für Angreifer unvorhersehbar machen:

private static long hashSeed0 = Environment.TickCount;
private static long hashSeed1 = DateTime.Now.Ticks;
public override int GetHashCode()
{
  //produce different hashes ever time this application is restarted
  //but remain consistent in each run, so attackers have a harder time
  //DoSing the hash tables.
  var hash = new SpookyHash(hashSeed0, hashSeed1);
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

* Eine große Überraschung dabei ist das Hand-Inlining einer Rotationsmethode, die (x << n) | (x >> -n)verbesserte Ergebnisse liefert . Ich wäre mir sicher gewesen, dass der Jitter das für mich eingefügt hätte, aber die Profilerstellung zeigte etwas anderes.

decimalist aus .NET-Sicht nicht nativ, obwohl es aus C # stammt. Das Problem dabei ist, dass seine eigene GetHashCode()Präzision als signifikant behandelt wird, während seine eigene Equals()dies nicht tut. Beide sind gültige Entscheidungen, aber nicht so gemischt. Bei der Implementierung Ihrer eigenen Version müssen Sie sich für die eine oder andere Version entscheiden, aber ich kann nicht wissen, welche Sie möchten.

‡ Zum Vergleich. Bei Verwendung für eine Zeichenfolge ist der SpookyHash auf 64 Bit erheblich schneller als string.GetHashCode()auf 32 Bit, was etwas schneller ist als string.GetHashCode()auf 64 Bit, was erheblich schneller ist als der SpookyHash auf 32 Bit, obwohl er immer noch schnell genug ist, um eine vernünftige Wahl zu sein.

Jon Hanna
quelle
Wenn ich mehrere Hash-Werte zu einem kombiniere, tendiere ich dazu, longWerte für die Zwischenergebnisse zu verwenden und dann das Endergebnis auf einen zu reduzieren int. Scheint das eine gute Idee zu sein? Ich mache mir Sorgen, dass man zB hash = (hash * 31) + nextField verwendet, dann wirken sich Paare von übereinstimmenden Werten nur auf die oberen 27 Bits des Hash aus. Wenn Sie die Berechnung auf a ausdehnen longund Inhalte einwickeln, wird diese Gefahr minimiert.
Supercat
@supercat es hängt von der Verteilung deines endgültigen Mungings ab. Die SpookilySharp-Bibliothek würde sicherstellen, dass die Verteilung gut ist, idealerweise (da keine Objekterstellung erforderlich ist), indem sie einen Zeiger auf einen blittbaren Typ oder eine der von ihr direkt verarbeiteten Aufzählungen übergibt, wenn Sie jedoch noch keine blittable haben Daten oder eine geeignete Aufzählung, dann das Aufrufen .Update()mit den mehreren Werten gemäß der obigen Antwort reicht aus.
Jon Hanna
@ JonHanna wären Sie bereit, mit dem problematischen Verhalten, auf das Sie gestoßen sind, genauer umzugehen? Ich versuche, eine Bibliothek zu implementieren, die die Implementierung von Wertobjekten trivial macht ( ValueUtils ), und ich würde ein Testset lieben, das eine schlechte Mischbarkeit von Hashs in Zweierpotenz-Hashtabellen demonstriert.
Eamon Nerbonne
@EamonNerbonne Ich habe nichts genaueres als "Die Gesamtzeit war auf diese Weise langsamer". Wie ich in einer Bearbeitung hinzugefügt habe, war die Tatsache, dass ich Open-Addressing verwendet habe, möglicherweise wichtiger als der Faktor der Zweierpotenz. Ich habe vor, einige Testfälle für ein bestimmtes Projekt durchzuführen, in denen ich einige verschiedene Ansätze vergleichen werde, damit ich danach möglicherweise eine bessere Antwort für Sie habe, obwohl dies keine hohe Priorität hat (ein persönliches Projekt ohne dringenden Bedarf) , also werde ich es bekommen, wenn ich dazu komme ...)
Jon Hanna
@ JonHanna: Ja, ich weiß, wie der persönliche Projektplan verläuft - viel Glück! Auf jeden Fall habe ich diesen letzten Kommentar nicht gut formuliert: Ich wollte nach dem problematischen Input fragen und nicht unbedingt nach den Details der daraus resultierenden Probleme. Ich würde das gerne als Test-Set (oder Inspiration für ein Test-Set) verwenden. Auf jeden Fall - viel Glück bei Ihrem Lieblingsprojekt :-).
Eamon Nerbonne
13

Das ist ein guter:

/// <summary>
/// Helper class for generating hash codes suitable 
/// for use in hashing algorithms and data structures like a hash table. 
/// </summary>
public static class HashCodeHelper
{
    private static int GetHashCodeInternal(int key1, int key2)
    {
        unchecked
        {
           var num = 0x7e53a269;
           num = (-1521134295 * num) + key1;
           num += (num << 10);
           num ^= (num >> 6);

           num = ((-1521134295 * num) + key2);
           num += (num << 10);
           num ^= (num >> 6);

           return num;
        }
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="arr">An array of objects used for generating the 
    /// hash code.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode(params object[] arr)
    {
        int hash = 0;
        foreach (var item in arr)
            hash = GetHashCodeInternal(hash, item.GetHashCode());
        return hash;
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <param name="obj4">The fourth object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and
    /// data structures like a hash table.
    /// </returns>
    public static int GetHashCode<T1, T2, T3, T4>(T1 obj1, T2 obj2, T3 obj3,
        T4 obj4)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3, obj4));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2, T3>(T1 obj1, T2 obj2, T3 obj3)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2>(T1 obj1, T2 obj2)
    {
        return GetHashCodeInternal(obj1.GetHashCode(), obj2.GetHashCode());
    }
}

Und so geht's:

private struct Key
{
    private Type _type;
    private string _field;

    public Type Type { get { return _type; } }
    public string Field { get { return _field; } }

    public Key(Type type, string field)
    {
        _type = type;
        _field = field;
    }

    public override int GetHashCode()
    {
        return HashCodeHelper.GetHashCode(_field, _type);
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Key))
            return false;
        var tf = (Key)obj;
        return tf._field.Equals(_field) && tf._type.Equals(_type);
    }
}
Magnus
quelle
1
Wie werden die Schlüssel bestimmt? GetHashCode () akzeptiert keine Parameter, daher muss dieser mit zwei Schlüsseln aufgerufen werden, die irgendwie bestimmt werden müssen. Entschuldigung, ohne weitere Erklärung sieht das nur klug aus, aber nicht so gut.
Michael Stum
Und warum brauchen Sie die generischen Überladungen? Der Typ ist nicht wichtig (und wird in Ihrem Code nicht verwendet), da alle Objekte eine GetHashCode()Methode haben, sodass Sie die Methode immer mit dem paramsArray-Parameter verwenden können. Oder fehlt mir hier etwas?
gehho
4
Wenn Sie Objekt anstelle von Generika verwenden, erhalten Sie Boxing- und Speicherzuordnungen, die Sie in GetHashCode nicht möchten. Generika sind also der richtige Weg.
CodesInChaos
1
Die h += (h << 10); h ^= (h >> 6); h += (h << 3); h ^= (h >> 11); h += (h << 15);nachfolgenden Shift / Xor-Schritte ( haben einen Code-Geruch: Sie hängen von keiner der Eingaben ab und sehen für mich schrecklich überflüssig aus.
sehe
1
@Magnus ja richtig, ich werde meinen ursprünglichen Kommentar löschen. Nur eine kleine Anmerkung, dass dies möglicherweise nicht so schnell ist wie einige andere Lösungen hier, aber wie Sie sagen, sollte es keine Rolle spielen. Die Verteilung ist großartig, besser als die meisten Lösungen hier, also +1 von mir! :)
Nawfal
11

Ab https://github.com/dotnet/coreclr/pull/14863 gibt es eine neue Möglichkeit, Hash-Codes zu generieren, die sehr einfach ist! Einfach schreiben

public override int GetHashCode()
    => HashCode.Combine(field1, field2, field3);

Dadurch wird ein Qualitäts-Hash-Code generiert, ohne dass Sie sich um die Implementierungsdetails kümmern müssen.

James Ko
quelle
Das sieht nach einer süßen Ergänzung aus ... gibt es eine Möglichkeit zu wissen, in welcher Version von .NET Core das Produkt enthalten sein wird?
Dan J
1
@DanJ Was für ein glücklicher Zufall, die HashCodeÄnderungen für corefx wurden nur wenige Stunden vor Ihrem Kommentar zusammengeführt :) Der Typ soll in .NET Core 2.1 ausgeliefert werden.
James Ko
Das ist großartig - und die ganze Bearbeitungszeit. Upvoted. :)
Dan J
@DanJ Noch bessere Nachrichten - es sollte ab sofort in den nächtlichen Builds von CoreFX verfügbar sein, die im Dotnet-Core-MyGet-Feed gehostet werden.
James Ko
Süß - das hilft mir bei der Arbeit nicht, da wir nicht ganz auf dem neuesten Stand sind, aber gut zu wissen. Prost!
Dan J
9

Hier ist eine weitere fließende Implementierung des oben von Jon Skeet veröffentlichten Algorithmus , die jedoch keine Zuweisungen oder Boxoperationen enthält:

public static class Hash
{
    public const int Base = 17;

    public static int HashObject(this int hash, object obj)
    {
        unchecked { return hash * 23 + (obj == null ? 0 : obj.GetHashCode()); }
    }

    public static int HashValue<T>(this int hash, T value)
        where T : struct
    {
        unchecked { return hash * 23 + value.GetHashCode(); }
    }
}

Verwendungszweck:

public class MyType<T>
{
    public string Name { get; set; }

    public string Description { get; set; }

    public int Value { get; set; }

    public IEnumerable<T> Children { get; set; }

    public override int GetHashCode()
    {
        return Hash.Base
            .HashObject(this.Name)
            .HashObject(this.Description)
            .HashValue(this.Value)
            .HashObject(this.Children);
    }
}

Der Compiler stellt sicher, dass HashValueaufgrund der generischen Typbeschränkung nicht mit einer Klasse aufgerufen wird. Es gibt jedoch keine Compiler-Unterstützung, HashObjectda durch Hinzufügen eines generischen Arguments auch eine Boxoperation hinzugefügt wird.

Scott Wegner
quelle
8

Hier ist mein simpler Ansatz. Ich verwende dafür das klassische Builder-Muster. Es ist typsicher (kein Boxen / Unboxing) und auch kompatibel mit .NET 2.0 (keine Erweiterungsmethoden usw.).

Es wird so verwendet:

public override int GetHashCode()
{
    HashBuilder b = new HashBuilder();
    b.AddItems(this.member1, this.member2, this.member3);
    return b.Result;
} 

Und hier ist die akute Builder-Klasse:

internal class HashBuilder
{
    private const int Prime1 = 17;
    private const int Prime2 = 23;
    private int result = Prime1;

    public HashBuilder()
    {
    }

    public HashBuilder(int startHash)
    {
        this.result = startHash;
    }

    public int Result
    {
        get
        {
            return this.result;
        }
    }

    public void AddItem<T>(T item)
    {
        unchecked
        {
            this.result = this.result * Prime2 + item.GetHashCode();
        }
    }

    public void AddItems<T1, T2>(T1 item1, T2 item2)
    {
        this.AddItem(item1);
        this.AddItem(item2);
    }

    public void AddItems<T1, T2, T3>(T1 item1, T2 item2, T3 item3)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
    }

    public void AddItems<T1, T2, T3, T4>(T1 item1, T2 item2, T3 item3, 
        T4 item4)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
    }

    public void AddItems<T1, T2, T3, T4, T5>(T1 item1, T2 item2, T3 item3, 
        T4 item4, T5 item5)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
        this.AddItem(item5);
    }        

    public void AddItems<T>(params T[] items)
    {
        foreach (T item in items)
        {
            this.AddItem(item);
        }
    }
}
Bitbonk
quelle
Sie können die Objekterstellung innerhalb der Gethashcode-Funktion wie in Mangus 'Antwort vermeiden. Rufen Sie einfach die verdammt statischen Hash-Funktionen auf (wer kümmert sich um Starter-Hash). Außerdem können Sie die AddItems<T>(params T[] items)Methode in der Hilfsklasse häufiger verwenden (als AddItem(T)jedes Mal aufzurufen ).
Nawfal
Und welchen Nutzen finden Sie this.result * Prime2 * item.GetHashCode()bei häufigem Gebrauch this.result * Prime2 + item.GetHashCode()?
Nawfal
Ich kann nicht AddItems<T>(params T[] items)öfter verwenden, weil typeof(T1) != typeof(T2)usw.
Bitbonk
Oh ja, das habe ich verpasst.
Nawfal
5

ReSharper- Benutzer können GetHashCode, Equals und andere mit generieren ReSharper -> Edit -> Generate Code -> Equality Members.

// ReSharper's GetHashCode looks like this
public override int GetHashCode() {
    unchecked {
        int hashCode = Id;
        hashCode = (hashCode * 397) ^ IntMember;
        hashCode = (hashCode * 397) ^ OtherIntMember;
        hashCode = (hashCode * 397) ^ (RefMember != null ? RefMember.GetHashCode() : 0);
        // ...
        return hashCode;
    }
}
Charles Burns
quelle
4

Wenn wir (hoffentlich) nicht mehr als 8 Eigenschaften haben, ist hier eine andere Alternative.

ValueTupleist eine Struktur und scheint eine solide GetHashCodeImplementierung zu haben .

Das heißt, wir könnten dies einfach tun:

// Yay, no allocations and no custom implementations!
public override int GetHashCode() => (this.PropA, this.PropB).GetHashCode();

Werfen wir einen Blick auf .NET Core aktuelle Implementierung für ValueTuple‚s GetHashCode.

Dies ist aus ValueTuple:

    internal static int CombineHashCodes(int h1, int h2)
    {
        return HashHelpers.Combine(HashHelpers.Combine(HashHelpers.RandomSeed, h1), h2);
    }

    internal static int CombineHashCodes(int h1, int h2, int h3)
    {
        return HashHelpers.Combine(CombineHashCodes(h1, h2), h3);
    }

Und das ist von HashHelper:

    public static readonly int RandomSeed = Guid.NewGuid().GetHashCode();

    public static int Combine(int h1, int h2)
    {
        unchecked
        {
            // RyuJIT optimizes this to use the ROL instruction
            // Related GitHub pull request: dotnet/coreclr#1830
            uint rol5 = ((uint)h1 << 5) | ((uint)h1 >> 27);
            return ((int)rol5 + h1) ^ h2;
        }
    }

Auf Englisch:

  • Links drehen (Kreisverschiebung) h1 um 5 Positionen.
  • Addiere das Ergebnis und h1 zusammen.
  • XOR das Ergebnis mit h2.
  • Führen Sie zunächst die obige Operation für {static random seed, h1} aus.
  • Führen Sie für jedes weitere Element die Operation für das vorherige Ergebnis und das nächste Element aus (z. B. h2).

Es wäre schön, mehr über die Eigenschaften dieses ROL-5-Hashcode-Algorithmus zu erfahren.

Bedauerlicherweise Aufschieben auf ValueTuplefür unsere eigenen GetHashCodekann nicht so schnell, wie wir möchten und erwarten. Dieser Kommentar in einer verwandten Diskussion zeigt, dass das direkte Anrufen HashHelpers.Combineperformanter ist. Auf der anderen Seite ist dieser intern, also müssten wir den Code kopieren und viel von dem opfern, was wir hier gewonnen haben. Wir wären auch dafür verantwortlich, uns daran zu erinnern, zuerst Combineden zufälligen Samen zu verwenden. Ich weiß nicht, was die Konsequenzen sind, wenn wir diesen Schritt überspringen.

Timo
quelle
Angenommen, es h1 >> 27ist 0, um es zu ignorieren, ist h1 << 5gleich, h1 * 32also ist es dasselbe wie h1 * 33 ^ h2. Nach dieser Seite heißt es "Modified Bernstein".
Cactuaroid
3

Der Großteil meiner Arbeit wird mit Datenbankkonnektivität erledigt, was bedeutet, dass meine Klassen alle eine eindeutige Kennung aus der Datenbank haben. Ich verwende immer die ID aus der Datenbank, um den Hashcode zu generieren.

// Unique ID from database
private int _id;

...    
{
  return _id.GetHashCode();
}
Mark G.
quelle
Das heißt, wenn Sie Objekte Person und Konto haben und beide haben und ID = 1, haben sie den gleichen Hash-Code. Und das ist nicht in Ordnung.
Pero
15
Eigentlich ist der obige Kommentar falsch. Es besteht immer die Möglichkeit von Hash-Code-Kollisionen (ein Hash-Code lokalisiert nur den Bucket, nicht das einzelne Objekt). Eine solche Implementierung - für einen Hashcode, der gemischte Objekte enthält - würde zu vielen Kollisionen führen, was unerwünscht ist, aber es wäre absolut in Ordnung, wenn Sie nur Objekte eines einzigen Typs in Ihren Hashtabellen hätten. Es verteilt sich auch nicht gleichmäßig, aber auch nicht die Basisimplementierung auf system.object, sodass ich mir darüber keine Sorgen machen würde ...
piers7
2
Der Hash-Code kann nur die ID sein, da die ID eine Ganzzahl ist. Es ist nicht nötig, GetHashCode für eine Ganzzahl aufzurufen (es ist eine Identitätsfunktion)
Darrel Lee
2
@DarrelLee aber tomo seine _id könnte ein Guid sein. Es ist eine gute Codierungspraxis, _id.GetHashCodeda die Absicht klar ist.
Nawfal
2
@ 1224 Abhängig von den Verwendungsmustern kann es aus dem von Ihnen angegebenen Grund schrecklich sein, aber es kann auch großartig sein. Wenn Sie eine Folge solcher Zahlen ohne Löcher haben, haben Sie einen perfekten Hash, der besser ist als jeder Algorithmus. Wenn Sie wissen, dass dies der Fall ist, können Sie sich sogar darauf verlassen und die Gleichheitsprüfung überspringen.
Jon Hanna
3

Ziemlich ähnlich wie bei Nightcoder, nur dass es einfacher ist, Primzahlen zu erhöhen, wenn Sie möchten.

PS: Dies ist eine dieser Situationen, in denen Sie ein wenig in den Mund kotzen und wissen, dass dies mit 9 Standardeinstellungen in eine Methode umgewandelt werden könnte, die jedoch langsamer ist. Schließen Sie also einfach Ihre Augen und versuchen Sie, sie zu vergessen.

/// <summary>
/// Try not to look at the source code. It works. Just rely on it.
/// </summary>
public static class HashHelper
{
    private const int PrimeOne = 17;
    private const int PrimeTwo = 23;

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9, T10 arg10)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();
            hash = hash * PrimeTwo + arg9.GetHashCode();
            hash = hash * PrimeTwo + arg10.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();
            hash = hash * PrimeTwo + arg9.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, T4 arg4)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();

            return hash;
        }
    }
}
Dbl
quelle
2
Behandelt keine Nullen.
JJS
1

Ich bin auf ein Problem mit Gleitkommazahlen und Dezimalstellen gestoßen, bei dem die oben als Antwort ausgewählte Implementierung verwendet wurde.

Dieser Test schlägt fehl (Floats; Hash ist der gleiche, obwohl ich 2 Werte auf negativ geschaltet habe):

        var obj1 = new { A = 100m, B = 100m, C = 100m, D = 100m};
        var obj2 = new { A = 100m, B = 100m, C = -100m, D = -100m};
        var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
        var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
        Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different   hash1:{0}  hash2:{1}",hash1,hash2));

Aber dieser Test besteht (mit Ints):

        var obj1 = new { A = 100m, B = 100m, C = 100, D = 100};
        var obj2 = new { A = 100m, B = 100m, C = -100, D = -100};
        var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
        var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
        Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different   hash1:{0}  hash2:{1}",hash1,hash2));

Ich habe meine Implementierung dahingehend geändert, dass GetHashCode nicht für die primitiven Typen verwendet wird, und es scheint besser zu funktionieren

    private static int InternalComputeHash(params object[] obj)
    {
        unchecked
        {
            var result = (int)SEED_VALUE_PRIME;
            for (uint i = 0; i < obj.Length; i++)
            {
                var currval = result;
                var nextval = DetermineNextValue(obj[i]);
                result = (result * MULTIPLIER_VALUE_PRIME) + nextval;

            }
            return result;
        }
    }



    private static int DetermineNextValue(object value)
    {
        unchecked
        {

                int hashCode;
                if (value is short
                    || value is int
                    || value is byte
                    || value is sbyte
                    || value is uint
                    || value is ushort
                    || value is ulong
                    || value is long
                    || value is float
                    || value is double
                    || value is decimal)
                {
                    return Convert.ToInt32(value);
                }
                else
                {
                    return value != null ? value.GetHashCode() : 0;
                }
        }
    }
HokieMike
quelle
1
Im Fall sollte man sonst uncheckedkeinen Einfluss hat Convert.ToInt32: uint, long, float, doubleund decimalkann alle Überlauf hier.
Mark Hurd
1

Microsoft führt für verschiedene Arten von Hashing ...

//for classes that contain a single int value
return this.value;

//for classes that contain multiple int value
return x ^ y;

//for classes that contain single number bigger than int    
return ((int)value ^ (int)(value >> 32)); 

//for classes that contain class instance fields which inherit from object
return obj1.GetHashCode();

//for classes that contain multiple class instance fields which inherit from object
return obj1.GetHashCode() ^ obj2.GetHashCode() ^ obj3.GetHashCode(); 

Ich kann mir vorstellen, dass Sie für mehrere große Int Folgendes verwenden können:

int a=((int)value1 ^ (int)(value1 >> 32));
int b=((int)value2 ^ (int)(value2 >> 32));
int c=((int)value3 ^ (int)(value3 >> 32));
return a ^ b ^ c;

Und das Gleiche gilt für Multi-Type: Alle werden zuerst in intusing konvertiert, GetHashCode() dann werden die int-Werte xor'ed und das Ergebnis ist Ihr Hash.

Für diejenigen, die Hash als ID verwenden (ich meine einen eindeutigen Wert), ist Hash natürlich auf eine Anzahl von Ziffern beschränkt. Ich denke, es waren 5 Bytes für den Hashing-Algorithmus, mindestens MD5.

Sie können mehrere Werte in einen Hash-Wert umwandeln, von denen einige identisch sind. Verwenden Sie ihn daher nicht als Bezeichner. (Vielleicht werde ich eines Tages Ihre Komponente verwenden)

deadManN
quelle
7
Das Xoring von Ganzzahlen zur Erstellung eines Hashcodes ist ein bekanntes Antimuster, das zu einer besonders hohen Anzahl von Kollisionen mit realen Werten führt.
Jon Hanna
Jeder hier verwendet eine Ganzzahl, und es gab nie eine Garantie dafür, dass der Hash gleich ist. Es wurde nur versucht, so unterschiedlich zu sein, wie es nur wenige Kollisionen gibt.
deadManN
Ja, aber Ihre zweite und fünfte versuchen nicht, Kollisionen zu vermeiden.
Jon Hanna
1
Ja, dieses Antimuster ist ziemlich häufig.
Jon Hanna
2
Es ist ein Gleichgewicht zu erreichen. Wenn Sie einen wirklich guten Hash-Code wie Spookyhash verwenden, erhalten Sie eine viel bessere Kollisionsvermeidung, aber die Rechenzeit ist viel länger als bei allen anderen (aber wenn es darum geht, sehr große Datenmengen zu hashen, ist Spookyhash extrem schnell). Eine einfache Verschiebung eines der Werte vor dem Xoring ist nur ein geringfügiger Zusatzaufwand für eine gute Reduzierung der Kollision. Die Primzahlmultiplikation erhöht sowohl die Zeit als auch die Qualität erneut. Was zwischen Shift oder Mult besser ist, ist daher umstritten. Plain xor hat jedoch sehr oft viele Kollisionen mit realen Daten und wird am besten vermieden
Jon Hanna
1

Dies ist eine statische Hilfsklasse, die die Implementierung von Josh Bloch implementiert. und bietet explizite Überladungen, um das Boxen zu "verhindern" und den Hash speziell für die langen Grundelemente zu implementieren.

Sie können einen Zeichenfolgenvergleich übergeben, der Ihrer gleichwertigen Implementierung entspricht.

Da die Hash-Ausgabe immer ein int ist, können Sie einfach Hash-Aufrufe verketten.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using System.Runtime.CompilerServices;


namespace Sc.Util.System
{
    /// <summary>
    /// Static methods that allow easy implementation of hashCode. Example usage:
    /// <code>
    /// public override int GetHashCode()
    ///     => HashCodeHelper.Seed
    ///         .Hash(primitiveField)
    ///         .Hsh(objectField)
    ///         .Hash(iEnumerableField);
    /// </code>
    /// </summary>
    public static class HashCodeHelper
    {
        /// <summary>
        /// An initial value for a hashCode, to which is added contributions from fields.
        /// Using a non-zero value decreases collisions of hashCode values.
        /// </summary>
        public const int Seed = 23;

        private const int oddPrimeNumber = 37;


        /// <summary>
        /// Rotates the seed against a prime number.
        /// </summary>
        /// <param name="aSeed">The hash's first term.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int rotateFirstTerm(int aSeed)
        {
            unchecked {
                return HashCodeHelper.oddPrimeNumber * aSeed;
            }
        }


        /// <summary>
        /// Contributes a boolean to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aBoolean">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, bool aBoolean)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + (aBoolean
                                ? 1
                                : 0);
            }
        }

        /// <summary>
        /// Contributes a char to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aChar">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, char aChar)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + aChar;
            }
        }

        /// <summary>
        /// Contributes an int to the developing HashCode seed.
        /// Note that byte and short are handled by this method, through implicit conversion.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aInt">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, int aInt)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + aInt;
            }
        }

        /// <summary>
        /// Contributes a long to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aLong">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, long aLong)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + (int)(aLong ^ (aLong >> 32));
            }
        }

        /// <summary>
        /// Contributes a float to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aFloat">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, float aFloat)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + Convert.ToInt32(aFloat);
            }
        }

        /// <summary>
        /// Contributes a double to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aDouble">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, double aDouble)
            => aSeed.Hash(Convert.ToInt64(aDouble));

        /// <summary>
        /// Contributes a string to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aString">The value to contribute.</param>
        /// <param name="stringComparison">Optional comparison that creates the hash.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(
                this int aSeed,
                string aString,
                StringComparison stringComparison = StringComparison.Ordinal)
        {
            if (aString == null)
                return aSeed.Hash(0);
            switch (stringComparison) {
                case StringComparison.CurrentCulture :
                    return StringComparer.CurrentCulture.GetHashCode(aString);
                case StringComparison.CurrentCultureIgnoreCase :
                    return StringComparer.CurrentCultureIgnoreCase.GetHashCode(aString);
                case StringComparison.InvariantCulture :
                    return StringComparer.InvariantCulture.GetHashCode(aString);
                case StringComparison.InvariantCultureIgnoreCase :
                    return StringComparer.InvariantCultureIgnoreCase.GetHashCode(aString);
                case StringComparison.OrdinalIgnoreCase :
                    return StringComparer.OrdinalIgnoreCase.GetHashCode(aString);
                default :
                    return StringComparer.Ordinal.GetHashCode(aString);
            }
        }

        /// <summary>
        /// Contributes a possibly-null array to the developing HashCode seed.
        /// Each element may be a primitive, a reference, or a possibly-null array.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aArray">CAN be null.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, IEnumerable aArray)
        {
            if (aArray == null)
                return aSeed.Hash(0);
            int countPlusOne = 1; // So it differs from null
            foreach (object item in aArray) {
                ++countPlusOne;
                if (item is IEnumerable arrayItem) {
                    if (!object.ReferenceEquals(aArray, arrayItem))
                        aSeed = aSeed.Hash(arrayItem); // recursive call!
                } else
                    aSeed = aSeed.Hash(item);
            }
            return aSeed.Hash(countPlusOne);
        }

        /// <summary>
        /// Contributes a possibly-null array to the developing HashCode seed.
        /// You must provide the hash function for each element.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aArray">CAN be null.</param>
        /// <param name="hashElement">Required: yields the hash for each element
        /// in <paramref name="aArray"/>.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash<T>(this int aSeed, IEnumerable<T> aArray, Func<T, int> hashElement)
        {
            if (aArray == null)
                return aSeed.Hash(0);
            int countPlusOne = 1; // So it differs from null
            foreach (T item in aArray) {
                ++countPlusOne;
                aSeed = aSeed.Hash(hashElement(item));
            }
            return aSeed.Hash(countPlusOne);
        }

        /// <summary>
        /// Contributes a possibly-null object to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aObject">CAN be null.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, object aObject)
        {
            switch (aObject) {
                case null :
                    return aSeed.Hash(0);
                case bool b :
                    return aSeed.Hash(b);
                case char c :
                    return aSeed.Hash(c);
                case int i :
                    return aSeed.Hash(i);
                case long l :
                    return aSeed.Hash(l);
                case float f :
                    return aSeed.Hash(f);
                case double d :
                    return aSeed.Hash(d);
                case string s :
                    return aSeed.Hash(s);
                case IEnumerable iEnumerable :
                    return aSeed.Hash(iEnumerable);
            }
            return aSeed.Hash(aObject.GetHashCode());
        }


        /// <summary>
        /// This utility method uses reflection to iterate all specified properties that are readable
        /// on the given object, excluding any property names given in the params arguments, and
        /// generates a hashcode.
        /// </summary>
        /// <param name="aSeed">The developing hash code, or the seed: if you have no seed, use
        /// the <see cref="Seed"/>.</param>
        /// <param name="aObject">CAN be null.</param>
        /// <param name="propertySelector"><see cref="BindingFlags"/> to select the properties to hash.</param>
        /// <param name="ignorePropertyNames">Optional.</param>
        /// <returns>A hash from the properties contributed to <c>aSeed</c>.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashAllProperties(
                this int aSeed,
                object aObject,
                BindingFlags propertySelector
                        = BindingFlags.Instance
                        | BindingFlags.Public
                        | BindingFlags.GetProperty,
                params string[] ignorePropertyNames)
        {
            if (aObject == null)
                return aSeed.Hash(0);
            if ((ignorePropertyNames != null)
                    && (ignorePropertyNames.Length != 0)) {
                foreach (PropertyInfo propertyInfo in aObject.GetType()
                        .GetProperties(propertySelector)) {
                    if (!propertyInfo.CanRead
                            || (Array.IndexOf(ignorePropertyNames, propertyInfo.Name) >= 0))
                        continue;
                    aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
                }
            } else {
                foreach (PropertyInfo propertyInfo in aObject.GetType()
                        .GetProperties(propertySelector)) {
                    if (propertyInfo.CanRead)
                        aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
                }
            }
            return aSeed;
        }


        /// <summary>
        /// NOTICE: this method is provided to contribute a <see cref="KeyValuePair{TKey,TValue}"/> to
        /// the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
        /// this method has a different name since it will not be automatically invoked by
        /// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
        /// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
        /// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
        /// the generated hash code will not be consistent. This method itself ALSO will not invoke
        /// this method on the Key or Value here if that itself is a KeyValuePair.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="keyValuePair">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashKeyAndValue<TKey, TValue>(this int aSeed, KeyValuePair<TKey, TValue> keyValuePair)
            => aSeed.Hash(keyValuePair.Key)
                    .Hash(keyValuePair.Value);

        /// <summary>
        /// NOTICE: this method is provided to contribute a collection of <see cref="KeyValuePair{TKey,TValue}"/>
        /// to the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
        /// this method has a different name since it will not be automatically invoked by
        /// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
        /// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
        /// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
        /// the generated hash code will not be consistent. This method itself ALSO will not invoke
        /// this method on a Key or Value here if that itself is a KeyValuePair or an Enumerable of
        /// KeyValuePair.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="keyValuePairs">The values to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashKeysAndValues<TKey, TValue>(
                this int aSeed,
                IEnumerable<KeyValuePair<TKey, TValue>> keyValuePairs)
        {
            if (keyValuePairs == null)
                return aSeed.Hash(null);
            foreach (KeyValuePair<TKey, TValue> keyValuePair in keyValuePairs) {
                aSeed = aSeed.HashKeyAndValue(keyValuePair);
            }
            return aSeed;
        }
    }
}
Steven Coco
quelle
Yipes: Ich habe einen Fehler gefunden! Die HashKeysAndValuesMethode wurde behoben: Sie wird aufgerufen HashKeyAndValue.
Steven Coco
0

Für den Fall, dass Sie HashCodeaus füllen möchtennetstandard2.1

public static class HashCode
{
    public static int Combine(params object[] instances)
    {
        int hash = 17;

        foreach (var i in instances)
        {
            hash = unchecked((hash * 31) + (i?.GetHashCode() ?? 0));
        }

        return hash;
    }
}

Hinweis: Bei Verwendung mit structwird aufgrund des Boxens Speicher zugewiesen

Ivan Sanz-Carasa
quelle