Schnelle und einfache Hash-Code-Kombinationen

Können Leute schnelle und einfache Möglichkeiten empfehlen, um die Hash-Codes zweier Objekte zu kombinieren? Ich mache mir keine allzu großen Sorgen um Kollisionen, da ich eine Hash-Tabelle habe, die so effizient funktioniert. Ich möchte nur etwas, das so schnell wie möglich einen Code generiert.

Beim Lesen in SO und im Internet scheint es einige Hauptkandidaten zu geben:

1. XORing
2. XORing mit Prime Multiplication
3. Einfache numerische Operationen wie Multiplikation / Division (mit Überlaufprüfung oder Umwickeln)
4. Erstellen eines Strings und anschließende Verwendung der Hash-Code-Methode der String-Klassen

Was würden die Leute empfehlen und warum?

Ich persönlich würde XOR vermeiden - es bedeutet, dass zwei gleiche Werte zu 0 führen - also Hash (1, 1) == Hash (2, 2) == Hash (3, 3) usw. Auch Hash (5, 0) == Hash (0, 5) usw., der gelegentlich auftreten kann. Ich habe es absichtlich für das Set-Hashing verwendet. Wenn Sie eine Folge von Elementen hashen möchten und sich nicht um die Bestellung kümmern, ist es schön.

Ich benutze normalerweise:

unchecked
{
    int hash = 17;
    hash = hash * 31 + firstField.GetHashCode();
    hash = hash * 31 + secondField.GetHashCode();
    return hash;
}

Das ist die Form, die Josh Bloch in Effective Java vorschlägt. Als ich das letzte Mal eine ähnliche Frage beantwortete, fand ich einen Artikel, in dem dies ausführlich besprochen wurde - IIRC, niemand weiß wirklich, warum es gut funktioniert, aber es funktioniert. Es ist auch leicht zu merken, leicht zu implementieren und auf eine beliebige Anzahl von Feldern zu erweitern.

Während die in Jon Skeets Antwort beschriebene Vorlage im Allgemeinen als Hash-Funktionsfamilie gut funktioniert, ist die Auswahl der Konstanten wichtig, und der Keim 17und der Faktor von, 31wie in der Antwort angegeben, funktionieren für allgemeine Anwendungsfälle überhaupt nicht gut. In den meisten Anwendungsfällen liegen die Hash-Werte viel näher bei Null als int.MaxValueund die Anzahl der gemeinsam gehashten Elemente beträgt einige Dutzend oder weniger.

Für das Hashing eines ganzzahligen Tupels {x, y}mit -1000 <= x <= 1000und -1000 <= y <= 1000hat es eine abgrundtiefe Kollisionsrate von fast 98,5%. Zum Beispiel {1, 0} -> {0, 31}, {1, 1} -> {0, 32}usw. Wenn wir die Abdeckung erweitern , um auch n-Tupel umfasst , wo 3 <= n <= 25, tut es weniger schrecklich mit einer Kollisionsgeschwindigkeit von etwa 38%. Aber wir können es viel besser machen.

public static int CustomHash(int seed, int factor, params int[] vals)
{
    int hash = seed;
    foreach (int i in vals)
    {
        hash = (hash * factor) + i;
    }
    return hash;
}

Ich habe eine Monte-Carlo-Stichproben-Suchschleife geschrieben, die die obige Methode mit verschiedenen Werten für Startwert und Faktor über verschiedene zufällige n-Tupel zufälliger Ganzzahlen getestet hat i. Zulässige Bereiche waren 2 <= n <= 25(wo nzufällig, aber zum unteren Ende des Bereichs hin voreingenommen) und -1000 <= i <= 1000. Für jedes Samen- und Faktorpaar wurden mindestens 12 Millionen einzigartige Kollisionstests durchgeführt.

Nach ca. 7 Stunden Laufzeit , das beste Paar gefunden (wo der Samen und Faktor sowohl auf 4 Stellen begrenzt waren oder weniger) war: seed = 1009, factor = 9176, mit einer Kollisionsgeschwindigkeit von 0,1131%. In den 5- und 6-stelligen Bereichen gibt es noch bessere Optionen. Aber ich habe der Kürze halber den besten 4-stelligen Darsteller ausgewählt, und er zeigt sich in allen gängigen intund charHashing-Szenarien recht gut . Es scheint auch gut mit ganzen Zahlen von viel größeren Größen zu funktionieren.

Es ist erwähnenswert, dass "Prime sein" keine allgemeine Voraussetzung für eine gute Leistung als Keim und / oder Faktor zu sein schien, obwohl dies wahrscheinlich hilfreich ist. 1009oben erwähnt ist in der Tat Prime, ist es aber 9176nicht. Ich habe explizit Variationen davon getestet, bei denen ich factorzu verschiedenen Primzahlen in der Nähe 9176(während des Verlassens seed = 1009) gewechselt habe und alle schlechter abschnitten als die obige Lösung.

Zuletzt habe ich auch mit der generischen ReSharper-Empfehlungsfunktionsfamilie von verglichen hash = (hash * factor) ^ i;und das Original, CustomHash()wie oben erwähnt, übertrifft es ernsthaft. Der ReSharper XOR-Stil scheint Kollisionsraten im Bereich von 20 bis 30% für allgemeine Anwendungsfallannahmen zu haben und sollte meiner Meinung nach nicht verwendet werden.

Wenn Sie .NET Core 2.1 oder höher oder .NET Framework 4.6.1 oder höher verwenden, sollten Sie die System.HashCode- Struktur verwenden, um zusammengesetzte Hash-Codes zu erstellen . Es gibt zwei Betriebsarten: Hinzufügen und Kombinieren.

Ein Beispiel mit Combine, das normalerweise einfacher ist und für bis zu acht Elemente funktioniert:

public override int GetHashCode()
{
    return HashCode.Combine(object1, object2);
}

Ein Beispiel für die Verwendung von Add:

public override int GetHashCode()
{
    var hash = new HashCode();
    hash.Add(this.object1);
    hash.Add(this.object2);
    return hash.ToHashCode();
}

Vorteile:

• Teil von .NET selbst, ab .NET Core 2.1 / .NET Standard 2.1 (siehe siehe unten)
  • Für .NET Framework 4.6.1 und höher kann das Microsoft.Bcl.HashCode NuGet-Paket verwendet werden, um diesen Typ zurück zu portieren.
• Es scheint gute Performance- und Mischeigenschaften zu haben, basierend auf der Arbeit des Autors und der Rezensenten, bevor diese in das corefx-Repo integriert wurden
• Behandelt Nullen automatisch
• Überladungen, die IEqualityComparerInstanzen benötigen

Nachteile:

• In .NET Framework vor .NET 4.6.1 nicht verfügbar. HashCodeist Teil von .NET Standard 2.1. Ab September 2019 hat das .NET-Team keine Pläne, .NET Standard 2.1 unter .NET Framework zu unterstützen , da .NET Core / .NET 5 die Zukunft von .NET ist .
• Allzweck, daher werden keine superspezifischen Fälle sowie handgefertigter Code behandelt

Verwenden Sie die Kombinationslogik in Tupel. Das Beispiel verwendet c # 7-Tupel.

(field1, field2).GetHashCode();

Ich gehe davon aus, dass das .NET Framework-Team beim Testen der Implementierung von System.String.GetHashCode () gute Arbeit geleistet hat, also würde ich es verwenden:

// System.String.GetHashCode(): http://referencesource.microsoft.com/#mscorlib/system/string.cs,0a17bbac4851d0d4
// System.Web.Util.StringUtil.GetStringHashCode(System.String): http://referencesource.microsoft.com/#System.Web/Util/StringUtil.cs,c97063570b4e791a
public static int CombineHashCodes(IEnumerable<int> hashCodes)
{
    int hash1 = (5381 << 16) + 5381;
    int hash2 = hash1;

    int i = 0;
    foreach (var hashCode in hashCodes)
    {
        if (i % 2 == 0)
            hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ hashCode;
        else
            hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ hashCode;

        ++i;
    }

    return hash1 + (hash2 * 1566083941);
}

Eine weitere Implementierung stammt aus den Methoden System.Web.Util.HashCodeCombiner.CombineHashCodes (System.Int32, System.Int32) und System.Array.CombineHashCodes (System.Int32, System.Int32) . Dieser ist einfacher, hat aber wahrscheinlich keine so gute Verteilung wie die obige Methode:

// System.Web.Util.HashCodeCombiner.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#System.Web/Util/HashCodeCombiner.cs,21fb74ad8bb43f6b
// System.Array.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#mscorlib/system/array.cs,87d117c8cc772cca
public static int CombineHashCodes(IEnumerable<int> hashCodes)
{
    int hash = 5381;

    foreach (var hashCode in hashCodes)
        hash = ((hash << 5) + hash) ^ hashCode;

    return hash;
}

Dies ist ein Umpacken der brillant recherchierten Lösung von Special Sauce .
Es verwendet Value Tuples ( ITuple).
Dies ermöglicht Standardeinstellungen für die Parameter seedund factor.

public static int CombineHashes(this ITuple tupled, int seed=1009, int factor=9176)
{
    var hash = seed;

    for (var i = 0; i < tupled.Length; i++)
    {
        unchecked
        {
            hash = hash * factor + tupled[i].GetHashCode();
        }
    }

    return hash;
}

Verwendung:

var hash1 = ("Foo", "Bar", 42).CombineHashes();    
var hash2 = ("Jon", "Skeet", "Constants").CombineHashes(seed=17, factor=31);

Wenn Ihre Eingabe-Hashes dieselbe Größe haben, gleichmäßig verteilt sind und nicht miteinander in Beziehung stehen, sollte ein XOR in Ordnung sein. Außerdem ist es schnell.

Die Situation, für die ich dies vorschlage, ist die, in der Sie dies tun möchten

H = hash(A) ^ hash(B); // A and B are different types, so there's no way A == B.

Wenn erwartet werden kann, dass A und B mit einer angemessenen (nicht zu vernachlässigenden) Wahrscheinlichkeit auf denselben Wert hashen, sollten Sie XOR natürlich nicht auf diese Weise verwenden.

Wenn Sie Geschwindigkeit suchen und nicht zu viele Kollisionen haben, ist XOR am schnellsten. Um ein Clustering um Null zu verhindern, können Sie Folgendes tun:

finalHash = hash1 ^ hash2;
return finalHash != 0 ? finalHash : hash1;

Natürlich sollten einige Prototypen Ihnen eine Vorstellung von Leistung und Clustering geben.

Angenommen, Sie haben eine relevante toString () -Funktion (in der Ihre verschiedenen Felder angezeigt werden sollen), würde ich nur den Hashcode zurückgeben:

this.toString().hashCode();

Dies ist nicht sehr schnell, sollte aber Kollisionen recht gut vermeiden.

Ich würde empfehlen, die in System.Security.Cryptography integrierten Hash-Funktionen zu verwenden, anstatt Ihre eigenen zu rollen.