c# - Getting Hash einer Liste von Zeichenfolgen unabhängig von der Reihenfolge




c# hash sha256 (2)

Eine Alternative zum Sortieren der String-Listen wäre es, die Hash-Codes der Strings zu erhalten und dann die Hash-Codes zu sortieren. (Das Vergleichen von Ints ist weniger kostenintensiv als der Vergleich von Strings.) Sie können dann einen Algorithmus verwenden, um die Hash-Codes zusammenzuführen, die (hoffentlich) eine bessere Verteilung ergeben.

Beispiel:

GetHashCodeOfList<T>(IEnumerable<T> list) {
   List<int> codes = new List<int>();
   foreach (T item in list) {
      codes.Add(item.GetHashCode());
   }
   codes.Sort();
   int hash = 0;
   foreach (int code in codes) {
      unchecked {
         hash *= 251; // multiply by a prime number
         hash += code; // add next hash code
      }
   }
   return hash;
}

https://code.i-harness.com

Ich möchte eine Funktion schreiben GetHashCodeOfList() die einen Hash-Code einer Liste von Strings unabhängig von der Reihenfolge zurückgibt. Gegeben 2 Listen mit den gleichen Strings sollte den gleichen Hash-Code zurückgeben.

ArrayList list1 = new ArrayList()    
list1.Add("String1");
list1.Add("String2");
list1.Add("String3");    

ArrayList list2 = new ArrayList()    
list2.Add("String3");    
list2.Add("String2"); 
list2.Add("String1");

GetHashCodeOfList(list1) = GetHashCodeOfList(list2) //this should be equal.

Ich hatte ein paar Gedanken:

  1. Ich kann zuerst die Liste sortieren, dann die sortierte Liste in eine lange Zeichenfolge kombinieren und dann GetHashCode() aufrufen. Das Sortieren ist jedoch ein langsamer Vorgang.

  2. Ich kann den Hash jeder einzelnen Zeichenfolge (durch Aufrufen von string.GetHashCode() ) in der Liste string.GetHashCode() , dann alle Hashes multiplizieren und Mod UInt32.MaxValue . Zum Beispiel: "String1".GetHashCode() * "String2".GetHashCode * … MOD UInt32.MaxValue . Dies führt jedoch zu einem Überlauf von Zahlen.

Hat jemand irgendwelche Gedanken?

Vielen Dank im Voraus für Ihre Hilfe.


Es gibt verschiedene Ansätze, die in zwei Hauptkategorien unterteilt sind, von denen jede ihre eigenen Vor- und Nachteile in Bezug auf Effektivität und Leistung aufweist. Es ist wahrscheinlich am besten, den einfachsten Algorithmus für jede Anwendung auszuwählen und nur die komplexeren Varianten zu verwenden, wenn dies für irgendeine Situation erforderlich ist.

Beachten Sie, dass diese Beispiele EqualityComparer<T>.Default da dies sauber mit EqualityComparer<T>.Default umgehen wird. Sie könnten besser als null für null tun, wenn Sie es wünschen. Wenn T auf Struktur beschränkt ist, ist es auch nicht notwendig. Sie können den EqualityComparer<T>.Default Lookup aus der Funktion EqualityComparer<T>.Default , wenn dies gewünscht wird.

Kommutative Operationen

Wenn Sie Operationen auf den Hashcodes der einzelnen Einträge verwenden, die commutative dies unabhängig von der Reihenfolge zum selben Endergebnis.

Es gibt mehrere offensichtliche Optionen für Zahlen:

XOR

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    foreach (T element in source)
    {
        hash = hash ^ EqualityComparer<T>.Default.GetHashCode(element);
    }
    return hash;
}

Ein Nachteil davon ist, dass der Hash für {"x", "x"} derselbe wie der Hash für {"y", "y"} ist. Wenn das für Ihre Situation kein Problem ist, ist es wahrscheinlich die einfachste Lösung.

Zusatz

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    foreach (T element in source)
    {
        hash = unchecked (hash + 
            EqualityComparer<T>.Default.GetHashCode(element));
    }
    return hash;
}

Überlauf ist hier in Ordnung, daher der explizite unchecked Kontext.

Es gibt immer noch einige unangenehme Fälle (zB {1, -1} und {2, -2}, aber es ist wahrscheinlicher, dass sie in Ordnung sind, besonders bei Strings. Im Fall von Listen, die solche ganzen Zahlen enthalten könnten, könnten Sie immer a implementieren benutzerdefinierte Hashing-Funktion (möglicherweise eine, die den Index der Wiederholung des spezifischen Werts als Parameter verwendet und einen eindeutigen Hash-Code entsprechend zurückgibt).

Hier ist ein Beispiel für einen solchen Algorithmus, der das oben erwähnte Problem auf ziemlich effiziente Weise umgeht. Es hat auch den Vorteil, die Verteilung der erzeugten Hash-Codes stark zu erhöhen (siehe den Artikel, der am Ende für einige Erklärungen verlinkt ist). Eine mathematisch / statistische Analyse, wie genau dieser Algorithmus "bessere" Hash-Codes erzeugt, wäre ziemlich weit fortgeschritten. Aber wenn er über einen großen Bereich von Eingabewerten getestet und die Ergebnisse grafisch dargestellt werden, sollte dies gut genug überprüft werden.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    int curHash;
    int bitOffset = 0;
    // Stores number of occurences so far of each value.
    var valueCounts = new Dictionary<T, int>();

    foreach (T element in source)
    {
        curHash = EqualityComparer<T>.Default.GetHashCode(element);
        if (valueCounts.TryGetValue(element, out bitOffset))
            valueCounts[element] = bitOffset + 1;
        else
            valueCounts.Add(element, bitOffset);

        // The current hash code is shifted (with wrapping) one bit
        // further left on each successive recurrence of a certain
        // value to widen the distribution.
        // 37 is an arbitrary low prime number that helps the
        // algorithm to smooth out the distribution.
        hash = unchecked(hash + ((curHash << bitOffset) |
            (curHash >> (32 - bitOffset))) * 37);
    }

    return hash;
}

Multiplikation

Das hat wenige Vorteile gegenüber der Addition: kleine Zahlen und eine Mischung aus positiven und negativen Zahlen können zu einer besseren Verteilung der Hash-Bits führen. Als ein Negativ, um diese "1" auszugleichen, wird ein nutzloser Eintrag, der nichts beiträgt, und irgendein Nullelement führt zu einer Null. Sie können Sonderfall Null diesen großen Fehler nicht verursachen.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 17;
    foreach (T element in source)
    {
        int h = EqualityComparer<T>.Default.GetHashCode(element);
        if (h != 0)
            hash = unchecked (hash * h);
    }
    return hash;
}

Bestellung zuerst

Der andere Kernansatz besteht darin, zuerst eine Reihenfolge zu erzwingen und dann eine beliebige Hash-Kombinationsfunktion zu verwenden. Die Reihenfolge selbst ist unerheblich, solange sie konsistent ist.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    foreach (T element in source.OrderBy(x => x, Comparer<T>.Default))
    {
        // f is any function/code you like returning int
        hash = f(hash, element);
    }
    return hash;
}

Dies hat einige wesentliche Vorteile dahingehend, dass die Kombinationsoperationen, die in f möglich sind, wesentlich bessere Hashing-Eigenschaften haben können (z. B. die Verteilung von Bits), dies jedoch zu signifikant höheren Kosten führt. Die Sortierung ist O(n log n) und die erforderliche Kopie der Sammlung ist eine Speicherzuordnung, die Sie nicht vermeiden können, wenn Sie das Original nicht verändern möchten. GetHashCode Implementierungen sollten normalerweise Allokationen vollständig vermeiden. Eine mögliche Implementierung von f wäre ähnlich zu der im letzten Beispiel unter dem Abschnitt Addition (z. B. jede konstante Anzahl von Bitverschiebungen links gefolgt von einer Multiplikation mit einer Primzahl - Sie könnten sogar aufeinanderfolgende Primzahlen bei jeder Iteration ohne zusätzliche Kosten verwenden, da sie nur einmal generiert werden müssen).

Wenn Sie jedoch mit Fällen arbeiten, in denen Sie den Hash berechnen und zwischenspeichern und die Kosten über viele Aufrufe von GetHashCode amortisieren können, GetHashCode dieser Ansatz zu einem GetHashCode Verhalten führen. Auch der letztere Ansatz ist noch flexibler, da es die Notwendigkeit vermeidet, den GetHashCode für die Elemente zu verwenden, wenn er ihren Typ kennt und stattdessen pro Byte Operationen für eine noch bessere Hashverteilung verwendet. Ein solcher Ansatz würde wahrscheinlich nur in Fällen nützlich sein, in denen die Leistung als erheblicher Engpass identifiziert wurde.

Schließlich, wenn Sie eine einigermaßen umfassende und ziemlich nicht-mathematische Übersicht über das Thema der Hash-Codes und ihre Wirksamkeit im Allgemeinen wollen, würden diese Blog-Beiträge lohnen, insbesondere die Implementierung eines einfachen Hashing-Algorithmus (Pt II) Post.





hash