Ist es möglich, eine gut verteilte Hash-Tabelle ohne Verwendung des Operators% zu implementieren?

11

Ich möchte eine schnelle, gut verteilte Hash-Tabelle in C # implementieren. Ich habe Probleme bei der Auswahl meiner Hash-Einschränkungsfunktion, die einen beliebigen Hash-Code verwendet und ihn "einschränkt", damit er zum Indizieren der Buckets verwendet werden kann. Bisher sehe ich zwei Möglichkeiten:

  • Einerseits können Sie sicherstellen, dass Ihre Buckets immer eine Primzahl von Elementen haben, und um den Hash einzuschränken, modulieren Sie ihn einfach durch die Anzahl der Buckets. Dies ist in der Tat das, was das .NET-Wörterbuch tut . Das Problem bei diesem Ansatz ist, dass die Verwendung von% im Vergleich zu anderen Vorgängen extrem langsam ist. Wenn Sie sich die Agner Fog-Befehlstabellen ansehen idiv(dies ist der Assembly-Code, der für% generiert wird) , beträgt die Befehlslatenz für neuere Intel-Prozessoren ~ 25 Zyklen. Vergleichen Sie dies mit rund 3 für muloder 1 für bitweise ops wie and, oroder xor.

  • Auf der anderen Seite kann die Anzahl der Buckets immer eine Potenz von 2 sein. Sie müssen immer noch den Modul des Hash berechnen, damit Sie nicht versuchen, außerhalb des Arrays zu indizieren, aber diesmal ist es weniger teuer . Da für Potenzen von 2 % Ngerade ist & (N - 1), wird die Beschränkung auf eine Maskierungsoperation reduziert, die nur 1-2 Zyklen dauert. Dies geschieht durch Googles Sparsehash . Der Nachteil dabei ist, dass wir uns darauf verlassen, dass Benutzer gute Hashes bereitstellen. Durch das Maskieren des Hashs wird im Wesentlichen ein Teil des Hashs abgeschnitten, sodass nicht mehr alle Teile des Hashs berücksichtigt werden. Wenn der Hash des Benutzers ungleichmäßig verteilt ist, zum Beispiel nur die höheren Bits ausgefüllt werden oder die niedrigeren Bits konsistent gleich sind, hat dieser Ansatz eine viel höhere Kollisionsrate.

Ich suche nach einem Algorithmus, der das Beste aus beiden Welten bietet: Er berücksichtigt alle Teile des Hashs und ist außerdem schneller als die Verwendung von%. Es muss nicht unbedingt ein Modul sein, sondern etwas, das garantiert im Bereich liegt 0..N-1(wobei N die Länge der Schaufeln ist) und für alle Schlitze gleichmäßig verteilt ist. Gibt es einen solchen Algorithmus?

Danke fürs Helfen.

c# algorithms language-agnostic hashing James Ko
quelle
1
Schlagen Sie den Lawineneffekt sowie die Erklärung in murmurhash3 (smhasher) nach . Der grundlegende Punkt in Ihrer Frage wird jedoch nicht durch die Übernahme einer besseren Hash-Funktion angesprochen. Stattdessen geht es darum, warum Benutzer überhaupt nicht dieselbe bessere Hash-Funktion anwenden, und um Aufforderung zur Gegenmaßnahme (als ob Benutzer böswillig faul wären).
Rwong
Eine grafische Erklärung und Demonstration der Lawine
rwong
Für schnelles Modulo (2^N +/- 1)siehe stackoverflow.com/questions/763137/…
rwong
@rwong Es tut mir leid, aber ich bin mir nicht ganz sicher, was dein Kommentar mit meinem Beitrag zu tun hat. Ich kontrolliere den vom Benutzer bereitgestellten Hash nicht, daher suche ich nicht nach einer besseren Hash-Funktion. Ich verstehe auch nicht, was Sie unter "böswillig faulen Benutzern" verstehen.
James Ko
4
Wenn die Hash-Funktion schlecht ist, kann der Hash-Tabellen-Implementierer nichts tun, um die schlechte Verteilung zu "beheben". Modulo eine Primzahl repariert keinen schlechten Hash. Stellen Sie sich eine Hash-Funktion vor, die als Ausgabe Vielfache einer Primzahl erzeugt. Ich habe ein solches Problem im realen Produktionscode gesehen.
Frank Hileman

Antworten:

9

Moderne Hash-Tabellen-Implementierungen verwenden die Modulo-Funktion nicht. Sie verbrauchen oft die Leistung von Tischen mit zwei Größen und hacken nicht benötigte Teile ab. Eine ideale Hash-Funktion würde dies ermöglichen. Die Verwendung von Modulo in Kombination mit Primzahl-Tabellengrößen trat in den Tagen auf, als die Hash-Funktionen im Allgemeinen schlecht waren, wie sie häufig in der .net-Entwicklung sind. Ich empfehle, über SipHash , eine moderne Hash-Funktion, zu lesen und dann über einige andere moderne Funktionen wie xxHash zu lesen .

Ich sollte erklären, warum .net-Hash-Funktionen oft schlecht sind. In .net sind Programmierer häufig gezwungen, Hash-Funktionen zu implementieren, indem sie GetHashcode überschreiben. .Net bietet jedoch nicht die Tools, die erforderlich sind, um sicherzustellen, dass die vom Programmierer erstellten Funktionen von hoher Qualität sind, nämlich:

  • Kapselung des Hash-Zustands in einer Struktur oder Klasse
  • Hash "Add" -Funktionen, die dem Hash-Status neue Daten hinzufügen (z. B. ein Byte-Array oder ein Double hinzufügen)
  • eine Hash "finalize" Funktion, um die Lawine zu erzeugen
  • Kapselung des Hash-Ergebnisses - in .net haben Sie eine Wahl, eine 32-Bit-Ganzzahl mit Vorzeichen.

Weitere Informationen zur Verwendung eines Hash-Funktionsergebnisses als Hash-Tabellenindex finden Sie in den Definitionen der universellen Formen des Hashings in diesem Dokument: Schnelleres 64-Bit-Universal-Hashing unter Verwendung von Multiplikationen ohne Übertrag

Frank Hileman
quelle
3

Verwenden Sie auch XOR, um AND zu verwenden, während alle Bits erhalten bleiben.

Zum Beispiel temp = (hash & 0xFFFF) ^ ( hash >> 16); index = (temp & 0xFF) ^ (temp >> 8);.

In diesem Beispiel gibt es kein Modulo und alle 32 Bit des hash8-Bit-Effekts index. Ob es jedoch schneller als DIV ist oder nicht, hängt von zu vielen Faktoren ab und kann in einigen Fällen leicht langsamer als DIV sein (z. B. großer Hash und kleiner Index).

Brendan
quelle
Dies wird immer schneller sein als DIV / IDIV, aber ich glaube nicht, dass es meine Frage beantwortet - indexwird im Bereich liegen [0..255]. Ich brauche etwas im Bereich [0..n-1], wo nist die Anzahl der Eimer.
James Ko
@JamesKo Wenn Sie jedoch ein Wörterbuch implementieren, steuern Sie auch die Anzahl der Buckets (bis zu einem gewissen Grad). Anstelle von Primzahlen können Sie also Zweierpotenzen wählen. (Ob dies tatsächlich eine gute Idee wäre, kann ich Ihnen nicht sagen.)
Svick
@svick Für Potenzen von 2 könnten wir eine einfache Maskenoperation durchführen. Wie in der Frage erwähnt, suche ich nach einem billigen Weg, dies mit Primzahlen zu tun, damit auch schlecht verteilte Hashes berücksichtigt werden.
James Ko
1

Sie können die Tatsache nutzen, dass viele Primzahlen eine modulare multiplikative Inverse haben. Siehe diesen Artikel . Sie haben eine der Einschränkungen erfüllt, indem Sie Ihren Bucket-Index zu einer Primzahl und dem Modul 2 ^ n gemacht haben, die von Natur aus relativ prim sind.

Der Artikel beschreibt den Algorithmus zum Finden einer Zahl, sodass das Multiplizieren mit dieser Zahl und das Ignorieren des Überlaufs das gleiche Ergebnis liefert, als hätten Sie durch die Bucket-Indexgröße geteilt.

BobDalgleish
quelle