Welche Integer-Hash-Funktionen sind gut, die einen Integer-Hash-Schlüssel akzeptieren?

Antworten:

47

Knuths multiplikative Methode:

hash(i)=i*2654435761 mod 2^32

Im Allgemeinen sollten Sie einen Multiplikator auswählen, der in der Reihenfolge Ihrer Hash-Größe ( 2^32im Beispiel) liegt und keine gemeinsamen Faktoren aufweist. Auf diese Weise deckt die Hash-Funktion Ihren gesamten Hash-Bereich einheitlich ab.

Bearbeiten: Der größte Nachteil dieser Hash-Funktion besteht darin, dass die Teilbarkeit erhalten bleibt. Wenn Ihre Ganzzahlen also alle durch 2 oder 4 teilbar sind (was nicht ungewöhnlich ist), sind auch ihre Hashes teilbar. Dies ist ein Problem in Hash-Tabellen. Es kann vorkommen, dass nur 1/2 oder 1/4 der verwendeten Eimer verwendet werden.

Rafał Dowgird
quelle
36
Es ist eine wirklich schlechte Hash-Funktion, obwohl sie mit einem berühmten Namen verbunden ist.
Seun Osewa
5
Es ist überhaupt keine schlechte Hash-Funktion, wenn es mit erstklassigen Tabellengrößen verwendet wird. Es ist auch für geschlossenes Hashing gedacht . Wenn die Hash-Werte nicht gleichmäßig verteilt sind, stellt das multiplikative Hashing sicher, dass Kollisionen von einem Wert Elemente mit anderen Hash-Werten wahrscheinlich nicht "stören".
Paolo Bonzini
11
Für die Neugierigen wird diese Konstante als Hash-Größe (2 ^ 32) geteilt durch Phi
awdz9nld
7
Paolo: Knuths Methode ist "schlecht" in dem Sinne, dass sie keine Lawine auf den oberen Bits erzeugt
awdz9nld
9
Bei näherer Betrachtung stellt sich heraus, dass 2654435761 tatsächlich eine Primzahl ist. Das ist wahrscheinlich der Grund, warum es anstelle von 2654435769 gewählt wurde.
Karadoc
149

Ich fand, dass der folgende Algorithmus eine sehr gute statistische Verteilung liefert. Jedes Eingangsbit beeinflusst jedes Ausgangsbit mit einer Wahrscheinlichkeit von etwa 50%. Es gibt keine Kollisionen (jede Eingabe führt zu einer anderen Ausgabe). Der Algorithmus ist schnell, außer wenn die CPU keine eingebaute Ganzzahlmultiplikationseinheit hat. C - Code, unter der Annahme , intbeträgt 32 Bit (für Java, ersetzen >>mit >>>und zu 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 unter Verwendung eines speziellen Multithread-Testprogramms berechnet, das viele Stunden lief und den Lawineneffekt berechnet (die Anzahl der Ausgangsbits, die sich ändern, wenn ein einzelnes Eingangsbit geändert wird; sollte im Durchschnitt fast 16 betragen) Ausgangsbitänderungen (Ausgangsbits sollten nicht voneinander abhängen) und die Wahrscheinlichkeit einer Änderung in jedem Ausgangsbit, wenn ein Eingangsbit geändert wird. Die berechneten Werte sind besser als der von MurmurHash verwendete 32-Bit-Finalizer und fast so gut (nicht ganz) wie bei Verwendung von AES . Ein kleiner Vorteil ist, dass dieselbe Konstante zweimal verwendet wird (dies hat sie beim letzten Test etwas schneller gemacht, nicht sicher, ob dies immer noch der Fall ist).

Sie können den Prozess umkehren (den Eingabewert aus dem Hash abrufen), wenn Sie den 0x45d9f3bdurch 0x119de1f3(die multiplikative Inverse ) 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: Auch wenn es möglicherweise nicht das schnellste ist. Dieser basiert auf splitmix64 , das auf dem Blog-Artikel Better Bit Mixing (Mix 13) zu basieren scheint .

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

Verwenden Sie für Java, longfügen Sie Lder Konstante hinzu, ersetzen Sie sie >>durch >>>und entfernen Sie sie unsigned. In diesem Fall ist das Umkehren 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;
}

Update: Möglicherweise möchten Sie sich auch das Hash Function Prospector- Projekt ansehen , in dem andere (möglicherweise bessere) Konstanten aufgeführt sind.

Thomas Müller
quelle
2
Die ersten beiden Zeilen sind genau gleich! Gibt es hier einen Tippfehler?
Kshitij Banerjee
3
Nein, dies ist kein Tippfehler. In der zweiten Zeile werden die Bits weiter gemischt. Die Verwendung nur einer Multiplikation ist nicht so gut.
Thomas Mueller
3
Ich habe die magische Zahl geändert, weil ich gemäß einem Testfall, den ich geschrieben habe, den Wert 0x45d9f3b für eine bessere Verwirrung und Diffusion sorgt , insbesondere wenn sich ein Ausgangsbit ändert, ändert sich jedes andere Ausgangsbit mit ungefähr der gleichen Wahrscheinlichkeit (zusätzlich zu allen Ausgangsbits, die sich mit dem ändern gleiche Wahrscheinlichkeit, wenn sich ein Eingangsbit ändert). Wie haben Sie gemessen, dass 0x3335b369 für Sie besser funktioniert? Ist ein int 32 Bit für Sie?
Thomas Müller
3
Ich suche nach einer netten Hash-Funktion für 64-Bit-Int ohne Vorzeichen bis 32-Bit-Int ohne Vorzeichen. Ist in diesem Fall die oben genannte magische Zahl gleich? Ich habe 32 Bit statt 16 Bit verschoben.
Alessandro
3
Ich glaube in diesem Fall wäre ein größerer Faktor besser, aber Sie müssten einige Tests durchführen. Oder (das ist, was ich tue) zuerst die x = ((x >> 32) ^ x)obigen 32-Bit-Multiplikationen verwenden und dann verwenden. Ich bin mir nicht sicher, was besser ist. Vielleicht möchten Sie sich auch den 64-Bit-Finalizer für Murmur3
Thomas Mueller vom
29

Hängt davon ab, wie Ihre Daten verteilt werden. Für einen einfachen Zähler die einfachste Funktion

f(i) = i

wird gut sein (ich vermute optimal, aber ich kann es nicht beweisen).

erikkallen
quelle
3
Das Problem dabei ist, dass es häufig große Mengen von Ganzzahlen gibt, die durch einen gemeinsamen Faktor teilbar sind (wortausgerichtete Speicheradressen usw.). Wenn Ihre Hash-Tabelle nun durch denselben Faktor teilbar ist, werden nur noch die Hälfte (oder 1/4, 1/8 usw.) der Eimer verwendet.
Rafał Dowgird
8
@ Rafal: Deshalb lautet die Antwort "für einen einfachen Zähler" und "
Hängt
5
Das ist eigentlich die Implementierung der Methode hashCode () durch Sun in java.lang.Integer grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/…
Juande Carrion
5
@JuandeCarrion Das ist irreführend, weil das nicht der Hash ist, der verwendet wird. Nachdem Java die Leistung von zwei Tabellengrößen verwendet hat, wird jeder zurückgegebene Hash erneut aufbereitet .hashCode()(siehe hier) .
Esailija
8
Die Identitätsfunktion ist aufgrund ihrer Verteilungseigenschaften (oder ihres Fehlens) in vielen praktischen Anwendungen als Hash ziemlich nutzlos, es sei denn, Lokalität ist natürlich ein gewünschtes Attribut
awdz9nld
12

Schnelle und gute Hash-Funktionen können aus schnellen Permutationen mit geringeren Qualitäten wie z

  • Multiplikation mit einer ungeraden ganzen Zahl
  • binäre Rotationen
  • xorshift

Um eine Hashing-Funktion mit überlegenen Qualitäten zu erhalten, wie mit PCG für die Zufallszahlengenerierung gezeigt.

Dies ist in der Tat auch das Rezept, das rrxmrrxmsx_0 und Murmeln-Hash wissentlich oder unwissentlich verwenden.

Ich persönlich gefunden

uint64_t xorshift(const uint64_t& n,int i){
  return n^(n>>i);
}
uint64_t hash(const uint64_t& n){
  uint64_t p = 0x5555555555555555ull; // pattern of alternating 0 and 1
  uint64_t c = 17316035218449499591ull;// random uneven integer constant; 
  return c*xorshift(p*xorshift(n,32),32);
}

gut genug sein.

Eine gute Hash-Funktion sollte

  1. Seien Sie bijektiv, wenn möglich keine Informationen zu verlieren und die geringsten Kollisionen zu haben
  2. Kaskade so viel und so gleichmäßig wie möglich, dh jedes Eingangsbit sollte jedes Ausgangsbit mit einer Wahrscheinlichkeit von 0,5 umdrehen.

Schauen wir uns zunächst die Identitätsfunktion an. Es erfüllt 1. aber nicht 2 .:

Identitätsfunktion

Das Eingangsbit n bestimmt das Ausgangsbit n mit einer Korrelation von 100% (rot) und keine anderen. Sie sind daher blau und ergeben eine perfekte rote Linie.

Eine Xorshift (n, 32) ist nicht viel besser und ergibt eineinhalb Linien. Immer noch zufriedenstellend 1., weil es mit einer zweiten Anwendung invertierbar ist.

xorshift

Eine Multiplikation mit einer vorzeichenlosen Ganzzahl ist viel besser, kaskadiert stärker und kippt mehr Ausgangsbits mit einer Wahrscheinlichkeit von 0,5, was Sie wollen, in Grün. Es erfüllt 1. wie für jede ungerade ganze Zahl gibt es eine multiplikative Inverse.

knuth

Die Kombination der beiden ergibt die folgende Ausgabe, die immer noch 1 erfüllt, da die Zusammensetzung zweier bijektiver Funktionen eine weitere bijektive Funktion ergibt.

knuth • xorshift

Eine zweite Anwendung von Multiplikation und Xorshift ergibt Folgendes:

vorgeschlagener Hash

Oder Sie können Galois- Feldmultiplikationen wie GHash verwenden , die auf modernen CPUs relativ schnell geworden sind und in einem Schritt überlegene Qualitäten aufweisen.

   uint64_t const inline gfmul(const uint64_t& i,const uint64_t& j){           
     __m128i I{};I[0]^=i;                                                          
     __m128i J{};J[0]^=j;                                                          
     __m128i M{};M[0]^=0xb000000000000000ull;                                      
     __m128i X = _mm_clmulepi64_si128(I,J,0);                                      
     __m128i A = _mm_clmulepi64_si128(X,M,0);                                      
     __m128i B = _mm_clmulepi64_si128(A,M,0);                                      
     return A[0]^A[1]^B[1]^X[0]^X[1];                                              
   }
Wolfgang Brehm
quelle
gfmul: Der Code scheint Pseudocode zu sein, da afaik mit __m128i keine Klammern verwenden kann. Immer noch sehr interessant. Die erste Zeile scheint zu sagen: "Nimm ein unitialisiertes __m128i (I) und xor es mit (Parameter) i. Sollte ich dies als Initialisierung I mit 0 und xor mit i lesen? Wenn ja, wäre es dasselbe wie Laden I mit i und führen Sie eine nicht (Betrieb) auf I?
Jan
@Jan was ich tun möchte ist __m128i I = i; //set the lower 64 bits, aber das kann ich nicht, also benutze ich ^=. 0^1 = 1daher nicht nicht beteiligt. In Bezug auf die Initialisierung mit {}meinem Compiler, der sich nie beschwert hat, ist es möglicherweise nicht die beste Lösung, aber ich möchte damit alles auf 0 initialisieren, damit ich es tun kann ^=oder |=. Ich denke, ich habe diesen Code auf diesem Blogpost basiert, der auch die Umkehrung liefert, sehr nützlich: D
Wolfgang Brehm
6

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

Tyler McHenry
quelle
6
  • 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

  • Integer Hash Funktion
Rechnung
quelle
3

Bei Eternally Confuzzled gibt es einen schönen Überblick über einige Hash-Algorithmen . Ich würde Bob Jenkins 'einzelnes Hash empfehlen, das schnell die Lawine erreicht und daher für eine effiziente Suche nach Hash-Tabellen verwendet werden kann.

Christoph
quelle
4
Das ist ein guter Artikel, aber er konzentriert sich auf das Hashing von Zeichenfolgenschlüsseln, nicht auf Ganzzahlen.
Adrian Mouat
Um ganz klar zu sein, obwohl die Methoden in diesem Artikel für ganze Zahlen funktionieren würden (oder angepasst werden könnten), gehe ich davon aus, dass es effizientere Algorithmen für ganze Zahlen gibt.
Adrian Mouat
2

Die Antwort hängt von vielen Dingen ab wie:

  • Wo wollen Sie es einsetzen?
  • Was versuchst du mit dem Hash zu machen?
  • Benötigen Sie eine krytographisch sichere Hash-Funktion?

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

dirkgently
quelle
1

Ich denke 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 wirst.

Es gibt bessere Datenstrukturen als Hash-Tabellen 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, zu sehen, wie sie verteilt sind usw., bevor ich über meine Hash-Funktion nachdenke.

Ouanixi
quelle
1

Für zufällige Hash-Werte sagten einige Ingenieure, dass die Primzahl des Goldenen Schnitts (2654435761) eine schlechte Wahl ist. Bei meinen Testergebnissen stellte ich fest, dass dies nicht der Fall ist. Stattdessen verteilt 2654435761 die Hash-Werte ziemlich gut.

#define MCR_HashTableSize 2^10

unsigned int
Hash_UInt_GRPrimeNumber(unsigned int key)
{
  key = key*2654435761 & (MCR_HashTableSize - 1)
  return key;
}

Die Größe der Hash-Tabelle muss eine Zweierpotenz sein.

Ich habe ein Testprogramm geschrieben, um viele Hash-Funktionen für ganze Zahlen auszuwerten. Die Ergebnisse zeigen, dass GRPrimeNumber eine ziemlich gute Wahl ist.

Ich habe versucht:

  1. total_data_entry_number / total_bucket_number = 2, 3, 4; wobei total_bucket_number = Hash-Tabellengröße;
  2. Zuordnen der Hashwertdomäne zur Bucket-Indexdomäne; Konvertieren Sie den Hash-Wert durch Logical And Operation mit (hash_table_size - 1) in einen Bucket-Index, wie in Hash_UInt_GRPrimeNumber () gezeigt.
  3. Berechnen Sie die Kollisionsnummer jedes Eimers.
  4. Notieren Sie den nicht zugeordneten Bucket, dh einen leeren Bucket.
  5. Finden Sie die maximale Kollisionszahl aller Schaufeln heraus. das heißt, die längste Kettenlänge;

Bei meinen Testergebnissen stellte ich fest, dass die Golden Ratio Prime Number immer weniger leere Eimer oder null leere Eimer und die kürzeste Kollisionskettenlänge aufweist.

Einige Hash-Funktionen für Ganzzahlen gelten als gut, aber die Testergebnisse zeigen, dass bei total_data_entry / total_bucket_number = 3 die längste Kettenlänge größer als 10 ist (maximale Kollisionszahl> 10) und viele Buckets nicht zugeordnet sind (leere Buckets) ), was sehr schlecht ist, verglichen mit dem Ergebnis von null leerem Eimer und längster Kettenlänge 3 durch Golden Ratio Prime Number Hashing.

Übrigens, mit meinen Testergebnissen fand ich, dass eine Version der Shifting-Xor-Hash-Funktionen ziemlich gut ist (sie wird von Mikera geteilt).

unsigned int Hash_UInt_M3(unsigned int key)
{
  key ^= (key << 13);
  key ^= (key >> 17);    
  key ^= (key << 5); 
  return key;
}
Chen-ChungChia
quelle
2
Aber warum nicht das Produkt nach rechts verschieben, damit Sie die am meisten gemischten Teile behalten? So sollte es funktionieren
Harold
1
@harold, die Primzahl des goldenen Schnitts wird sorgfältig ausgewählt, obwohl ich denke, dass es keinen Unterschied macht, aber ich werde testen, ob es mit den "am meisten gemischten Bits" viel besser ist. Mein Punkt ist zwar: "Es ist keine gute Wahl." ist nicht wahr, wie die Testergebnisse zeigen, nur den unteren Teil der Bits zu greifen ist gut genug und sogar besser als viele Hash-Funktionen.
Chen-ChungChia
(2654435761, 4295203489) ist ein goldener Schnitt von Primzahlen.
Chen-ChungChia
(1640565991, 2654435761) ist auch ein goldener Schnitt von Primzahlen.
Chen-ChungChia
@harold, das Verschieben des Produkts nach rechts wird schlechter, selbst wenn es nur um 1 Position nach rechts verschoben wird (geteilt durch 2), wird es immer noch schlechter (obwohl immer noch kein leerer Eimer vorhanden ist, aber die längste Kettenlänge größer ist); Wenn Sie sich um mehr Positionen nach rechts verschieben, wird das Ergebnis schlechter. Warum? Ich denke, der Grund ist: Wenn Sie das Produkt nach rechts verschieben, werden mehr Hash-Werte nicht zu Coprime. Nur meine Vermutung, der wahre Grund ist die Zahlentheorie.
Chen-ChungChia
1

Ich benutze splitmix64(in Thomas Muellers Antwort gezeigt ), seit ich diesen Thread gefunden habe. Kürzlich bin ich jedoch auf Pelle Evensens rrxmrrxmsx_0 gestoßen , das eine enorm bessere statistische Verteilung ergab als der ursprüngliche MurmurHash3-Finalizer und seine Nachfolger ( splitmix64und andere Mixe). Hier ist das Code-Snippet in C:

#include <stdint.h>

static inline uint64_t ror64(uint64_t v, int r) {
    return (v >> r) | (v << (64 - r));
}

uint64_t rrxmrrxmsx_0(uint64_t v) {
    v ^= ror64(v, 25) ^ ror64(v, 50);
    v *= 0xA24BAED4963EE407UL;
    v ^= ror64(v, 24) ^ ror64(v, 49);
    v *= 0x9FB21C651E98DF25UL;
    return v ^ v >> 28;
}

Pelle bietet auch eine eingehende Analyse des im letzten Schritt von MurmurHash3und der neueren Varianten verwendeten 64-Bit-Mischers .

Frederico Schardong
quelle
2
Diese Funktion ist nicht bijektiv. Für alle v mit v = ror (v, 25), nämlich alle 0 und alle 1, wird an zwei Stellen dieselbe Ausgabe erzeugt. Für alle Werte v = ror64 (v, 24) ^ ror64 (v, 49), die mindestens zwei weitere und mit v = ror (v, 28) gleich sind, ergeben sich weitere 2 ^ 4, was ungefähr 22 unnötigen Kollisionen entspricht . Zwei Anwendungen von splitmix sind wahrscheinlich genauso gut und genauso schnell, aber dennoch invertierbar und kollisionsfrei.
Wolfgang Brehm