Warum sollten Hash-functionen einen Primzahl-Modulus verwenden?

Vor langer Zeit kaufte ich ein Buch mit Datenstrukturen für 1,25 Dollar aus dem Handel. Die Erklärung für eine Hashing-function besagt, dass sie schließlich wegen der “Natur der Mathematik” um eine Primzahl modieren sollte.

Was erwarten Sie von einem 1,25 $ Buch?

Wie auch immer, ich hatte Jahre Zeit, über die Natur der Mathematik nachzudenken, und kann es immer noch nicht herausfinden.

Ist die Verteilung der Zahlen wirklich gleichmäßiger, wenn es eine Primzahl von Buckets gibt? Oder ist das die Geschichte eines alten Programmierers, die jeder akzeptiert, weil alle anderen es akzeptieren?

Gewöhnlich arbeitet eine einfache Hash-function, indem sie die “Bestandteile” der Eingabe (Zeichen im Fall einer Zeichenkette) nimmt und sie mit den Potenzen einer Konstanten multipliziert und sie zu einem ganzzahligen Typ addiert. So könnte zum Beispiel ein typischer (wenn auch nicht besonders guter) Hash einer Zeichenkette lauten:

(first char) + k * (second char) + k^2 * (third char) + ... 

Wenn dann ein Bündel von Strings mit dem gleichen ersten Zeichen eingespeist wird, dann sind die Ergebnisse alle gleich modulo k, zumindest bis der Integer-Typ überläuft.

[Als Beispiel ähnelt der String hashCode von Java dem unheimlich – er kehrt die Reihenfolge der Zeichen um, mit k = 31. So erhalten Sie markante Beziehungen modulo 31 zwischen Strings, die auf die gleiche Weise enden, und markante Beziehungen modulo 2 ^ 32 zwischen Strings, die die gleichen sind, außer nahe dem Ende. Dies beeinträchtigt das Verhalten der Hashtabellen nicht ernsthaft.]

Eine Hashtabelle arbeitet, indem sie den Modul des Hashwerts über die Anzahl der Buckets nimmt.

In einer Hashtabelle ist es wichtig, keine Kollisionen für wahrscheinliche Fälle zu erzeugen, da Kollisionen die Effizienz der Hashtabelle reduzieren.

Nehmen wir nun an, dass jemand eine ganze Reihe von Werten in eine Hashtabelle einfügt, die eine Beziehung zwischen den Elementen haben, so wie alle dasselbe erste Zeichen haben. Dies ist ein ziemlich vorhersehbares Nutzungsmuster, würde ich sagen, also wollen wir nicht, dass es zu viele Kollisionen produziert.

Es stellt sich heraus, dass “aufgrund der Natur der Mathematik”, wenn die im Hash verwendete Konstante und die Anzahl der Buckets Co-Rime sind , Kollisionen in einigen häufigen Fällen minimiert werden. Wenn sie nicht gleichzeitig sind, gibt es einige ziemlich einfache Beziehungen zwischen Eingängen, für die Kollisionen nicht minimiert werden. Alle Hashes kommen gleich modulo dem gemeinsamen Faktor, was bedeutet, dass sie alle in den 1 / n-ten der Buckets fallen, die diesen Wert modulo den gemeinsamen Faktor haben. Sie erhalten n-mal so viele Kollisionen, wobei n der gemeinsame Faktor ist. Da n mindestens 2 ist, würde ich sagen, dass es für einen ziemlich einfachen Anwendungsfall inakzeptabel ist, mindestens doppelt so viele Kollisionen wie normal zu erzeugen. Wenn ein Benutzer unsere Distribution in Buckets aufteilt, wollen wir, dass es sich um einen ungewöhnlichen Unfall handelt, nicht um eine einfach vorhersehbare Nutzung.

Hashtable-Implementierungen haben offensichtlich keine Kontrolle über die darin enthaltenen Elemente. Sie können nicht verhindern, dass sie verwandt sind. Es muss also sichergestellt werden, dass die Konstante und die Anzahl der Buckets cofrime sind. Auf diese Weise verlassen Sie sich nicht nur auf die “letzte” Komponente, um den Modul des Buckets in Bezug auf einen kleinen gemeinsamen Faktor zu bestimmen. Soweit ich weiß, müssen sie nicht unbedingt die Besten sein, um das zu erreichen, nur Koprime.

Wenn jedoch die Hash-function und die Hashtabelle unabhängig voneinander geschrieben werden, weiß die Hashtabelle nicht, wie die Hash-function funktioniert. Es könnte eine Konstante mit kleinen Faktoren verwenden. Wenn Sie Glück haben, kann es ganz anders funktionieren und nicht linear sein. Wenn der Hash gut genug ist, dann ist jede Bucket-Anzahl in Ordnung. Eine paranoide Hashtabelle kann jedoch keine gute Hash-function annehmen, sollte also eine Primzahl von Buckets verwenden. In ähnlicher Weise sollte eine paranoide Hash-function eine größere Primzahlkonstante verwenden, um die Wahrscheinlichkeit zu verringern, dass jemand eine Anzahl von Eimern verwendet, die zufällig einen gemeinsamen Faktor mit der Konstante haben.

In der Praxis ist es ziemlich normal, eine Potenz von 2 als Anzahl der Buckets zu verwenden. Dies ist praktisch und erspart das Suchen oder Vorauswählen einer Primzahl der richtigen Größe. Sie verlassen sich also darauf, dass die Hash-function nicht einmal Multiplikatoren verwendet, was im Allgemeinen eine sichere Annahme ist. Aber Sie können immer noch gelegentlich schlechte Hash-Verhalten basierend auf Hash-functionen wie dem oben genannten erhalten, und Prime Bucket Count könnte weiter helfen.

Das Prinzip “alles muss prime sein” ist meines Wissens eine hinreichende, aber keine notwendige Voraussetzung für eine gute Verteilung über Hashtables. Es erlaubt jedem zu interagieren, ohne davon ausgehen zu müssen, dass die anderen der gleichen Regel gefolgt sind.

[Edit: Es gibt einen anderen, spezielleren Grund, eine Primzahl von Buckets zu verwenden, wenn Sie Kollisionen mit linearem Sondieren behandeln. Dann berechnen Sie einen Schritt aus dem Hash-Code, und wenn dieser Schritt ein Faktor der Bucket-Anzahl ist, dann können Sie nur (Bucket_count / stride) Probes, bevor Sie zurück sind, wo Sie begonnen haben. Der Fall, den Sie am meisten vermeiden möchten, ist stride = 0, was natürlich speziell sein muss, aber um auch das Spezial-Gehäuse bucket_count / stride gleich einer kleinen ganzen Zahl zu vermeiden, können Sie den bucket_count prime machen und egal was Schritt ist vorgesehen, es ist nicht 0.]

Das erste, was Sie tun, wenn Sie aus der Hash-Tabelle einfügen / retraving ist, den Hash-Code für den gegebenen Schlüssel zu berechnen und dann den richtigen Bucket zu finden, indem Sie den Hash-Code auf die Größe der Hash-Tabelle mit hashCode% table_length trimmen. Hier sind 2 ‘Aussagen’, die Sie wahrscheinlich irgendwo gelesen haben

  1. Wenn Sie für table_length eine Potenz von 2 verwenden, ist finding (hashCode (key)% 2 ^ n) so einfach und schnell wie (hashCode (key) & (2 ^ n -1)). Aber wenn Ihre function, HashCode für einen gegebenen Schlüssel zu berechnen, nicht gut ist, werden Sie definitiv unter dem Clustering vieler Schlüssel in einigen Hash-Buckets leiden.
  2. Aber wenn Sie Primzahlen für table_length verwenden, können die berechneten HashCodes in die verschiedenen Hash-Buckets mappen, selbst wenn Sie eine etwas dumme hashCode-function haben.

Und hier ist der Beweis.

Angenommen, Ihre hashCode-function führt zu den folgenden hashCodes unter anderem {x, 2x, 3x, 4x, 5x, 6x …}, dann werden alle diese Cluster in nur m Anzahl von Buckets gruppiert, wobei m = table_length / GreatestCommonFactor (table_length, x). (Es ist trivial, dies zu überprüfen / abzuleiten). Jetzt können Sie einen der folgenden Schritte ausführen, um Clusterbildung zu vermeiden

Stellen Sie sicher, dass Sie nicht zu viele hashCodes erzeugen, die ein Vielfaches eines anderen hashCodes sind, wie in {x, 2x, 3x, 4x, 5x, 6x …}, aber das kann schwierig sein, wenn Ihre HashTabelle dies haben soll Millionen von Einträgen. Oder machen Sie einfach m gleich table_length, indem Sie GreatestCommonFactor (table_length, x) gleich 1 setzen, dh indem Sie table_length co-rime mit x setzen. Und wenn x eine beliebige Zahl sein kann, dann stelle sicher, dass table_length eine Primzahl ist.

Von – http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Ziemlich klare Erklärung, mit Bildern auch.

Bearbeiten: Als Zusammenfassung werden Primzahlen verwendet, weil Sie die beste Chance haben, einen eindeutigen Wert zu erhalten, wenn Sie Werte mit der gewählten Primzahl multiplizieren und sie alle addieren. Wenn Sie zum Beispiel eine Zeichenkette eingeben, wird jeder Buchstabe mit der Primzahl multipliziert, und wenn Sie dann all diese Werte addieren, erhalten Sie seinen Hashwert.

Eine bessere Frage wäre, warum genau die Nummer 31?

tl; dr

index[hash(input)%2] würde zu einer Kollision für die Hälfte aller möglichen Hashes und einer Reihe von Werten führen. index[hash(input)%prime] führt zu einer Kollision von <2 aller möglichen Hashes. Durch das Festlegen des Divisors auf die Tabellengröße wird außerdem sichergestellt, dass die Nummer nicht größer als die Tabelle sein kann.

Primzahlen werden verwendet, weil Sie gute Chancen haben, einen eindeutigen Wert für eine typische Hash-function zu erhalten, die Polynome Modulo P verwendet. Nehmen wir an, Sie verwenden eine solche Hash-function für Strings der Länge < = N, und Sie haben eine Kollision. Das bedeutet, dass 2 verschiedene Polynome denselben Wert modulo P erzeugen. Die Differenz dieser Polynome ist wiederum ein Polynom gleichen Grades N (oder weniger). Es hat nicht mehr als N Wurzeln (hier zeigt sich die Natur der Mathematik selbst, da diese Behauptung nur für ein Polynom über einem Feld gilt => Primzahl). Wenn also N viel kleiner als P ist, haben Sie wahrscheinlich keine Kollision. Danach kann Experiment wahrscheinlich zeigen, dass 37 groß genug ist, um Kollisionen für eine Hash-Tabelle von Strings zu vermeiden, die Länge 5-10 haben, und klein genug ist, um für Berechnungen zu verwenden.

Um einen alternativen Standpunkt zu bieten, gibt es diese Seite:

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

Die besagt, dass Sie die größtmögliche Anzahl von Buckets verwenden sollten, anstatt auf eine Primzahl von Buckets zu runden. Es scheint eine vernünftige Möglichkeit zu sein. Intuitiv kann ich sicherlich sehen, wie eine größere Anzahl von Eimern besser wäre, aber ich kann daraus kein mathematisches Argument machen.

Primzahlen sind eindeutige Zahlen. Sie sind insofern einzigartig, als das Produkt einer Primzahl mit irgendeiner anderen Zahl die beste Chance hat, einzigartig zu sein (nicht so einzigartig wie die Primzahl selbst natürlich), weil eine Primzahl verwendet wird, um sie zu komponieren. Diese Eigenschaft wird in Hashfunktionen verwendet.

Wenn Sie eine Zeichenfolge “Samuel” angeben, können Sie einen eindeutigen Hash generieren, indem Sie die einzelnen Ziffern oder Buchstaben mit einer Primzahl multiplizieren und addieren. Deshalb werden Primzahlen verwendet.

Die Verwendung von Primzahlen ist jedoch eine alte Technik. Der Schlüssel hier zu verstehen, dass Sie, solange Sie einen ausreichend eindeutigen Schlüssel erzeugen können, auch zu anderen Hashing-Techniken wechseln können. Hier finden Sie mehr zu diesem Thema über http://www.azillionmonkeys.com/qed/hash.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Es hängt von der Wahl der Hash-function ab.

Viele Hash-functionen kombinieren die verschiedenen Elemente in den Daten, indem sie mit einigen Faktoren multipliziert werden, wobei die Potenz von zwei der Wortgröße der Maschine entspricht (dieser Modul ist frei, indem die Berechnung einfach überläuft).

Sie möchten keinen gemeinsamen Faktor zwischen einem Multiplikator für ein Datenelement und der Größe der Hash-Tabelle, da es dann vorkommen kann, dass bei einer Variation des Datenelements die Daten nicht über die gesamte Tabelle verteilt werden. Wenn Sie eine Primzahl für die Größe der Tabelle wählen, ist ein solcher gemeinsamer Faktor höchst unwahrscheinlich.

Auf der anderen Seite bestehen diese Faktoren normalerweise aus ungeraden Primzahlen, also sollten Sie auch sicher sein, Zweierpotenzen für Ihre Hash-Tabelle zu verwenden (zB verwendet Eclipse 31, wenn es die Java-Methode hashCode () generiert).

Angenommen, Ihre Tabellengröße (oder die Nummer für Modulo) ist T = (B * C). Wenn nun Hash für Ihre Eingabe wie (N * A * B) ist, wobei N eine ganze Zahl sein kann, wird Ihre Ausgabe nicht gut verteilt. Denn jedes Mal, wenn n C, 2C, 3C usw. wird, beginnt sich Ihre Ausgabe zu wiederholen. dh Ihre Ausgabe wird nur in C-Positionen verteilt. Beachten Sie, dass C hier ist (T / HCF (Tabellengröße, Hash)).

Dieses Problem kann beseitigt werden, indem HCF 1 gemacht wird. Primzahlen sind dafür sehr gut.

Eine andere interessante Sache ist, wenn T 2 ^ N ist. Diese geben die Ausgabe genau gleich wie alle unteren N Bits des Eingabe-Hash. Da jede Zahl Potenzen von 2 dargestellt werden kann, wenn wir Modulo einer beliebigen Zahl mit T nehmen, subtrahieren wir alle Potenzen der 2 Formnummer, die> = N sind, und geben daher abhängig von der Eingabe immer die Nummer des spezifischen Musters ab . Dies ist auch eine schlechte Wahl.

Ähnlich ist auch T als 10 ^ N aus ähnlichen Gründen schlecht (Muster in dezimaler Notation von Zahlen anstelle von binär).

Also, Primzahlen neigen dazu, eine bessere verteilte Ergebnisse zu geben, sind daher eine gute Wahl für die Tabellengröße.

Ich möchte etwas für Steve Jessops Antwort hinzufügen (ich kann es nicht kommentieren, da ich nicht genug Reputation habe). Aber ich habe hilfreiches Material gefunden. Seine Antwort ist sehr hilfreich, aber er hat einen Fehler gemacht: Die Eimergröße sollte keine Zweierpotenz sein. Ich zitiere nur aus dem Buch “Introduction to Algorithm” von Thomas Cormen, Charles Leisersen, et al. Auf Seite 263:

Wenn wir die Divisionsmethode verwenden, vermeiden wir normalerweise bestimmte Werte von m. Zum Beispiel sollte m keine Potenz von 2 sein, denn wenn m = 2 ^ p, dann ist h (k) nur die p Bits niedrigster Ordnung von k. Wenn wir nicht wissen, dass alle p-Bit-Muster niedriger Ordnung gleich wahrscheinlich sind, ist es besser, die Hash-function so zu gestalten, dass sie von allen Bits des Schlüssels abhängt. Wie in Aufgabe 11.3-3 beschrieben, ist die Wahl von m = 2 ^ p-1, wenn k eine in radix 2 interpretierte Zeichenkette ist, eine schlechte Wahl, da die Permutation der Zeichen von k nicht den Hash-Wert ändert.

Ich hoffe es hilft.

Kopieren von meiner anderen Antwort https://stackoverflow.com/a/43126969/917428 . Sehen Sie es für weitere Details und Beispiele.

Ich glaube, dass es nur damit zu tun hat, dass Computer in Base 2 arbeiten. Denken Sie nur daran, wie das Gleiche für Base 10 funktioniert:

  • 8% 10 = 8
  • 18% 10 = 8
  • 87865378% 10 = 8

Es spielt keine Rolle, wie die Zahl ist: Solange sie mit 8 endet, ist ihr Modulo 10 8.

Die Auswahl einer ausreichend großen Zahl, die keine Zweierpotenz ist, stellt sicher, dass die Hash-function wirklich eine function aller Eingangsbits ist, und nicht nur eine Teilmenge davon.

Für eine Hash-function ist es nicht nur wichtig, Koloskopien allgemein zu minimieren, sondern es auch unmöglich zu machen, mit dem gleichen Hash zu bleiben, während einige Bytes getastet werden.

Angenommen, Sie haben eine Gleichung: (x + y*z) % key = x mit 0 und 0 . Wenn der Schlüssel eine Primzahl ist, gilt n * y = Schlüssel ist für jedes n in N wahr und für jede andere Zahl falsch.

Ein Beispiel, in dem der Schlüssel kein Paradebeispiel ist: x = 1, z = 2 und Schlüssel = 8 Weil Schlüssel / z = 4 immer noch eine natürliche Zahl ist, wird 4 eine Lösung für unsere Gleichung und in diesem Fall (n / 2) * y = Schlüssel ist für jedes n in N wahr. Die Menge an Lösungen für die Gleichung hat sich praktisch verdoppelt, weil 8 keine Primzahl ist.

Wenn unser Angreifer bereits weiß, dass 8 eine mögliche Lösung für die Gleichung ist, kann er die Datei von 8 auf 4 ändern und erhält immer noch den gleichen Hash.

Ich habe die beliebte WordPress-Website gelesen, die oben in einigen der oben genannten Antworten verlinkt ist. Nach dem, was ich verstanden habe, möchte ich eine einfache Beobachtung teilen, die ich gemacht habe.

Sie können alle Details in diesem Artikel finden , gehen aber davon aus, dass Folgendes zutrifft:

  • Die Verwendung einer Primzahl gibt uns die “beste Chance” eines einzigartigen Wertes

Eine generelle Hashmap-Implementierung möchte, dass zwei Dinge einzigartig sind.

  • Eindeutiger Hash-Code für den Schlüssel
  • Eindeutiger Index zum Speichern des tatsächlichen Werts

Wie bekommen wir den einzigartigen Index? Indem man auch die Anfangsgröße des internen Containers zu einem Prime macht. Also im Grunde genommen ist prim beteiligt, weil es dieses einzigartige Merkmal besitzt, einzigartige Zahlen zu erzeugen, die wir letztendlich verwenden, um ID-Objekte zu benutzen und Indizes innerhalb des internen Containers zu finden.

Beispiel:

Schlüssel = “Schlüssel”

value = “Wert” uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

Karten mit eindeutiger ID

Jetzt wollen wir einen einzigartigen Standort für unseren Wert – also wir

uniqueId % internalContainerSize == uniqueLocationForValue , unter der Annahme, dass internalContainerSize ebenfalls eine Primzahl ist.

Ich weiß, dass das vereinfacht ist, aber ich hoffe, dass ich die allgemeine Idee durchsetzen kann.