Ich habe verschiedene Algorithmen getestet, um die Geschwindigkeit und die Anzahl der Kollisionen zu messen

Ich habe drei verschiedene Schlüsselsätze verwendet:

• Eine Liste von 216.553 englischen Wörtern ^{🕗  Archiv} (in Kleinbuchstaben)
• Die Zahlen "1" bis "216553" (denken Sie an Postleitzahlen und , wie ein schlechter Hash msn.com eruntergefahren hat ^{🕗  Archiv} )
• 216.553 “ zufällige „(dh Typ 4-UUID ) GUIDs

Für jeden Korpus die Anzahl der Kollisionen und die durchschnittliche Zeit, die für das Hashing aufgewendet wurde wurde aufgezeichnet.

Ich habe getestet:

• DJB2
• DJB2a (Variante mit xor anstelle von +)
• FNV-1 (32-Bit)
• FNV-1a (32-Bit)
• SDBM
• CRC32
• Murmur2 (32-Bit)
• SuperFastHash

Ergebnisse

Jedes Ergebnis enthält die durchschnittliche Hash-Zeit und die Anzahl der Kollisionen

Hash Lowercase Random UUID Numbers ============= ============= =========== ============== Murmur 145 ns 259 ns 92 ns 6 collis 5 collis 0 collis FNV-1a 152 ns 504 ns 86 ns 4 collis 4 collis 0 collis FNV-1 184 ns 730 ns 92 ns 1 collis 5 collis 0 collis▪ DBJ2a 158 ns 443 ns 91 ns 5 collis 6 collis 0 collis▪▪▪ DJB2 156 ns 437 ns 93 ns 7 collis 6 collis 0 collis▪▪▪ SDBM 148 ns 484 ns 90 ns 4 collis 6 collis 0 collis** SuperFastHash 164 ns 344 ns 118 ns 85 collis 4 collis 18742 collis CRC32 250 ns 946 ns 130 ns 2 collis 0 collis 0 collis LoseLose 338 ns - - 215178 collis 

Hinweise :

• Die Der LoseLose-Algorithmus (wobei Hash = Hash + Zeichen) ist wirklich schrecklich . Alles kollidiert in denselben 1.375 Eimern.
• SuperFastHash ist schnell und die Dinge sehen ziemlich verstreut aus. Meine Güte, die Zahl Kollisionen. Ich hoffe, der Typ, der es portiert hat, hat etwas falsch gemacht; es ist ziemlich schlecht
• CRC32 ist ziemlich gut . Langsamer und eine 1k-Nachschlagetabelle

Treten tatsächlich Kollisionen auf?

Ja. Ich habe angefangen, mein Testprogramm zu schreiben, um festzustellen, ob Hash-Kollisionen tatsächlich auftreten – und nicht nur ein theoretisches Konstrukt sind.Sie treten tatsächlich auf:

FNV-1-Kollisionen

• creamwove kollidiert mit quists

FNV -1a Kollisionen

• costarring kollidiert mit liquid
• declinate kollidiert mit macallums
• altarage kollidiert mit zinke
• altarages kollidiert mit zinkes

Murmel2-Kollisionen

• cataract kollidiert mit periti
• roquette kollidiert mit skivie
• shawl kollidiert mit stormbound
• dowlases kollidiert mit tramontane
• cricketings kollidiert mit twanger
• longans kollidiert mit whigs

DJB2-Kollisionen

• hetairas kollidiert mit mentioner
• heliotropes kollidiert mit neurospora
• depravement kollidiert mit serafins
• stylist kollidiert mit subgenera
• joyful kollidiert mit synaphea
• redescribed kollidiert mit urites
• dram kollidiert mit vivency

DJB2a-Kollisionen

• haggadot kollidiert mit loathsomenesses
• adorablenesses kollidiert mit rentability
• playwright kollidiert mit snush
• playwrighting kollidiert mit snushing
• treponematoses kollidiert mit waterbeds

CRC32-Kollisionen

• codding kollidiert mit gnu
• exhibiters kollidiert mit schlager

SuperFastHash-Kollisionen

• dahabiah kollidiert mit drapability
• encharm kollidiert mit enclave
• grahams kollidiert mit gramary
• … schnitt 79 Kollisionen ab …
• night kollidiert mit vigil
• kollidiert mit vigils
• finks kollidiert mit vinic

Randomnessification

Das andere subjektive Maß ist die zufällige Verteilung der Hashes. Die Zuordnung der resultierenden HashTables zeigt, wie gleichmäßig die Daten verteilt sind. Alle Hash-Funktionen zeigen eine gute Verteilung, wenn die Tabelle linear zugeordnet wird:

Oder als Hilbert Map ( XKCD ist immer relevant ):

Außer beim Hashing von Zahlenfolgen ("1", , …, "216553") (z. B. Postleitzahlen ), wo Muster beginnen in den meisten Hashing-Algorithmen:

SDBM :

DJB2a :

FNV-1 :

Alle außer

Wenn Sie eine Hash-Map aus einem unveränderlichen Wörterbuch erstellen möchten, sollten Sie ein perfektes Hashing in Betracht ziehen. https://en.wikipedia.org/wiki/Perfect_hash_function – Während der Erstellung der Hash-Funktion und der Hash-Tabelle können Sie für einen bestimmten Datensatz garantieren, dass keine Kollisionen auftreten.

Kommentare

• Hier ‚ erfahren Sie mehr über (minimales) perfektes Hashing burtleburtle.net/bob/hash/perfect.html einschließlich Leistungsdaten, obwohl ‚ nicht den aktuellsten Prozessor usw. verwendet.
• ‚ ist ziemlich offensichtlich, aber es sollte darauf hingewiesen werden, dass die Schlüssel dieselbe Größe wie die Werte haben müssen, um keine Kollisionen zu gewährleisten, es sei denn, th Es gibt Einschränkungen für die Werte, die der Algorithmus nutzen kann.
• @ devios1 Ihre Aussage ist bedeutungslos. Erstens sind die Werte in einer Hash-Tabelle, ob perfekt oder nicht, unabhängig von den Schlüsseln. Zweitens ist eine perfekte Hash-Tabelle nur ein lineares Array von Werten, das durch das Ergebnis der Funktion indiziert wird, die so erstellt wurde, dass alle Indizes eindeutig sind.
• @MarcusJ Perfektes Hash wird normalerweise mit weniger als 100 verwendet Schlüssel, aber werfen Sie einen Blick auf cmph.sourceforge.net … immer noch weit außerhalb Ihrer Reichweite.
• @DavidCary Nichts bei Ihnen Link unterstützt Ihren Anspruch. Möglicherweise haben Sie O (1) mit “ keine Kollisionen “ verwechselt, aber sie sind nicht ‚ überhaupt nicht dasselbe. Natürlich garantiert perfektes Hashing keine Kollisionen, aber es erfordert, dass alle Schlüssel im Voraus bekannt sind und dass es relativ wenige davon gibt. (Siehe jedoch den Link zu cmph oben.)

Hier ist eine Liste von Hash-Funktionen, aber die Kurzversion lautet:

Wenn Sie nur eine gute Hash-Funktion haben möchten und kann es kaum erwarten, djb2 ist eine der besten String-Hash-Funktionen, die ich kenne. Es verfügt über eine hervorragende Verteilung und Geschwindigkeit auf vielen verschiedenen Sätzen von Schlüsseln und Tabellengrößen.

unsigned long hash(unsigned char *str) { unsigned long hash = 5381; int c; while (c = *str++) hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ return hash; } 

Kommentare

• Tatsächlich ist djb2 wie die meisten einfachen Hash-Funktionen nullempfindlich, sodass Sie solche Hashes leicht brechen können.Es hat eine schlechte Tendenz zu viele Kollisionen und eine schlechte Verteilung, es bricht bei den meisten smhasher-Qualitätstests: Siehe github.com/rurban/smhasher/blob/master/doc/bernstein Seine CDB-Datenbank verwendet es, aber ich würde es nicht ‚ mit öffentlichem Zugriff verwenden.
• DJB ist vom Standpunkt der Leistung und Verteilung ziemlich schlecht. Ich würde ‚ es heute nicht verwenden.
• @ConradMeyer Ich ‚ würde wetten, dass DJB durch beschleunigt werden kann ein Faktor von drei, genau wie in dieser Frage von mir und dann ‚ wahrscheinlich die meisten verwendbaren Algorithmen schlagen würde. In Bezug auf die Verteilung stimme ich zu. Ein Hash, der selbst für zwei Buchstabenketten Kollisionen erzeugt, kann ‚ nicht wirklich gut sein.
• Leute, ich habe Zweifel. Sie sagen, djb2 ist schlecht, aber die Testergebnisse der akzeptierten Antwort zeigen, dass es gut ist.
• Sie könnten zumindest eine sinnvolle Primzahl verwenden, die weniger Kollisionen erzeugt statt 33. stackoverflow.com/a/2816747/21499

CityHash von Google ist der gesuchte Algorithmus. Es ist nicht gut für die Kryptografie, aber gut für die Erzeugung eindeutiger Hashes.

Lesen Sie den Blog für weitere Details und den Blog Code ist hier verfügbar .

CityHash ist in C ++ geschrieben. Es gibt auch einen einfachen C-Port .

Informationen zur 32-Bit-Unterstützung:

Alle CityHash-Funktionen sind für 64-Bit-Prozessoren optimiert. Das heißt, sie werden (mit Ausnahme der neuen, die SSE4.2 verwenden) in 32-Bit-Code ausgeführt. Sie werden jedoch nicht sehr schnell sein. Möglicherweise möchten Sie Murmeln oder etwas anderes in 32-Bit-Code verwenden.

Kommentare

• Wird CityHash ähnlich wie “ City Sushi ausgesprochen? “
• Haben Sie eine Schauen Sie sich auch SipHash an, es soll MurmurHash / CityHash / etc ersetzen. 131002.net/siphash
• Siehe auch FarmHash, a Nachfolger von CitHash. code.google.com/p/farmhash
• xxHash behauptet, 5x schneller als CityHash zu sein.
• plain C port Link ist unterbrochen

Ich habe einen kurzen Geschwindigkeitsvergleich verschiedener Hashing-Algorithmen beim Hashing von Dateien erstellt.

Die einzelnen Diagramme unterscheiden sich nur geringfügig in der Lesemethode und können hier ignoriert werden, da alle Dateien in einem tmpfs gespeichert wurden. Daher war der Benchmark nicht an E / A gebunden, wenn Sie sich fragen.

• Lineare Skala
• Logarithmische Skala

Zu den Algorithmen gehören: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Schlussfolgerungen:

• Nicht kryptografische Hash-Funktionen wie Murmur3, Cityhash und Spooky liegen ziemlich nahe beieinander. Man sollte beachten, dass Cityhash auf CPUs mit SSE 4.2s CRC -Anweisung, die meine CPU nicht hat, möglicherweise schneller ist. SpookyHash war in meinem Fall immer ein kleines bisschen vor CityHash.
• MD5 scheint ein guter Kompromiss bei der Verwendung kryptografischer Hash-Funktionen zu sein, obwohl SHA256 für Kollisionsschwachstellen von MD5 und SHA1.
• Die Komplexität aller Algorithmen ist linear – was wirklich nicht überraschend ist, da sie blockweise arbeiten. (Ich wollte sehen, ob die Lesemethode einen Unterschied macht, damit Sie nur die Werte ganz rechts vergleichen können.)
• SHA256 war langsamer als SHA512.
• Ich habe die Zufälligkeit von nicht untersucht Die Hash-Funktionen. Aber hier ist ein guter Vergleich der Hash-Funktionen, die in der Antwort von Ian Boyds fehlen. Dies weist darauf hin, dass CityHash in Eckfällen einige Probleme hat.

Die für die Diagramme verwendete Quelle:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (Entschuldigung für den hässlichen Code)

Kommentare

• Das lineare Skalendiagramm schneidet die Beschriftung der y-Achse ab, die angibt, welche Menge gezeichnet wird. Ich denke, es wäre wahrscheinlich “ Zeit in Sekunden „, genau wie die logarithmische Skala. Es lohnt sich, ‚ zu beheben.

Ich weiß, dass es Dinge wie SHA-256 und dergleichen gibt, aber diese Algorithmen sind entworfen um sicher zu sein , was normalerweise bedeutet, dass sie langsamer sind als Algorithmen, die weniger eindeutig sind.

Die Annahme, dass kryptografische Hash-Funktionen eindeutiger sind, ist falsch und kann in der Praxis häufig als rückwärts gezeigt werden. In Wahrheit:

1. Kryptografische Hash-Funktionen sollten idealerweise nicht von zufälligen ;
2. Bei nicht kryptografischen Hash-Funktionen ist es jedoch wünschenswert, dass günstig mit wahrscheinlichen Eingaben interagiert.

Dies bedeutet, dass eine nicht kryptografische Hash-Funktion möglicherweise weniger Kollisionen aufweist als a kryptografischer Datensatz für „guten“ Datensatz – Datensätze, für die er entwickelt wurde.

Wir können dies anhand der Daten in Ian Boyds Antwort und ein wenig Mathematik demonstrieren: die Geburtstagsproblem . Die Formel für die erwartete Anzahl kollidierender Paare bei Auswahl von n Ganzzahlen aus der Menge [1, d] lautet wie folgt (aus Wikipedia):

n - d + d * ((d - 1) / d)^n 

Einstecken von n = 216.553 und d = 2 ^ 32 Wir erhalten ungefähr 5.5 erwartete Kollisionen . Ians Tests zeigen meistens Ergebnisse in dieser Nachbarschaft, aber mit einer dramatischen Ausnahme: Die meisten Funktionen haben keine Kollisionen in der Tests aufeinanderfolgender Zahlen. Die Wahrscheinlichkeit, 216.553 32-Bit-Zahlen zufällig auszuwählen und keine Kollisionen zu erhalten, liegt bei etwa 0,43%. Und das nur für eine Funktion – hier haben wir fünf verschiedene Hash-Funktionsfamilien mit Null Kollisionen!

Was wir hier also sehen, ist, dass die von Ian getesteten Hashes günstig mit dem Datensatz für fortlaufende Zahlen interagieren – dh sie verteilen sich minimal unterschiedlich Eingaben weiter als eine ideale kryptografische Hash-Funktion. (Randnotiz: Dies bedeutet, dass Ians grafische Einschätzung, dass FNV-1a und MurmurHash2 für ihn im Zahlendatensatz „zufällig“ aussehen, aus seinen eigenen Daten widerlegt werden kann. Keine Kollisionen mit einem Datensatz dieser Größe für beide Hash-Funktionen sind auffallend nicht zufällig!)

Dies ist keine Überraschung, da dies ein wünschenswertes Verhalten für viele Verwendungen von Hash-Funktionen ist. Beispielsweise sind Hash-Tabellenschlüssel häufig sehr ähnlich. In Ians Antwort wird ein Problem erwähnt, das MSN einmal mit Postleitzahl-Hash-Tabellen hatte . Dies ist eine Verwendung, bei der die Kollisionsvermeidung bei wahrscheinlichen Eingaben das zufällige Verhalten gewinnt.

Ein weiterer lehrreicher Vergleich ist der Kontrast in den Entwurfszielen zwischen CRC- und kryptografischen Hash-Funktionen:

• CRC wurde entwickelt, um Fehler abzufangen, die aus verrauschten Kommunikationskanälen resultieren eine kleine Anzahl von Bit-Flips;
• Crypto-Hashes sind so konzipiert, dass sie Änderungen abfangen, die von böswilligen Angreifern vorgenommen wurden , denen begrenzte Rechenressourcen, aber willkürlich viel Klugheit zugewiesen werden.

Für CRC ist es also wieder gut , bei minimal unterschiedlichen Eingaben weniger Kollisionen als zufällig zu haben. Bei Krypto-Hashes ist dies ein Nein-Nein!

Die SHA-Algorithmen (einschließlich SHA-256) sind hat so konzipiert, dass es schnell ist

Tatsächlich kann ihre Geschwindigkeit manchmal ein Problem sein. Insbesondere besteht eine übliche Technik zum Speichern eines von einem Passwort abgeleiteten Tokens darin, einen Standard-Fast-Hash-Algorithmus 10.000 Mal auszuführen (Speichern des Hash des Hash des Hash des Hash des … Passworts).

#!/usr/bin/env ruby require "securerandom" require "digest" require "benchmark" def run_random_digest(digest, count) v = SecureRandom.random_bytes(digest.block_length) count.times { v = digest.digest(v) } v end Benchmark.bmbm do |x| x.report { run_random_digest(Digest::SHA256.new, 1_000_000) } end 

Ausgabe:

Rehearsal ------------------------------------ 1.480000 0.000000 1.480000 ( 1.391229) --------------------------- total: 1.480000sec user system total real 1.400000 0.000000 1.400000 ( 1.382016) 

Kommentare

• ‚ ist relativ schnell, sicher, für einen kryptografischen Hashing-Algorithmus . Aber das OP möchte nur Werte in einer Hashtabelle speichern, und ich glaube nicht, dass eine kryptografische Hash-Funktion dafür wirklich geeignet ist.
• Die aufgeworfene Frage (tangential erscheint es jetzt) das Thema der kryptografischen Hash-Funktionen. Das ‚ ist das Bit, auf das ich antworte.
• Nur um die Leute von der Idee von “ abzuhalten Eine übliche Technik zum Speichern eines von einem Passwort abgeleiteten Tokens besteht darin, einen Standard-Fast-Hash-Algorithmus 10.000 Mal “ auszuführen – während dies üblich ist, ist ‚ ist einfach nur dumm. Es gibt Algorithmen, die für diese Szenarien entwickelt wurden, z. B. bcrypt. Verwenden Sie die richtigen Tools.
• Kryptografische Hashes sind für einen hohen Durchsatz ausgelegt. Dies bedeutet jedoch häufig, dass sie einen hohen Einrichtungs-, Abbau-, .rodata und / oder staatliche Kosten aufweisen .Wenn Sie einen Algorithmus für eine Hashtabelle wünschen, haben Sie normalerweise sehr kurze Schlüssel und viele davon, benötigen jedoch nicht die zusätzlichen Garantien eines kryptografischen Schlüssels. Ich verwende selbst einen optimierten Jenkins-Effekt.
• @ChrisMorgan: Anstatt einen kryptografisch sicheren Hash zu verwenden, kann HashTable DoS mithilfe der Hash-Randomisierung viel effizienter gelöst werden, sodass jeder Lauf von die Programme oder sogar auf jeder Hashtabelle, damit die Daten nicht ‚ jedes Mal in demselben Bucket gruppiert werden.

Verwenden Sie SipHash . Es hat viele wünschenswerte Eigenschaften:

• Schnell. Eine optimierte Implementierung dauert ungefähr 1 Zyklus pro Byte.

• Sicher. SipHash ist eine starke PRF (Pseudozufallsfunktion). Dies bedeutet, dass es nicht von einer Zufallsfunktion zu unterscheiden ist (es sei denn, Sie kennen den 128-Bit-Geheimschlüssel). Daher:

  • Sie müssen sich keine Sorgen machen, dass Ihre Hash-Tabellensonden aufgrund von Kollisionen zu einer linearen Zeit werden. Mit SipHash wissen Sie , dass Sie unabhängig von den Eingaben im Durchschnitt eine durchschnittliche Fallleistung erzielen.

  • Immunität gegen Hash-basierte Denial-of-Service-Angriffe.

  • Sie können SipHash (insbesondere die Version mit 128-Bit-Ausgabe) als MAC verwenden (Nachrichtenauthentifizierungscode). Wenn Sie eine Nachricht und ein SipHash-Tag erhalten und das Tag mit dem aus dem Ausführen von SipHash mit Ihrem geheimen Schlüssel identisch ist, wissen Sie, dass derjenige, der den Hash erstellt hat, auch im Besitz Ihres geheimen Schlüssels war und dass weder die Nachricht noch der Der Hash wurde seitdem geändert.

Kommentare

• Isn ‚ t SipHash-Overkill, es sei denn, Sie benötigen Sicherheit? Benötigt einen 128-Bit-Schlüssel, der nur ein verherrlichter Hash-Samen ist. Ganz zu schweigen von MurmurHash3 mit 128-Bit-Ausgabe und SipHash nur mit 64-Bit-Ausgabe. Offensichtlich hat der größere Digest eine geringere Kollisionswahrscheinlichkeit.
• @bryc Der Unterschied besteht darin, dass sich SipHash auch bei böswilligen Eingaben weiterhin gut benimmt. Eine auf SipHash basierende Hash-Tabelle kann für Daten aus potenziell feindlichen Quellen verwendet werden und einen Algorithmus wie die lineare Prüfung verwenden, der sehr empfindlich auf die Details der Hash-Funktion reagiert.
• Siphash (und verwandte neuere prng Stilfunktionen) ist meine Standardauswahl für Sicherheit. Für die Leistung ist xxhash schwer zu schlagen. Selbst in den Diskussionen hier gibt es im Internet unzählige schlechte Hashing-Ratschläge. Eine gute Leistung bei zufälligen oder halbzufälligen Eingaben ist bedeutungslos. Was ist die Worst-Case-Leistung mit Eingaben aus der realen Welt? Was ist das Ergebnis mit böswilligen Eingaben? Ihre Hash-Tabelle wird schließlich zu einem Angriffsvektor.

Dies hängt von den Daten ab, die Sie hashen. Einige Hashing-Vorgänge funktionieren besser mit bestimmten Daten wie Text. Einige Hashing-Algorithmen wurden speziell für bestimmte Daten entwickelt.

Paul Hsieh hat einmal schnellen Hash erstellt. Er listet Quellcode und Erklärungen auf. Aber es wurde schon geschlagen. 🙂

Java verwendet diese einfache Multiplikation -und-Add-Algorithmus:

Der Hash-Code für ein String-Objekt wird berechnet als

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

unter Verwendung von Int-Arithmetik, wobei s[i] das i ​ -te Zeichen der Zeichenfolge ist, n ist die Länge der Zeichenfolge, und ^ gibt die Potenzierung an. (Der Hash-Wert der leeren Zeichenfolge ist Null.)

Es gibt wahrscheinlich viel bessere, aber dies ist ziemlich weit verbreitet und scheint gut zu sein Kompromiss zwischen Geschwindigkeit und Einzigartigkeit.

Kommentare

• Ich würde ‚ nicht genau dasselbe verwenden eine, die hier verwendet wird, da es ‚ immer noch relativ leicht ist, Kollisionen damit zu erzeugen. Es ‚ ist definitiv nicht schrecklich, aber es gibt viel bessere da draußen. Und wenn es ‚ keinen wesentlichen Grund gibt, mit Java kompatibel zu sein, sollte nicht ausgewählt werden.
• Wenn Sie dies immer noch auswählen Aus irgendeinem Grund könnte man zumindest eine bessere Primzahl wie 92821 als Multiplikator verwenden. Das reduziert Kollisionen erheblich. stackoverflow.com/a/2816747/21499
• Sie können stattdessen auch FNV1a verwenden. ‚ ist ebenfalls ein einfacher multiplikationsbasierter Hash, verwendet jedoch einen größeren Multiplikator, der den Hash besser verteilt.
• Sie verwenden nicht ‚ möchte s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3] nicht ausführen. Vermeiden Sie den Energieversorger (^) und gehen Sie folgendermaßen vor: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Ja, in dem Code, der iterativ ausgeführt wird (und ausgeführt werden sollte), war es in einer geschlossenen Formel nur einfacher zu verstehen.

Warum müssen Sie zunächst Ihr eigenes Hashing implementieren? Für die meisten Aufgaben sollten Sie mit Datenstrukturen aus einer Standardbibliothek gute Ergebnisse erzielen, vorausgesetzt, es ist eine Implementierung verfügbar (es sei denn, Sie tun dies nur für Ihre eigene Ausbildung).

Mein persönlicher Favorit ist FNV. 1

Hier ist eine Beispielimplementierung der 32-Bit-Version in C:

unsigned long int FNV_hash(void* dataToHash, unsigned long int length) { unsigned char* p = (unsigned char *) dataToHash; unsigned long int h = 2166136261UL; unsigned long int i; for(i = 0; i < length; i++) h = (h * 16777619) ^ p[i] ; return h; } 

Kommentare

• Die FNV-1a-Variante ist mit Zufälligkeit etwas besser. Tauschen Sie die Reihenfolge der * und ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619