it-swarm-eu.dev

Welcher Hashing-Algorithmus eignet sich am besten für Eindeutigkeit und Geschwindigkeit?

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.

algorithmssecurityperformancehashingunique-data
1444
Earlz

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

Ich habe drei verschiedene Schlüsselsätze verwendet:

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

Ich habe getestet:

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 :

Treten tatsächlich Kollisionen auf?

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
  • ... 79 Kollisionen abschneiden ...
  • night kollidiert mit vigil
  • nights kollidiert mit vigils
  • finks kollidiert mit vinic

Zufälligkeit

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:

Enter image description here

Oder als Hilbert Map ( XKCD ist immer relevant ):

Enter image description here

Außer beim Hashing von Zahlenfolgen ("1", "2", ..., "216553") (Zum Beispiel Postleitzahlen ) , wo in den meisten Hashing-Algorithmen Muster auftauchen:

[~ # ~] sdbm [~ # ~] :

Enter image description here

DJB2a :

Enter image description here

FNV-1 :

Enter image description here

Alle außer FNV-1a , die für mich immer noch ziemlich zufällig aussehen:

Enter image description here

Tatsächlich scheint Murmur2 mit Numbers eine noch bessere Zufälligkeit zu haben als FNV-1a:

Enter image description here

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.

FNV-1a-Algorithmus

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.

FNV-1 besser als FNV-1a?

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:

  • Kollisionen selten : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
  • häufige Kollisionen : SuperFastHash, Loselose

Und dann ist da noch, wie gleichmäßig die Hashes verteilt sind:

  • hervorragende Verteilung: Murmur2, FNV-1a, SuperFastHas
  • ausgezeichnete Verteilung: FNV-1
  • gute Verteilung: SDBM, DJB2, DJB2a
  • schreckliche Verteilung: Loselose

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:

  • Schneller
  • Besser Zufälligkeit aller Eingabeklassen

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

GUIDs sind eindeutig und nicht zufällig

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.

Alle englischen Wörter spiegeln

2530
Ian Boyd

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.

61
Damien

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;
}
34
Dean Harding

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 .

Über 32-Bit-Unterstützung :

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.

29
Vipin Parakkat

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:

  • 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, schneller sein kann. SpookyHash war in meinem Fall immer ein kleines bisschen vor CityHash.
  • MD5 scheint ein guter Kompromiss zu sein, wenn kryptografische Hash-Funktionen verwendet werden, obwohl SHA256 möglicherweise sicherer für die Kollisionsschwachstellen von MD5 und SHA1 ist.
  • Die Komplexität aller Algorithmen ist linear - was nicht verwunderlich 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 der Hash-Funktionen nicht untersucht. Aber hier ist ein guter Vergleich der Hash-Funktionen, die in Ian Boyds Antwort fehlen . Dies weist darauf hin, dass CityHash in Eckfällen einige Probleme hat.

Die für die Diagramme verwendete Quelle:

21
Sahib

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)
18
yfeldblum

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:

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

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:

  • CRC wurde entwickelt, um Fehler abzufangen, die aus verrauschten Kommunikationskanälen resultieren, bei denen es sich wahrscheinlich um eine kleine Anzahl von Bitflips handelt.
  • Krypto-Hashes wurden entwickelt, um Änderungen zu erfassen, die von böswilligen Angreifern vorgenommen wurden, denen begrenzte Rechenressourcen, aber willkürlich viel Klugheit zugewiesen wurden.

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!

15
sacundim

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.

10
Demi

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. :) :)

9
user712092

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.

6
biziclop

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;
}
4
user17754