Was ist eine gute Hash-Funktion?

130

Was ist eine gute Hash-Funktion? Ich habe in meinen Datenstrukturkursen im College viele Hash-Funktionen und Anwendungen gesehen, aber ich habe meistens festgestellt, dass es ziemlich schwierig ist, eine gute Hash-Funktion zu erstellen. Als Faustregel zur Vermeidung von Kollisionen sagte mein Professor:

function Hash(key)
  return key mod PrimeNumber
end

(mod ist der% -Operator in C und ähnlichen Sprachen)

Die Primzahl entspricht der Größe der Hash-Tabelle. Ich verstehe, dass dies eine etwas gute Funktion ist, um Kollisionen zu vermeiden, und eine schnelle, aber wie kann ich eine bessere machen? Gibt es bessere Hash-Funktionen für String-Tasten gegen Zifferntasten?

Hoffmann
quelle
34
Haben Sie darüber nachgedacht, eine oder mehrere der folgenden allgemeinen Hash-Funktionen zu verwenden: partow.net/programming/hashfunctions/index.html
In fnv_func ist der Typ von p [i] char. Was passiert mit h nach der ersten Iteration? Wurde es absichtlich gemacht?
5
@martinatime sagte: Es gibt eine Reihe von Informationen zu Hash-Funktionen in Wikipedia en.wikipedia.org/wiki/Hash_function und am Ende dieses Artikels hat partow.net/programming/hashfunctions/index.html Algorithmen in verschiedenen Sprachen implementiert.
2501

Antworten:

33

Für die "normale" Suche nach Hash-Tabellen für praktisch alle Arten von Daten - diese von Paul Hsieh ist die beste, die ich je verwendet habe.

http://www.azillionmonkeys.com/qed/hash.html

Wenn Sie sich für kryptografisch sichere oder etwas fortgeschritteneres interessieren, dann YMMV. Wenn Sie nur eine Kick-Ass-Universal-Hash-Funktion für eine Hash-Tabellensuche wünschen, dann ist dies das, wonach Sie suchen.

Chris Harris
quelle
Danke für den informativen Link! Ich kenne einige Analysen von Bob Jenkins und anderen, die auf recht gute, allgemein akzeptable Hash-Funktionen hinweisen, aber ich bin noch nicht auf diese gestoßen.
Konrad Rudolph
Ich hatte von Jenkins 'Seite gelesen, dass SFH eine der besten ist, aber ich denke, Murmur könnte es besser machen, siehe diese ausgezeichnete Antwort: programmers.stackexchange.com/questions/49550/…
nawfal
2
Wofür steht YMMV?
Cobarzan
3
@ Cobarzan Ihre Laufleistung kann variieren
ProgrammerDan
2
Hsiehs Hash-Funktion ist schrecklich, mit einer Größenordnung mehr Kollisionen als wir wollen. Insbesondere Zeichenfolgen, die sich nur in den letzten 4 Bytes unterscheiden, können leicht kollidieren. Wenn Sie eine 30-stellige Zeichenfolge haben, die sich in den letzten 4 Bytes unterscheidet, nachdem 28 Bytes verarbeitet wurden, unterscheiden sich die Hashes nur in den letzten 2 Bytes. Das bedeutet, dass Sie eine Kollision für einen der verbleibenden Zwei-Byte-Werte GARANTIERT haben. (Ja, es ist schnell. Na und.)
Andrew Lazarus
51

Es gibt keine "gute Hash-Funktion" für universelle Hashes (Hrsg. Ja, ich weiß, es gibt so etwas wie "universelles Hashing", aber das habe ich nicht gemeint). Je nach Kontext bestimmen unterschiedliche Kriterien die Qualität eines Hash. Zwei Personen haben SHA bereits erwähnt. Dies ist ein kryptografischer Hash und überhaupt nicht gut für Hash-Tabellen, die Sie wahrscheinlich meinen.

Hash-Tabellen haben sehr unterschiedliche Anforderungen. Trotzdem ist es schwierig, eine gute Hash-Funktion allgemein zu finden, da unterschiedliche Datentypen unterschiedliche Informationen offenlegen, die gehasht werden können. Als Faustregel gilt, dass alle Informationen, die ein Typ enthält, gleichermaßen berücksichtigt werden. Dies ist nicht immer einfach oder sogar möglich. Aus Gründen der Statistik (und damit der Kollision) ist es auch wichtig, eine gute Verteilung über den Problemraum, dh alle möglichen Objekte, zu generieren. Dies bedeutet, dass es beim Hashing von Zahlen zwischen 100 und 1050 nicht gut ist, die höchstwertige Ziffer eine große Rolle im Hash spielen zu lassen, da diese Ziffer für ~ 90% der Objekte 0 ist. Es ist weitaus wichtiger, die letzten drei zu lassen Ziffern bestimmen den Hash.

Ebenso ist es beim Hashing von Zeichenfolgen wichtig, alle Zeichen zu berücksichtigen - es sei denn, es ist im Voraus bekannt, dass die ersten drei Zeichen aller Zeichenfolgen gleich sind. wenn man diese berücksichtigt, ist das eine Verschwendung.

Dies ist tatsächlich einer der Fälle, in denen ich rate, zu lesen, was Knuth in The Art of Computer Programming , vol. 3. Eine weitere gute Lektüre ist Julienne Walkers The Art of Hashing .

Konrad Rudolph
quelle
1
Konrad, Sie haben aus theoretischer Sicht sicherlich Recht, aber haben Sie jemals versucht, die Paul Hsieh-Hash-Funktion zu verwenden, die ich in meinem Kommentar erwähnt habe? Es ist wirklich ziemlich gut gegen viele verschiedene Arten von Daten!
Chris Harris
9

Es gibt zwei Hauptzwecke von Hashing-Funktionen:

  • Datenpunkte gleichmäßig in n Bits zu verteilen.
  • um die Eingabedaten sicher zu identifizieren.

Es ist unmöglich, einen Hash zu empfehlen, ohne zu wissen, wofür Sie ihn verwenden.

Wenn Sie nur eine Hash-Tabelle in einem Programm erstellen, müssen Sie sich keine Gedanken darüber machen, wie reversibel oder hackbar der Algorithmus ist ... SHA-1 oder AES sind dafür völlig unnötig. Verwenden Sie sie besser eine Variation von FNV . FNV erzielt eine bessere Streuung (und damit weniger Kollisionen) als ein einfacher Prime Mod, wie Sie bereits erwähnt haben, und ist anpassungsfähiger für unterschiedliche Eingangsgrößen.

Wenn Sie die Hashes verwenden, um öffentliche Informationen zu verbergen und zu authentifizieren (z. B. das Hashing eines Kennworts oder eines Dokuments), sollten Sie einen der wichtigsten Hashing-Algorithmen verwenden, die von der öffentlichen Kontrolle überprüft werden. Die Hash Function Lounge ist ein guter Anfang.

Myrddin Emrys
quelle
aktualisierter Link zur Hash Function Lounge: larc.usp.br/~pbarreto/hflounge.html
Tim Partridge
Wie gut hält FNV einer Geburtstagskollision stand, verglichen mit beispielsweise der gleichen Anzahl von Bits von einem SHA1?
Kevin Hsu
@ Kevin Solange die Lawinenmerkmale eines Hashs gut sind (winzige Änderungen der Eingabe = große Änderungen der Ausgabe), sind Geburtstagskollisionen einfach eine Funktion der Bits im Hash. FNV-1a ist in dieser Hinsicht ausgezeichnet, und Sie können so viele oder so wenige Bits im Hash haben, wie Sie möchten (obwohl es ein wenig zusätzlichen Aufwand erfordert, um eine Bitanzahl zu erhalten, die keine Zweierpotenz ist).
Myrddin Emrys
5

Dies ist ein Beispiel für ein gutes und auch ein Beispiel dafür, warum Sie niemals eines schreiben möchten. Es ist ein Fowler / Noll / Vo (FNV) Hash, der zu gleichen Teilen Genie der Informatik und reines Voodoo ist:

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

Bearbeiten:

  • Landon Curt Noll empfiehlt weiter seiner Website den FVN-1A-Algorithmus gegenüber dem ursprünglichen FVN-1-Algorithmus: Der verbesserte Algorithmus verteilt das letzte Byte im Hash besser. Ich habe den Algorithmus entsprechend angepasst.
Nick Van Brunt
quelle
3
Vielleicht möchten Sie auf dieser Website nach Informationen suchen, warum diese Werte ausgewählt werden: isthe.com/chongo/tech/comp/fnv/#fnv-prime
Cthutu
Gesundheit. Diese kurze, einfache, effiziente, generische und effektive 64-Bit-Hash-Funktion war genau das, was ich brauchte.
Mattarod
3

Ich würde sagen, dass die Hauptregel lautet, nicht selbst zu rollen. Versuchen Sie, etwas zu verwenden, das gründlich getestet wurde, z. B. SHA-1 oder ähnliches.

Einar
quelle
Er scheint nichts kryptografisch Sicheres zu brauchen, also wäre SHA-1 viel übertrieben.
Erik
Übrigens, obwohl keine Kollisionen für SHA-1 gefunden wurden, wird angenommen, dass es eine Frage von Jahren oder Monaten ist, bevor eine gefunden wird. Ich würde empfehlen, SHA-256 zu verwenden.
Samuel Allan
1

Eine gute Hash-Funktion hat folgende Eigenschaften:

  1. Bei einem Hash einer Nachricht ist es für einen Angreifer rechnerisch unmöglich, eine andere Nachricht so zu finden, dass ihre Hashes identisch sind.

  2. Bei einem Nachrichtenpaar m 'und m ist es rechnerisch nicht möglich, zwei zu finden, so dass h (m) = h (m')

Die beiden Fälle sind nicht gleich. Im ersten Fall gibt es einen bereits vorhandenen Hash, für den Sie eine Kollision suchen möchten. Im zweiten Fall versuchen Sie, zwei beliebige Nachrichten zu finden , die kollidieren. Die zweite Aufgabe ist aufgrund des "Paradoxons" zum Geburtstag erheblich einfacher.

Wenn die Leistung kein so großes Problem darstellt, sollten Sie immer eine sichere Hash-Funktion verwenden. Es gibt sehr clevere Angriffe, die ausgeführt werden können, indem Kollisionen in einem Hash erzwungen werden. Wenn Sie von Anfang an etwas Starkes verwenden, sichern Sie sich dagegen ab.

Verwenden Sie MD5 oder SHA-1 nicht in neuen Designs. Die meisten Kryptographen, ich eingeschlossen, würden sie als kaputt betrachten. Die Hauptschwäche bei diesen beiden Entwürfen besteht darin, dass die zweite Eigenschaft, die ich oben skizziert habe, für diese Konstruktionen nicht gilt. Wenn ein Angreifer zwei Nachrichten generieren kann, m und m ', die beide den gleichen Wert haben, können sie diese Nachrichten gegen Sie verwenden. SHA-1 und MD5 leiden auch unter Nachrichtenerweiterungsangriffen, die Ihre Anwendung tödlich schwächen können, wenn Sie nicht vorsichtig sind.

Ein moderner Hash wie Whirpool ist die bessere Wahl. Es leidet nicht unter diesen Nachrichtenerweiterungsangriffen und verwendet dieselbe Mathematik wie AES, um die Sicherheit gegen eine Vielzahl von Angriffen zu beweisen.

Hoffentlich hilft das!

Simon Johnson
quelle
1
Ich denke, die Empfehlung der kryptografischen Hash-Funktion ist in diesem Fall ein wirklich schlechter Rat.
Slava
@ Slava: Warum? Was sind Ihre Gründe zu sagen, dass eine "kryptografische Hash-Funktion in diesem Fall ein wirklich schlechter Rat ist?" Warum ist es ein schlechter Rat? Was sind die relativen Nachteile, die es so machen?
Lassen Sie mich darüber basteln
2
@Mowzer Da eine Hash-Funktion, die in der Hash-Map verwendet wird, schnell und leicht sein sollte (vorausgesetzt, sie liefert immer noch guten Hash), wurden Krypto-Hashes explizit als rechenintensiv eingestuft, um Brute-Force-Angriffe zu verhindern.
Slava
1

Was Sie hier sagen, ist, dass Sie eine haben möchten, die Kollisionsfestigkeit verwendet. Versuchen Sie es mit SHA-2. Oder versuchen Sie, eine (gute) Blockverschlüsselung in einer Einweg-Komprimierungsfunktion zu verwenden (das haben Sie noch nie zuvor versucht), wie AES im Miyaguchi-Preenel-Modus. Das Problem dabei ist, dass Sie:

1) eine IV haben müssen. Versuchen Sie, die ersten 256 Bits der Bruchteile der Khinchin-Konstante oder ähnliches zu verwenden. 2) ein Auffüllschema haben. Einfach. Barrow es aus einem Hash wie MD5 oder SHA-3 (Keccak [ausgesprochen 'Ket-Chak']). Wenn Sie sich nicht um die Sicherheit kümmern (einige andere sagten dies), schauen Sie sich FNV oder Lookup2 von Bob Jenkins an (eigentlich bin ich der erste, der Lookup2 empfiehlt). Versuchen Sie auch MurmurHash, es ist schnell (überprüfen Sie dies: .16 cpb ).

Gavriel Feria
quelle