zurückrechnen - Welche Ganzzahl-Hash-Funktion ist gut, die einen Integer-Hash-Schlüssel akzeptiert?




hashwert zurückrechnen (6)

Die Antwort hängt von vielen Dingen ab wie:

  • Wo wollen Sie es einsetzen?
  • Was versuchst du mit dem Hash zu machen?
  • Brauchen Sie eine kryptographisch sichere Hash-Funktion?

Ich schlage vor, dass Sie sich die Merkle-Damgard Familie von Hash-Funktionen wie SHA-1 usw. Merkle-Damgard

Welche Ganzzahl-Hash-Funktion ist gut, die einen Integer-Hash-Schlüssel akzeptiert?


Es gibt einen schönen Überblick über einige Hash-Algorithmen bei Eternally Confuzzled . Ich würde Bob Jenkins 'Single-at-Time-Hash empfehlen, der schnell eine Lawine erreicht und daher für eine effiziente Hashtabellen-Suche verwendet werden kann.


Ich fand, dass der folgende Algorithmus eine sehr gute statistische Verteilung bietet. Jedes Eingangsbit beeinflußt jedes Ausgangsbit mit ungefähr 50% Wahrscheinlichkeit. Es gibt keine Kollisionen (jede Eingabe führt zu einer anderen Ausgabe). Der Algorithmus ist schnell, außer wenn die CPU keine eingebaute Ganzzahl-Multiplikationseinheit besitzt. C-Code, unter der Annahme int ist 32 Bit (für Java, ersetzen >> mit >>> und entfernen unsigned ):

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

Die magische Zahl wurde mit einem speziellen, mehrere Stunden gelaufenen Multithread-Testprogramm berechnet, das den Lawineneffekt berechnet (die Anzahl der Ausgangsbits, die sich ändern, wenn ein einzelnes Eingangsbit geändert wird; im Durchschnitt fast 16), Unabhängigkeit von Ausgangsbitänderungen (Ausgangsbits sollten nicht voneinander abhängen) und die Wahrscheinlichkeit einer Änderung in jedem Ausgangsbit, wenn irgendein Eingangsbit geändert wird. Die berechneten Werte sind besser als der von MurmurHash verwendete 32-Bit-Finalizer und fast genauso gut (nicht ganz) wie bei der Verwendung von AES .

Sie können den Prozess umkehren (holen Sie den Eingabewert aus dem Hash), wenn Sie die 0x45d9f3b durch 0x119de1f3 (die multiplikative Umkehrung ) ersetzen:

unsigned int unhash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

Für 64-Bit-Nummern empfehle ich Folgendes zu verwenden, auch wenn es nicht unbedingt der schnellste ist. Dieser basiert auf splitmix64 , welches auf dem Blog-Artikel Better Bit Mixing (Mix 13) basiert.

uint64_t hash(uint64_t x) {
    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;
}

Für Java verwenden Sie long , fügen Sie L zur Konstante hinzu, ersetzen Sie >> durch >>> und entfernen Sie unsigned . In diesem Fall ist das Rückwärtsfahren komplizierter:

uint64_t unhash(uint64_t x) {
    x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3);
    x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089);
    x = x ^ (x >> 30) ^ (x >> 60);
    return x;
}

Ich glaube nicht, dass wir sagen können, dass eine Hash-Funktion "gut" ist, ohne Ihre Daten im Voraus zu kennen! und ohne zu wissen, was du damit machen willst.

Es gibt bessere Datenstrukturen als Hashtabellen für unbekannte Datengrößen (ich gehe davon aus, dass Sie hier das Hashing für eine Hash-Tabelle durchführen). Ich würde persönlich eine Hash-Tabelle verwenden, wenn ich weiß, dass ich eine "endliche" Anzahl von Elementen habe, die in einer begrenzten Menge an Speicher gespeichert werden müssen. Ich würde versuchen, eine schnelle statistische Analyse meiner Daten durchzuführen, um zu sehen, wie sie verteilt wird, bevor ich über meine Hash-Funktion nachdenke.


Diese Seite listet einige einfache Hash-Funktionen auf, die im Allgemeinen recht anständig sind, aber jeder einfache Hash hat pathologische Fälle, in denen er nicht gut funktioniert.


  • 32-Bit-Multiplikationsmethode (sehr schnell) siehe @rafal

    #define hash32(x) ((x)*2654435761)
    #define H_BITS 24 // Hashtable size
    #define H_SHIFT (32-H_BITS)
    unsigned hashtab[1<<H_BITS]  
    .... 
    unsigned slot = hash32(x) >> H_SHIFT
    
  • 32-Bit und 64-Bit (gute Verteilung) bei: MurmurHash

  • Ganzzahlige Hash-Funktion






hash