Warum sollten Hash-Funktionen einen Primzahlmodul verwenden?

335

Vor langer Zeit habe ich ein Datenstrukturbuch für 1,25 US-Dollar vom Schnäppchen-Tisch gekauft. Darin lautete die Erklärung für eine Hashing-Funktion, dass sie aufgrund der "Natur der Mathematik" letztendlich um eine Primzahl modifiziert werden sollte.

Was erwarten Sie von einem Buch im Wert von 1,25 USD?

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

Ist die Verteilung der Zahlen wirklich gleichmäßiger, selbst wenn es eine Primzahl von Eimern gibt? Oder ist dies eine alte Programmierergeschichte, die jeder akzeptiert, weil alle anderen sie akzeptieren?

theschmitzer
quelle
1
Vollkommen vernünftige Frage: Warum sollte es eine Primzahl von Eimern geben?
Draemon
1
Diese Frage scheint nicht zum Thema zu gehören, da sie höchstwahrscheinlich zur Informatik gehört .
Leichtigkeitsrennen im Orbit
2
cs.stackexchange.com/a/64191/64222 eine weitere gut argumentierte Erklärung.
Grüner Baum
Hier ist eine weitere gute Erklärung für eine etwas verwandte Frage mit einigen überraschenden Beweiszahlen
quora.com/…

Antworten:

242

Normalerweise funktioniert eine einfache Hash-Funktion, indem die "Komponenten" der Eingabe (Zeichen im Fall einer Zeichenfolge) mit den Potenzen einer Konstanten multipliziert und zu einem ganzzahligen Typ addiert werden. So könnte beispielsweise ein typischer (wenn auch nicht besonders guter) Hash eines Strings sein:

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

Wenn dann eine Reihe von Zeichenfolgen eingespeist werden, die alle das gleiche erste Zeichen haben, sind die Ergebnisse alle das gleiche Modulo k, zumindest bis der ganzzahlige Typ überläuft.

[Als Beispiel ist Javas String hashCode diesem unheimlich ähnlich - er führt die Zeichen in umgekehrter Reihenfolge mit k = 31 aus. Sie erhalten also auffällige Beziehungen Modulo 31 zwischen Zeichenfolgen, die auf die gleiche Weise enden, und auffällige Beziehungen Modulo 2 ^ 32 zwischen Zeichenfolgen, die bis auf das Ende gleich sind. Dies bringt das Hashtable-Verhalten nicht ernsthaft durcheinander.]

Eine Hashtabelle berechnet den Modul des Hash über die Anzahl der Buckets.

In einer Hashtabelle ist es wichtig, in wahrscheinlichen Fällen keine Kollisionen zu erzeugen, da Kollisionen die Effizienz der Hashtabelle verringern.

Angenommen, jemand fügt eine ganze Reihe von Werten in eine Hashtabelle ein, die eine Beziehung zwischen den Elementen haben, wie alle, die das gleiche erste Zeichen haben. Ich würde sagen, dies ist ein ziemlich vorhersehbares Nutzungsmuster, daher möchten wir nicht, dass es zu viele Kollisionen erzeugt.

Es stellt sich heraus, dass "aufgrund der Natur der Mathematik", wenn die im Hash verwendete Konstante und die Anzahl der Buckets Koprime sind , Kollisionen in einigen häufigen Fällen minimiert werden. Wenn sie nicht koprime sindDann gibt es einige ziemlich einfache Beziehungen zwischen Eingaben, für die Kollisionen nicht minimiert werden. Alle Hashes sind gleich modulo dem gemeinsamen Faktor, was bedeutet, dass sie alle in das 1 / n-te der Buckets fallen, deren Wert modulo der gemeinsame Faktor ist. 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 nicht akzeptabel ist, mindestens doppelt so viele Kollisionen wie normal zu erzeugen. Wenn ein Benutzer unsere Verteilung in Eimer aufteilt, möchten wir, dass es sich um einen Freak-Unfall handelt und nicht um eine einfache vorhersehbare Verwendung.

Jetzt haben Hashtable-Implementierungen offensichtlich keine Kontrolle über die darin enthaltenen Elemente. Sie können nicht verhindern, dass sie verwandt sind. Sie müssen also sicherstellen, dass die Anzahl der Konstanten und der Bucket gleichzeitig erfolgt. Auf diese Weise verlassen Sie sich nicht nur auf die "letzte" Komponente, um den Modul des Eimers in Bezug auf einen kleinen gemeinsamen Faktor zu bestimmen. Soweit ich weiß, müssen sie nicht erstklassig sein, um dies zu erreichen, sondern nur Koprime.

Wenn die Hash-Funktion und die Hashtabelle jedoch unabhängig voneinander geschrieben werden, weiß die Hashtabelle nicht, wie die Hash-Funktion funktioniert. Möglicherweise wird eine Konstante mit kleinen Faktoren verwendet. Wenn Sie Glück haben, funktioniert es möglicherweise ganz anders und ist nichtlinear. Wenn der Hash gut genug ist, ist jede Bucket-Anzahl in Ordnung. Eine paranoide Hashtabelle kann jedoch keine gute Hash-Funktion annehmen und sollte daher eine Primzahl von Buckets verwenden. In ähnlicher Weise sollte eine paranoide Hash-Funktion eine größere Primkonstante verwenden, um die Wahrscheinlichkeit zu verringern, dass jemand eine Anzahl von Buckets verwendet, die zufällig einen gemeinsamen Faktor mit der Konstante haben.

In der Praxis halte ich es für ziemlich normal, eine Potenz von 2 als Anzahl der Eimer zu verwenden. Dies ist praktisch und erspart das Durchsuchen oder Vorauswählen einer Primzahl der richtigen Größe. Sie verlassen sich also auf die Hash-Funktion, um nicht einmal Multiplikatoren zu verwenden, was im Allgemeinen eine sichere Annahme ist. Aber Sie können immer noch gelegentlich schlechte Hashing-Verhaltensweisen erhalten, die auf Hash-Funktionen wie der oben beschriebenen basieren, und die Anzahl der Haupt-Buckets könnte weiter helfen.

Das Prinzip, dass "alles Primzahl sein muss", ist meines Wissens eine ausreichende, aber nicht notwendige Voraussetzung für eine gute Verteilung über Hashtabellen. Es ermöglicht jedem, zusammenzuarbeiten, ohne davon ausgehen zu müssen, dass die anderen die gleiche Regel befolgt haben.

[Bearbeiten: Es gibt einen anderen, spezielleren Grund, eine Primzahl von Buckets zu verwenden, wenn Sie Kollisionen mit linearer Abtastung behandeln. Dann berechnen Sie einen Schritt aus dem Hashcode, und wenn sich herausstellt, dass dieser Schritt ein Faktor für die Bucket-Anzahl ist, können Sie nur (Bucket_Count / Stride) -Sonden durchführen, bevor Sie wieder dort sind, wo Sie begonnen haben. Der Fall, den Sie am meisten vermeiden möchten, ist natürlich stride = 0, was ein Sonderfall sein muss. Um jedoch auch zu vermeiden, dass Bucket_count / Stride mit Sondergehäusen gleich einer kleinen Ganzzahl ist, können Sie einfach den Bucket_count prim machen und sich nicht darum kümmern, was der ist Schritt ist vorausgesetzt, es ist nicht 0.]

Steve Jessop
quelle
Nur als Randnotiz: Eine Diskussion für eine sinnvolle Wahl des Faktors k für HashCodes ist hier: stackoverflow.com/q/1835976/21499
Hans-Peter Störr
9
Das ist eine großartige Antwort. Können Sie dies bitte weiter erläutern? "So erhalten Sie auffällige Beziehungen Modulo 31 zwischen Zeichenfolgen, die auf die gleiche Weise enden, und auffällige Beziehungen Modulo 2 ^ 32 zwischen Zeichenfolgen, die bis auf das Ende gleich sind. Dies führt zu keinem ernsthaften Durcheinander des Hashtable-Verhaltens. "" Ich verstehe besonders nicht den 2 ^ 32 Teil
gewöhnlichen
2
Zusätzlicher Hinweis, um dies klarer zu machen: "Alle Hashes sind gleich modulo der gemeinsame Faktor" -> Dies liegt daran, wenn Sie die Beispiel-Hash-Funktion hash = 1. Zeichen + 2. Zeichen * k + ... und betrachten Nehmen Sie Zeichenfolgen mit demselben ersten Zeichen. Hash% k ist für diese Zeichenfolgen gleich. Wenn M die Größe der Hashtabelle ist und g die gcd von M und k ist, dann ist (Hash% k)% g gleich Hash% g (da g k teilt) und daher ist Hash% g auch für diese Zeichenfolgen gleich. Betrachten Sie nun (Hash% M)% g, dies ist gleich Hash% g (da g M teilt). Also (Hash% M)% g ist für alle diese Zeichenfolgen gleich.
Quark
1
@DanielMcLaury Joshua Bloch erklärte, warum für Java - es wurde in zwei populären Büchern (K & R, Dragon-Buch) empfohlen und zeigte eine gute Leistung bei geringen Kollisionen im englischen Wörterbuch. Es ist schnell (verwendet die Horner-Methode ). Anscheinend kann sich sogar K & R nicht erinnern, woher es kam. Eine ähnliche Funktion ist der Rabin-Fingerabdruck des Rabin-Karp-Algorithmus (1981), aber K & R (1978) geht dem voraus.
Bain
1
@SteveJessop, können Sie bitte erklären, "auffällige Beziehungen modulo 2 ^ 32 zwischen Zeichenfolgen, die bis auf das Ende gleich sind"? Vielen Dank.
Khanna111
29

Das erste, was Sie beim Einfügen / Abrufen von Hash-Tabellen tun müssen, ist, den Hash-Code für den angegebenen Schlüssel zu berechnen und dann den richtigen Bucket zu finden, indem Sie den Hash-Code auf die Größe der Hash-Tabelle zuschneiden, indem Sie Hash-Code% table_length ausführen. Hier sind 2 'Aussagen', die Sie höchstwahrscheinlich irgendwo gelesen haben

  1. Wenn Sie für table_length eine Potenz von 2 verwenden, ist das Finden von (hashCode (Schlüssel)% 2 ^ n) so einfach und schnell wie (hashCode (Schlüssel) & (2 ^ n -1)). Wenn Ihre Funktion zum Berechnen von hashCode für einen bestimmten Schlüssel jedoch nicht gut ist, leiden Sie definitiv unter dem Clustering vieler Schlüssel in einigen Hash-Buckets.
  2. Wenn Sie jedoch Primzahlen für table_length verwenden, können die berechneten HashCodes den verschiedenen Hash-Buckets zugeordnet werden, selbst wenn Sie eine etwas dumme HashCode-Funktion haben.

Und hier ist der Beweis.

Wenn Ihre hashCode-Funktion unter anderem zu folgenden hashCodes führt {x, 2x, 3x, 4x, 5x, 6x ...}, werden alle diese in nur m Buckets zusammengefasst, 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 Clustering zu vermeiden

Stellen Sie sicher, dass Sie nicht zu viele Hashcodes generieren, die ein Vielfaches eines anderen HashCodes sind, wie in {x, 2x, 3x, 4x, 5x, 6x ...}. Dies kann jedoch schwierig sein, wenn Ihre HashTabelle dies haben soll Millionen von Einträgen. Oder machen Sie m einfach gleich table_length, indem Sie GreatestCommonFactor (table_length, x) gleich 1 machen, dh indem Sie table_length coprime mit x machen. Und wenn x eine beliebige Zahl sein kann, stellen Sie sicher, dass table_length eine Primzahl ist.

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


quelle
11

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

Ziemlich klare Erklärung, auch mit Bildern.

Bearbeiten: Zusammenfassend werden Primzahlen verwendet, da Sie die beste Chance haben, einen eindeutigen Wert zu erhalten, wenn Sie Werte mit der ausgewählten Primzahl multiplizieren und alle addieren. Wenn Sie beispielsweise eine Zeichenfolge angeben und jeden Buchstaben mit der Primzahl multiplizieren und dann alle addieren, erhalten Sie den Hashwert.

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

AlbertoPL
quelle
5
Obwohl ich denke, dass eine Zusammenfassung hilfreich wäre, falls diese Site jemals tot sein sollte, wird ein Rest ihres Inhalts hier auf SO gespeichert.
Thomas Owens
2
Der Artikel erklärt nicht warum, sondern sagt: "Forscher fanden heraus, dass die Verwendung einer Primzahl von 31 eine bessere Verteilung der Schlüssel und eine geringere Anzahl von Kollisionen ergibt. Niemand weiß warum ..." Witzig und stellte die gleiche Frage wie ich .
Theschmitzer
> Eine bessere Frage wäre, warum genau die Nummer 31? Wenn Sie meinen, warum die Nummer 31 verwendet wird, dann sagt Ihnen der Artikel, auf den Sie verweisen, warum, dh weil es schnell zu multiplizieren ist und Cos-Tests zeigen, dass es die beste ist, die verwendet werden kann. Der andere beliebte Multiplikator, den ich gesehen habe, ist 33, was der Theorie Gewicht verleiht, dass das Geschwindigkeitsproblem (zumindest anfangs) ein wichtiger Faktor war. Wenn Sie meinen, was ist mit 31, das es in den Tests besser macht, dann fürchte ich, ich weiß es nicht.
sgmoore
Genau, der einzige Grund, warum es als Multiplikator hätte verwendet werden können, war, dass es leicht zu multiplizieren war. (Wenn ich sage, ich habe 33 als Multiplikator verwendet gesehen, meine ich nicht, dass dies in letzter Zeit wahrscheinlich Jahrzehnte her war und möglich war, bevor viele Analysen zum Hashing durchgeführt wurden).
sgmoore
3
@SteveJessop Die Zahl 31 kann von der CPU leicht als (x * 32) -1-Operation optimiert werden, bei der *32es sich um eine einfache Bitverschiebung oder noch besser um einen sofortigen Adressenskalierungsfaktor handelt (z. B. lea eax,eax*8; leax, eax,eax*4bei x86 / x64). Ist *31also ein guter Kandidat für die Multiplikation von Primzahlen. Dies war vor einigen Jahren ziemlich richtig - jetzt hat die neueste CPU-Architektur eine fast sofortige Multiplikation - die Division ist immer langsamer ...
Arnaud Bouchez
10

tl; dr

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

Indolering
quelle
1
2 ist ein Primzahl-Typ
Ganesh Chowdhary Sadanala
8

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

TT_
quelle
1
Während die Erklärung jetzt offensichtlich zu sein scheint, kam sie mir nach dem Lesen eines Buches von A.Shen "Programmierung: Theoreme und Probleme" (auf Russisch), siehe Diskussion des Rabin-Algorithmus. Ich bin mir nicht sicher, ob eine englische Übersetzung vorhanden ist.
TT_
5

Nur um einen alternativen Standpunkt zu bieten, gibt es diese Seite:

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

Was besagt, dass Sie die größtmögliche Anzahl von Eimern verwenden sollten, anstatt auf eine Primzahl von Eimern abzurunden. 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 kein mathematisches Argument dafür vorbringen.

Falaina
quelle
Eine größere Anzahl von Eimern bedeutet weniger Kollisionen: Siehe das Pigeonhole-Prinzip.
Unbekannt
11
@ Unbekannt: Ich glaube nicht, dass das stimmt. Bitte korrigieren Sie mich, wenn ich falsch liege, aber ich glaube, wenn Sie das Pigeonhole-Prinzip auf Hash-Tabellen anwenden, können Sie nur dann behaupten, dass es zu Kollisionen kommt, wenn Sie mehr Elemente als Bins haben, und keine Rückschlüsse auf die Anzahl oder Dichte der Kollisionen ziehen. Ich glaube jedoch immer noch, dass die größere Anzahl von Behältern die richtige Route ist.
Falaina
Wenn Sie davon ausgehen, dass die Kollisionen in jeder Hinsicht zufällig sind, verringert ein größeres Leerzeichen (Buckets) nach dem Geburtstagsparadox die Wahrscheinlichkeit, dass eine Kollision auftritt.
Unbekannt
1
@ Unbekannt Sie haben übersehen, dass Kollisionen auch von der Hash-Funktion selbst abhängen. Also, wenn die has-Funktion wirklich schlecht ist, dann kann es immer noch zu erheblichen Kollisionen kommen, egal wie groß Sie die Größe erhöhen
Suraj Chandran
Der ursprüngliche Artikel scheint verschwunden zu sein, aber hier gibt es einige aufschlussreiche Kommentare, einschließlich einer Diskussion mit dem ursprünglichen Autor. news.ycombinator.com/item?id=650487
Adrian McCarthy
3

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

Mit einer Zeichenfolge „Samuel“ können Sie einen eindeutigen Hash generieren, indem Sie jede der einzelnen Ziffern oder Buchstaben mit einer Primzahl multiplizieren und addieren. Aus diesem Grund werden Primzahlen verwendet.

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

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

user105033
quelle
1
hahahah .... hat das Produkt von 2 Primzahlen nicht eine bessere Chance, "einzigartig" zu sein als das Produkt einer Primzahl und einer anderen Zahl?
HasaniH
@Beska Hier wird "Eindeutigkeit" rekursiv definiert, daher glaube ich, dass "Nicht-Eindeutigkeit" auf die gleiche Weise definiert werden sollte :)
TT_
3

Dies hängt von der Wahl der Hash-Funktion ab.

Viele Hash-Funktionen kombinieren die verschiedenen Elemente in den Daten, indem sie mit einigen Faktoren multipliziert werden, die die Zweierpotenz entsprechend der Wortgröße der Maschine modulo (dieser Modul ist frei, indem nur die Berechnung überlaufen gelassen wird).

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 durch Variieren 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. Daher sollten Sie auch sicher sein, wenn Sie Zweierpotenzen für Ihre Hash-Tabelle verwenden (z. B. verwendet Eclipse 31, wenn es die Java-Methode hashCode () generiert).

Sternenblau
quelle
2

Angenommen, Ihre Tabellengröße (oder die Zahl für Modulo) ist T = (B * C). Wenn der Hash für Ihre Eingabe wie (N * A * B) ist, wobei N eine beliebige Ganzzahl sein kann, ist Ihre Ausgabe nicht gut verteilt. Da jedes Mal, wenn n zu 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 (T / HCF (Tabellengröße, Hash)) ist.

Dieses Problem kann durch die Herstellung von HCF 1 behoben werden. Die 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, subtrahieren wir, wenn wir Modulo einer beliebigen Zahl mit T nehmen, alle Potenzen von 2 Formnummern, die> = N sind, und geben daher abhängig von der Eingabe immer die Anzahl eines bestimmten Musters ab . Dies ist auch eine schlechte Wahl.

In ähnlicher Weise ist T als 10 ^ N aus ähnlichen Gründen ebenfalls schlecht (Muster in Dezimalschreibweise von Zahlen anstelle von Binär).

Primzahlen ergeben daher tendenziell besser verteilte Ergebnisse und sind daher eine gute Wahl für die Tabellengröße.

nishantbhardwaj2002
quelle
2

Kopieren von meiner anderen Antwort https://stackoverflow.com/a/43126969/917428 . Weitere Details und Beispiele finden Sie hier.

Ich glaube, dass es nur damit zu tun hat, dass Computer in Basis 2 funktionieren. Denken Sie nur daran, wie dasselbe für Basis 10 funktioniert:

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

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

Wenn Sie eine ausreichend große Zahl ohne Zweierpotenz auswählen, wird sichergestellt, dass die Hash-Funktion wirklich eine Funktion aller Eingabebits ist und nicht eine Teilmenge davon.

Ste_95
quelle
1

Ich möchte etwas für Steve Jessops Antwort hinzufügen (ich kann es nicht kommentieren, da ich nicht genug Ruf habe). Aber ich habe hilfreiches Material gefunden. Seine Antwort ist sehr hilfreich, aber er hat einen Fehler gemacht: Die Eimergröße sollte keine Potenz von 2 sein. Ich zitiere nur aus dem Buch "Einführung in den Algorithmus" von Thomas Cormen, Charles Leisersen et al. Auf Seite 263:

Bei Verwendung der Divisionsmethode vermeiden wir normalerweise bestimmte Werte von m. Zum Beispiel sollte m keine Potenz von 2 sein, da wenn m = 2 ^ p ist, h (k) nur die p Bits niedrigster Ordnung von k sind. Wenn wir nicht wissen, dass alle p-Bit-Muster niedriger Ordnung gleich wahrscheinlich sind, ist es besser, die Hash-Funktion so zu gestalten, dass sie von allen Bits des Schlüssels abhängt. Wie Sie in Übung 11.3-3 zeigen müssen, kann die Wahl von m = 2 ^ p-1, wenn k eine in Radix 2 ^ p interpretierte Zeichenfolge ist, eine schlechte Wahl sein, da das Permutieren der Zeichen von k den Hashwert nicht ändert.

Ich hoffe es hilft.

iefgnoix
quelle
0

Für eine Hash-Funktion ist es nicht nur wichtig, Kolisionen im Allgemeinen zu minimieren, sondern es auch unmöglich zu machen, beim Ändern einiger Bytes beim gleichen Hash zu bleiben.

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

Ein Beispiel, bei dem Schlüssel kein Hauptbeispiel ist: x = 1, z = 2 und Schlüssel = 8 Da 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 gilt für jedes n in N. Die Anzahl der Lösungen für die Gleichung hat sich praktisch verdoppelt, da 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 trotzdem den gleichen Hash.

Christian
quelle
0

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

Sie finden alle Details im Artikel hier , gehen jedoch davon aus, dass Folgendes zutrifft:

  • Die Verwendung einer Primzahl gibt uns die "beste Chance" auf einen eindeutigen Wert

Eine allgemeine Hashmap-Implementierung möchte, dass zwei Dinge eindeutig sind.

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

Wie erhalten wir den eindeutigen Index? Indem Sie auch die Anfangsgröße des internen Containers zu einer Primzahl machen. Prime ist also im Grunde genommen beteiligt, weil es diese einzigartige Eigenschaft besitzt, eindeutige Zahlen zu erzeugen, die wir letztendlich verwenden, um Objekte zu identifizieren und Indizes innerhalb des internen Containers zu finden.

Beispiel:

key = "key"

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

Karten zu eindeutiger ID

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

uniqueId % internalContainerSize == uniqueLocationForValuevorausgesetzt, es internalContainerSizeist auch eine Primzahl.

Ich weiß, dass dies vereinfacht ist, aber ich hoffe, die allgemeine Idee durchzubringen.

Ryan
quelle
0

"Die Natur der Mathematik" in Bezug auf Primzahlmodule ist, dass sie ein Baustein eines endlichen Feldes sind . Die anderen beiden Bausteine ​​sind eine Additions- und eine Multiplikationsoperation. Die besondere Eigenschaft von Primmodulen besteht darin, dass sie mit den "regulären" Additions- und Multiplikationsoperationen, die gerade auf den Modul gebracht werden, ein endliches Feld bilden. Dies bedeutet, dass jede Multiplikation einem anderen ganzzahligen Modulo der Primzahl zugeordnet wird, ebenso wie jede Addition.

Primzahlmodule sind vorteilhaft, weil:

  • Sie bieten die größte Freiheit bei der Auswahl des sekundären Multiplikators beim sekundären Hashing. Alle Multiplikatoren außer 0 besuchen alle Elemente genau einmal
  • Wenn alle Hashes kleiner als der Modul sind, gibt es überhaupt keine Kollisionen
  • Zufällige Primzahlen mischen sich besser als die Potenz zweier Module und komprimieren die Informationen aller Bits, nicht nur einer Teilmenge

Sie haben jedoch einen großen Nachteil, sie erfordern eine Ganzzahldivision, die selbst auf einer modernen CPU viele (~ 15-40) Zyklen dauert. Mit ungefähr der Hälfte der Berechnung kann man sicherstellen, dass der Hash sehr gut verwechselt ist. Zwei Multiplikationen und Xorshift-Operationen mischen sich besser als ein Prime-Moudulus. Dann können wir jede Hash-Tabellengröße verwenden, und die Hash-Reduzierung ist am schnellsten. Insgesamt ergeben sich 7 Operationen für eine Potenz von 2 Tabellengrößen und ungefähr 9 Operationen für beliebige Größen.

Ich habe mir kürzlich viele der schnellsten Hash-Tabellen-Implementierungen angesehen und die meisten von ihnen verwenden keine Primmodule.

Wolfgang Brehm
quelle
0

Diese Frage wurde mit der angemesseneren Frage zusammengeführt, warum Hash-Tabellen Arrays in Prime-Größe und keine Potenz von 2 verwenden sollten. Für Hash-Funktionen selbst gibt es hier viele gute Antworten, aber für die verwandte Frage, warum einige sicherheitskritische Hash-Tabellen Verwenden Sie wie bei glibc Arrays in erstklassiger Größe, es gibt noch keine.

Im Allgemeinen ist die Leistung von 2 Tischen viel schneller. Dort die teure h % n => h & bitmask, bei der die Bitmaske über clz("count führende Nullen") der Größe n berechnet werden kann . Eine Modulo-Funktion muss eine Ganzzahldivision durchführen, die etwa 50x langsamer ist als eine logische and. Es gibt einige Tricks, um ein Modulo zu vermeiden, wie die Verwendung von Lemires https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ , aber im Allgemeinen verbrauchen schnelle Hash-Tabellen Strom von 2 und sichere Hash-Tabellen verwenden Primzahlen.

Warum so?

Sicherheit wird in diesem Fall durch Angriffe auf die Kollisionsauflösungsstrategie definiert, bei der bei den meisten Hash-Tabellen nur eine lineare Suche in einer verknüpften Liste von Kollisionen durchgeführt wird. Oder mit der schnelleren offenen Adressierungstabelle lineare Suche in der Tabelle direkt. Mit der Potenz von 2 Tabellen und einigen internen Kenntnissen der Tabelle, z. B. der Größe oder der Reihenfolge der Liste der Schlüssel, die von einer JSON-Schnittstelle bereitgestellt werden, erhalten Sie die Anzahl der verwendeten richtigen Bits. Die Anzahl der Einsen auf der Bitmaske. Dies ist normalerweise niedriger als 10 Bit. Und für 5-10 Bit ist es trivial, Brute-Force-Kollisionen selbst mit den stärksten und langsamsten Hash-Funktionen durchzuführen. Sie erhalten nicht mehr die volle Sicherheit Ihrer 32-Bit- oder 64-Bit-Hash-Funktionen. Und es geht darum, schnelle kleine Hash-Funktionen zu verwenden, nicht Monster wie Murmeln oder sogar Siphash.

Wenn Sie also eine externe Schnittstelle zu Ihrer Hash-Tabelle bereitstellen, z. B. einen DNS-Resolver, eine Programmiersprache, ... möchten Sie sich um Missbrauchsleute kümmern, die solche Dienste gerne DOS-fähig machen. Normalerweise ist es für solche Leute einfacher, Ihren öffentlichen Dienst mit viel einfacheren Methoden zu schließen, aber es ist passiert. Also kümmerten sich die Leute darum.

Die beste Möglichkeit, solche Kollisionsangriffe zu verhindern, ist also entweder

1) Prime Tables verwenden, weil dann

  • Alle 32 oder 64 Bit sind relevant, um den Bucket zu finden, nicht nur einige.
  • Die Funktion zum Ändern der Größe von Hash-Tabellen ist natürlicher als nur doppelt. Die beste Wachstumsfunktion ist die Fibonacci-Sequenz, und die Primzahlen kommen dieser näher als die Verdoppelung.

2) Verwenden Sie bessere Maßnahmen gegen den tatsächlichen Angriff, zusammen mit einer schnellen Kraft von 2 Größen.

  • Zählen Sie die Kollisionen und brechen Sie bei erkannten Angriffen ab oder schlafen Sie. Dies sind Kollisionszahlen mit einer Wahrscheinlichkeit von <1%. Wie 100 mit 32-Bit-Hash-Tabellen. Dies ist z. B. der DNS-Resolver von djb.
  • Konvertieren Sie die verknüpfte Liste von Kollisionen in Bäume mit O (log n) -Suche und nicht O (n), wenn ein Kollisionsangriff erkannt wird. Dies ist, was zB Java tut.

Es gibt einen weit verbreiteten Mythos, dass sicherere Hash-Funktionen helfen, solche Angriffe zu verhindern, was falsch ist, wie ich erklärt habe. Es gibt keine Sicherheit nur mit niedrigen Bits. Dies würde nur mit Tabellen in Prime-Größe funktionieren, aber dies würde eine Kombination der beiden langsamsten Methoden verwenden, Slow Hash plus Slow Prime Modulo.

Hash-Funktionen für Hash-Tabellen müssen in erster Linie klein (inlinierbar) und schnell sein. Sicherheit kann nur durch die Verhinderung der linearen Suche bei Kollisionen erreicht werden. Und keine trivial schlechten Hash-Funktionen zu verwenden, wie solche, die für einige Werte unempfindlich sind (wie \ 0 bei Verwendung der Multiplikation).

Die Verwendung von zufälligen Startwerten ist ebenfalls eine gute Option. Die Leute haben zuerst damit begonnen, aber mit genügend Informationen in der Tabelle hilft selbst ein zufälliger Startwert nicht viel, und dynamische Sprachen machen es normalerweise trivial, den Startwert über andere Methoden abzurufen, da er in gespeichert ist bekannte Speicherplätze.

rurban
quelle
-1
function eratosthenes(n) {

    function getPrime(x) {
        var middle = (x-(x%2))/2;
        var arr_rest = [];
        for(var j=2 ; j<=middle;j++){
            arr_rest.push(x%j);
        }

        if(arr_rest.indexOf(0) == -1) {
            return true
        }else {
            return false
        }

    }
    if(n<2)  {
        return []
    }else if(n==2){
        return [2]
    }else {
        var arr = [2]
        for(var i=3;i<n;i++) {
            if(getPrime(i)){
                arr.push(i)
            }
        }
    }

    return arr;
}
Khaireddine Hamdi
quelle
2
Könnten Sie bitte Kommentare hinzufügen, um Ihre Lösung zu erläutern?
pom421