Was ist eine gute Hash-Funktion?

StackOverflow https://stackoverflow.com/questions/34595

Frage

Was ist eine gute Hash-Funktion?Ich habe in meinen Datenstrukturkursen am College viele Hash-Funktionen und Anwendungen gesehen, aber meistens habe ich 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)

wobei die Primzahl die Größe der Hash-Tabelle angibt.Ich verstehe, dass das eine ziemlich gute und schnelle Funktion zur Kollisionsvermeidung ist, aber wie kann ich eine bessere machen?Gibt es bessere Hash-Funktionen für Zeichenfolgenschlüssel im Vergleich zu Zifferntasten?

War es hilfreich?

Lösung

Für die Durchführung „normaler“ Hash-Tabellensuchen im Grunde jeder Art von Daten – dieses von Paul Hsieh ist das Beste, das ich je verwendet habe.

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

Wenn Ihnen kryptografische Sicherheit oder etwas anderes Fortgeschritteneres am Herzen liegt, dann ist YMMV genau das Richtige für Sie.Wenn Sie einfach nur eine erstklassige Allzweck-Hash-Funktion für die Suche nach Hash-Tabellen benötigen, dann ist dies genau das Richtige für Sie.

Andere Tipps

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

Hash-Tabellen haben sehr unterschiedliche Anforderungen.Dennoch ist es schwierig, allgemein eine gute Hash-Funktion zu finden, da unterschiedliche Datentypen unterschiedliche Informationen offenlegen, die gehasht werden können.Als Faustregel gilt, dass es gut ist, darüber nachzudenken alle Informationen, die ein Typ gleichermaßen enthält.Dies ist nicht immer einfach oder überhaupt möglich.Aus Gründen der Statistik (und damit der Kollision) ist es außerdem wichtig, eine gute Streuung über den Problemraum zu erzeugen, d. h.alle möglichen Objekte.Das bedeutet, dass es beim Hashing von Zahlen zwischen 100 und 1050 nicht sinnvoll ist, die höchstwertige Ziffer eine große Rolle im Hash spielen zu lassen, da diese Ziffer bei etwa 90 % der Objekte 0 ist.Viel wichtiger ist es, den Hash von den letzten drei Ziffern bestimmen zu lassen.

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 empfehle, zu lesen, was Knuth zu sagen hat Die Kunst der Computerprogrammierung, Bd.3.Eine weitere gute Lektüre ist die von Julienne Walker Die Kunst des Hashing.

Es gibt zwei Hauptzwecke von Hashing-Funktionen:

  • um 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 man ihn verwendet.

Wenn Sie lediglich 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 hierfür völlig unnötig, Sie sollten besser a verwenden Variation von FNV.FNV erreicht eine bessere Streuung (und damit weniger Kollisionen) als ein einfacher Prime-Mod, wie Sie ihn erwähnt haben, und ist anpassungsfähiger an unterschiedliche Eingabegrößen.

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

Dies ist ein gutes Beispiel und auch ein Beispiel dafür, warum Sie niemals eines schreiben möchten.Es handelt sich um einen Fowler/Noll/Vo (FNV)-Hash, der zu gleichen Teilen Informatikgenie und puren 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 seine Seite der 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.

Ich würde sagen, dass die wichtigste Faustregel darin besteht, nicht selbst zu würfeln.Versuchen Sie, etwas zu verwenden, das gründlich getestet wurde, z. B. SHA-1 oder etwas in dieser Richtung.

Eine gute Hash-Funktion hat die folgenden Eigenschaften:

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

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

Die beiden Fälle sind nicht das gleiche.Im ersten Fall gibt es einen bereits vorhandenen Hash, für den Sie eine Kollision finden möchten.Im zweiten Fall versuchen Sie zu finden beliebig zwei Botschaften, die kollidieren.Die zweite Aufgabe ist aufgrund des Geburtstagsparadoxons deutlich einfacher.

Wenn die Leistung keine so große Rolle spielt, sollten Sie immer eine sichere Hash-Funktion verwenden.Es gibt sehr clevere Angriffe, die durch das Erzwingen von Kollisionen in einem Hash ausgeführt werden können.Wer von Anfang an etwas Starkes nutzt, sichert sich dagegen ab.

Verwenden Sie MD5 oder SHA-1 nicht in neuen Designs.Die meisten Kryptographen, mich eingeschlossen, würden sie für kaputt halten.Die Hauptursache für die Schwäche dieser beiden Konstruktionen besteht darin, dass die zweite Eigenschaft, die ich oben dargelegt habe, für diese Konstruktionen nicht gilt.Wenn ein Angreifer zwei Nachrichten generieren kann, m und m', die beide auf denselben Wert hashen, kann er diese Nachrichten gegen Sie verwenden.SHA-1 und MD5 leiden auch unter Nachrichtenerweiterungsangriffen, die Ihre Anwendung fatal schwächen können, wenn Sie nicht vorsichtig sind.

Ein modernerer Hash wie Whirpool ist die bessere Wahl.Es leidet nicht unter diesen Message-Extension-Angriffen und verwendet dieselben mathematischen Methoden wie AES, um die Sicherheit gegen eine Vielzahl von Angriffen nachzuweisen.

Hoffentlich hilft das!

Was Sie hier sagen, ist, dass Sie eines haben möchten, das kollisionssicher ist.Versuchen Sie es mit SHA-2.Oder versuchen Sie es mit einer (guten) Blockverschlüsselung in einer Einwegkomprimierungsfunktion (das habe ich noch nie zuvor versucht), wie AES im Miyaguchi-Preenel-Modus.Das Problem dabei ist, dass Sie Folgendes tun müssen:

1) eine Infusion haben.Versuchen Sie es mit den ersten 256 Bits der Bruchteile der Chinchin-Konstante oder so ähnlich.2) ein Polsterschema haben.Einfach.Barrow es von einem Hash wie MD5 oder SHA-3 (Keccak [ausgesprochen „ket-chak“)).Wenn Ihnen die Sicherheit egal ist (ein paar andere haben das gesagt), schauen Sie sich FNV oder Lookup2 von Bob Jenkins an (eigentlich bin ich der Erste, der Lookup2 empfiehlt). Probieren Sie auch MurmurHash aus, es ist schnell (sehen Sie sich das an:.16 cpb).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top