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?
language-agnostic
data-structures
hash
theschmitzer
quelle
quelle
Antworten:
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:
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.]
quelle
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
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
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?
quelle
*32
es sich um eine einfache Bitverschiebung oder noch besser um einen sofortigen Adressenskalierungsfaktor handelt (z. B.lea eax,eax*8; leax, eax,eax*4
bei x86 / x64). Ist*31
also 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 ...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.quelle
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.
quelle
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.
quelle
http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
quelle
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).
quelle
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.
quelle
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:
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.
quelle
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:
Ich hoffe es hilft.
quelle
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 = x
mit0<x<key
und0<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.
quelle
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:
Eine allgemeine Hashmap-Implementierung möchte, dass zwei Dinge eindeutig sind.
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 == uniqueLocationForValue
vorausgesetzt, esinternalContainerSize
ist auch eine Primzahl.Ich weiß, dass dies vereinfacht ist, aber ich hoffe, die allgemeine Idee durchzubringen.
quelle
"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 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.
quelle
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 überclz
("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 logischeand
. 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
2) Verwenden Sie bessere Maßnahmen gegen den tatsächlichen Angriff, zusammen mit einer schnellen Kraft von 2 Größen.
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.
quelle
quelle