Welcher Hashing-Algorithmus eignet sich am besten für Eindeutigkeit und Geschwindigkeit? Beispiel (gute) Verwendungen umfassen Hash-Wörterbücher.
Ich weiß, dass es Dinge wie SHA-256 und dergleichen gibt, aber diese Algorithmen sind so konzipiert , dass sie sicher sind , was normalerweise bedeutet, dass sie langsamer sind als Algorithmen, die weniger einzigartig sind. Ich möchte einen Hash-Algorithmus, der schnell ausgelegt ist und dennoch ziemlich einzigartig bleibt, um Kollisionen zu vermeiden.
Ich habe verschiedene Algorithmen getestet, um die Geschwindigkeit und die Anzahl der Kollisionen zu messen.
Ich habe drei verschiedene Schlüsselsätze verwendet:
"1"
Bis "216553"
(Denken Sie an Postleitzahlen und , wie ein schlechter Hash msn.com heruntergefahren hat ???? archive)Für jeden Korpus wurden die Anzahl der Kollisionen und die durchschnittliche Zeit für das Hashing aufgezeichnet.
Ich habe getestet:
xor
anstelle von +
)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 :
Ja. Ich habe angefangen, mein Testprogramm zu schreiben, um zu sehen, ob Hash-Kollisionen tatsächlich auftreten - und sind nicht nur ein theoretisches Konstrukt. Sie passieren tatsächlich:
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
night
kollidiert mit vigil
nights
kollidiert mit vigils
finks
kollidiert mit vinic
Das andere subjektive Maß ist, wie zufällig die Hashes verteilt sind. 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"
, "2"
, ..., "216553"
) (Zum Beispiel Postleitzahlen ) , wo in den meisten Hashing-Algorithmen Muster auftauchen:
[~ # ~] sdbm [~ # ~] :
DJB2a :
FNV-1 :
Alle außer FNV-1a , die für mich immer noch ziemlich zufällig aussehen:
Tatsächlich scheint Murmur2 mit Numbers
eine noch bessere Zufälligkeit zu haben als FNV-1a
:
Wenn ich mir die
FNV-1a
"Zahlen" -Karte ansehe, denke ich , dass ich subtile vertikale Muster sehe. Mit Murmeln Ich sehe überhaupt keine Muster. Was denkst du?
Das Extra *
in der Tabelle gibt an, wie schlecht die Zufälligkeit ist. Mit FNV-1a
Als bestem und DJB2x
als schlechtestem:
Murmur2: .
FNV-1a: .
FNV-1: ▪
DJB2: ▪▪
DJB2a: ▪▪
SDBM: ▪▪▪
SuperFastHash: .
CRC: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
Loselose: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
▪
▪▪▪▪▪▪▪▪▪▪▪▪▪
▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
Ich habe dieses Programm ursprünglich geschrieben, um zu entscheiden, ob ich überhaupt Sorge über Kollisionen machen musste: das tue ich.
Und dann stellte sich heraus, dass die Hash-Funktionen ausreichend zufällig waren.
Der FNV1-Hash ist in Varianten erhältlich, die 32-, 64-, 128-, 256-, 512- und 1024-Bit-Hashes zurückgeben.
Der FNV-1a-Algorithmus lautet:
hash = FNV_offset_basis
for each octetOfData to be hashed
hash = hash xor octetOfData
hash = hash * FNV_prime
return hash
Wo die Konstanten FNV_offset_basis
Und FNV_prime
Von der gewünschten Rückgabe-Hash-Größe abhängen:
Hash Size
===========
32-bit
prime: 2^24 + 2^8 + 0x93 = 16777619
offset: 2166136261
64-bit
prime: 2^40 + 2^8 + 0xb3 = 1099511628211
offset: 14695981039346656037
128-bit
prime: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
offset: 144066263297769815596495629667062367629
256-bit
prime: 2^168 + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211
offset: 100029257958052580907070968620625704837092796014241193945225284501741471925557
512-bit
prime: 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759
offset: 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785
1024-bit
prime: 2^680 + 2^8 + 0x8d = 5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
offset: 1419779506494762106872207064140321832088062279544193396087847491461758272325229673230371772250864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915
Siehe der FNV-Hauptseite für Details.
Alle meine Ergebnisse sind mit der 32-Bit-Variante.
Nein, FNV-1a ist rundum besser. Bei Verwendung des englischen Wortkorpus gab es mehr Kollisionen mit FNV-1a:
Hash Word Collisions
====== ===============
FNV-1 1
FNV-1a 4
Vergleichen Sie nun Klein- und Großbuchstaben:
Hash lowercase Word Collisions UPPERCASE Word collisions
====== ========================= =========================
FNV-1 1 9
FNV-1a 4 11
In diesem Fall ist FNV-1a nicht "400%" schlechter als FN-1, nur 20% schlechter.
Ich denke, der wichtigere Aspekt ist, dass es bei Kollisionen zwei Klassen von Algorithmen gibt:
Und dann ist da noch, wie gleichmäßig die Hashes verteilt sind:
Update
Murmeln? Klar, warum nicht
Update
@whatshisname fragte sich, wie ein CRC32 funktionieren würde, und fügte der Tabelle Zahlen hinzu.
CRC32 ist ziemlich gut . Wenige Kollisionen, aber langsamer, und der Overhead einer 1k-Nachschlagetabelle.
Snip alle fehlerhaften Sachen über die CRC-Verteilung - mein schlechtes
Bis heute wollte ich FNV-1a als meinen de facto Hash-Table-Hashing-Algorithmus verwenden. Aber jetzt wechsle ich zu Murmur2:
Und ich hoffe wirklich, wirklich , dass etwas mit dem SuperFastHash
Algorithmus, den ich gefunden habe , nicht stimmt; Es ist schade, so beliebt zu sein wie es ist.
Update: Von der MurmurHash3-Homepage bei Google :
(1) - SuperFastHash hat sehr schlechte Kollisionseigenschaften, die an anderer Stelle dokumentiert wurden.
Ich denke, es ist nicht nur ich.
Update: Mir wurde klar, warum Murmur
schneller ist als die anderen. MurmurHash2 arbeitet mit jeweils vier Bytes. Die meisten Algorithmen sind Byte für Byte :
for each octet in Key
AddTheOctetToTheHash
Dies bedeutet, dass Murmur mit zunehmender Länge die Chance bekommt, zu glänzen.
Update
Ein zeitgemäßer Beitrag von Raymond Chen bekräftigt die Tatsache, dass "random" GUIDs nicht für ihre Zufälligkeit verwendet werden sollen. Sie oder eine Teilmenge davon sind als Hash-Schlüssel ungeeignet:
Selbst der Algorithmus der Version 4 GUID ist nicht unvorhersehbar, da der Algorithmus die Qualität des Zufallszahlengenerators nicht angibt. Der Wikipedia-Artikel für GUID enthält Primärrecherchen, die darauf hindeuten , dass zukünftige und frühere GUIDs basierend auf der Kenntnis des Zustands des Zufallszahlengenerators vorhergesagt werden können, da der Generator nicht kryptografisch stark ist.
Zufälligkeit ist nicht dasselbe wie Kollisionsvermeidung; Aus diesem Grund wäre es ein Fehler, einen eigenen "Hashing" -Algorithmus zu erfinden, indem Sie eine Teilmenge einer "zufälligen" Anleitung verwenden:
int HashKeyFromGuid(Guid type4uuid)
{
//A "4" is put somewhere in the GUID.
//I can't remember exactly where, but it doesn't matter for
//the illustrative purposes of this pseudocode
int guidVersion = ((type4uuid.D3 & 0x0f00) >> 8);
Assert(guidVersion == 4);
return (int)GetFirstFourBytesOfGuid(type4uuid);
}
Hinweis : Wiederum habe ich "random GUID" in Anführungszeichen gesetzt, da es sich um die "zufällige" Variante handelt von GUIDs. Eine genauere Beschreibung wäre Type 4 UUID
. Aber niemand weiß, was Typ 4 oder Typ 1, 3 und 5 sind. Es ist also einfacher, sie als "zufällige" GUIDs zu bezeichnen.
Wenn Sie eine Hash-Map aus einem unveränderlichen Wörterbuch erstellen möchten, sollten Sie das perfekte Hashing in Betracht ziehen https://en.wikipedia.org/wiki/Perfect_hash_function - während der Erstellung der Hash-Funktion und In der Hash-Tabelle können Sie für einen bestimmten Datensatz garantieren, dass keine Kollisionen auftreten.
hier ist eine Liste von Hash-Funktionen, aber die Kurzversion lautet:
Wenn Sie nur eine gute Hash-Funktion haben möchten und nicht warten können,
djb2
ist eine der besten String-Hash-Funktionen, die ich kenne. Es verfügt über eine hervorragende Verteilung und Geschwindigkeit auf vielen verschiedenen Schlüsselsätzen und Tischgröß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;
}
CityHash von Google ist der Algorithmus, den Sie suchen. Es ist nicht gut für die Kryptographie, aber gut für die Erzeugung eindeutiger Hashes.
Lesen Sie das Blog für weitere Details und das Code ist hier verfügbar .
CityHash ist in C++ geschrieben. Es gibt auch einen einfachen C-Port .
Alle CityHash-Funktionen sind auf 64-Bit-Prozessoren abgestimmt. 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.
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.
Algorithmen umfassen: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}
.
Schlussfolgerungen:
CRC
Anweisung, die meine CPU nicht hat, schneller sein kann. SpookyHash war in meinem Fall immer ein kleines bisschen vor CityHash.Die für die Diagramme verwendete Quelle:
Die SHA - Algorithmen (einschließlich SHA-256) sind entworfen um schnell zu sein.
In der Tat 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)
Ich weiß, dass es Dinge wie SHA-256 und dergleichen gibt, aber diese Algorithmen sind so konzipiert , dass sie sicher sind , was normalerweise bedeutet, dass sie langsamer sind als Algorithmen, die weniger einzigartig sind.
Die Annahme, dass kryptografische Hash-Funktionen eindeutiger sind, ist falsch, und tatsächlich kann gezeigt werden, dass sie in der Praxis häufig rückwärts sind. In Wahrheit:
Dies bedeutet, dass eine nicht kryptografische Hash-Funktion möglicherweise weniger Kollisionen aufweist als eine kryptografische für "gute" Datensätze - Datensätze, für die sie entwickelt wurde .
Wir können dies tatsächlich anhand der Daten in Ian Boyds Antwort und ein bisschen Mathematik demonstrieren: das Geburtstagsproblem . Die Formel für die erwartete Anzahl kollidierender Paare, wenn Sie zufällig n
Ganzzahlen aus der Menge [1, d]
Auswählen, lautet wie folgt (aus Wikipedia):
n - d + d * ((d - 1) / d)^n
Wenn wir n
= 216.553 und d
= 2 ^ 32 einstecken, erhalten wir ungefähr 5.5 erwartete Kollisionen . Ians Tests zeigen meistens Ergebnisse in dieser Nachbarschaft, aber mit einer dramatischen Ausnahme: Die meisten Funktionen haben in den aufeinanderfolgenden Zahlentests keine Kollisionen . Die Wahrscheinlichkeit, 216.553 32-Bit-Zahlen zufällig auszuwählen und keine Kollisionen zu erhalten, liegt bei etwa 0,43%. Und das ist nur für eine Funktion - hier haben wir fünf verschiedene Hash-Funktionsfamilien ohne Kollisionen!
Was wir hier sehen, ist, dass die von Ian getesteten Hashes günstig mit dem Datensatz für fortlaufende Zahlen interagieren - dh sie verteilen minimal unterschiedliche 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 beides Hash-Funktionen, ist 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. Ians Antwort erwähnt ein Problem, das MSN einmal mit Postleitzahl-Hash-Tabellen hatte . Dies ist eine Verwendung, bei der Kollisionsvermeidung bei wahrscheinlich Eingaben über zufälliges Verhalten gewinnt.
Ein weiterer lehrreicher Vergleich ist der Kontrast in den Entwurfszielen zwischen CRC- und kryptografischen Hash-Funktionen:
Für CRC ist es also wieder gut, weniger Kollisionen als zufällig in minimal unterschiedlichen Eingaben zu haben. Bei Krypto-Hashes ist dies ein Nein-Nein!
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 einer 128-Bit-Ausgabe) als MAC (Message Authentication Code) verwenden. 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 Hash wurde seitdem geändert.
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 Fast Hash gemacht. Er listet Quellcode und Erklärungen auf. Aber es wurde schon geschlagen. :) :)
Java verwendet this einfachen Multiplikations- und Additionsalgorithmus:
Der Hash-Code für ein String-Objekt wird als berechnet
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
mit int arithmetik, wobei
s[i]
ist das i -te Zeichen der Zeichenfolge,n
ist die Länge der Zeichenfolge und^
zeigt Potenzierung an. (Der Hashwert der leeren Zeichenfolge ist Null.)
Es gibt wahrscheinlich viel bessere, aber dies ist ziemlich weit verbreitet und scheint ein guter Kompromiss zwischen Geschwindigkeit und Einzigartigkeit zu sein.
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;
}