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.
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):
unsignedint hash(unsignedint 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 :
unsignedint unhash(unsignedint 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.
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).
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 "
@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(constuint64_t& n,int i){return n^(n>>i);}uint64_t hash(constuint64_t& n){uint64_t p =0x5555555555555555ull;// pattern of alternating 0 and 1uint64_t c =17316035218449499591ull;// random uneven integer constant; return c*xorshift(p*xorshift(n,32),32);}
gut genug sein.
Eine gute Hash-Funktion sollte
Seien Sie bijektiv, wenn möglich keine Informationen zu verlieren und die geringsten Kollisionen zu haben
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 .:
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.
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.
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.
Eine zweite Anwendung von Multiplikation und Xorshift ergibt Folgendes:
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_tconstinline gfmul(constuint64_t& i,constuint64_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];}
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.
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.
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
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.
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.
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.
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.
Berechnen Sie die Kollisionsnummer jedes Eimers.
Notieren Sie den nicht zugeordneten Bucket, dh einen leeren Bucket.
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).
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>staticinlineuint64_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 .
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.
Antworten:
Knuths multiplikative Methode:
Im Allgemeinen sollten Sie einen Multiplikator auswählen, der in der Reihenfolge Ihrer Hash-Größe (
2^32
im 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.
quelle
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 ,
int
beträgt 32 Bit (für Java, ersetzen>>
mit>>>
und zu entfernenunsigned
):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
0x45d9f3b
durch0x119de1f3
(die multiplikative Inverse ) ersetzen :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 .
Verwenden Sie für Java,
long
fügen SieL
der Konstante hinzu, ersetzen Sie sie>>
durch>>>
und entfernen Sie sieunsigned
. In diesem Fall ist das Umkehren komplizierter:Update: Möglicherweise möchten Sie sich auch das Hash Function Prospector- Projekt ansehen , in dem andere (möglicherweise bessere) Konstanten aufgeführt sind.
quelle
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 Murmur3Hängt davon ab, wie Ihre Daten verteilt werden. Für einen einfachen Zähler die einfachste Funktion
wird gut sein (ich vermute optimal, aber ich kann es nicht beweisen).
quelle
.hashCode()
(siehe hier) .Schnelle und gute Hash-Funktionen können aus schnellen Permutationen mit geringeren Qualitäten wie z
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
gut genug sein.
Eine gute Hash-Funktion sollte
Schauen wir uns zunächst die Identitätsfunktion an. Es erfüllt 1. aber nicht 2 .:
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.
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.
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.
Eine zweite Anwendung von Multiplikation und Xorshift ergibt Folgendes:
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.
quelle
__m128i I = i; //set the lower 64 bits
, aber das kann ich nicht, also benutze ich^=
.0^1 = 1
daher 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: DDiese 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.
quelle
32-Bit-Multiplikationsmethode (sehr schnell) siehe @rafal
32-Bit und 64-Bit (gute Verteilung) bei: MurmurHash
quelle
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.
quelle
Die Antwort hängt von vielen Dingen ab wie:
Ich schlage vor, dass Sie sich die Merkle-Damgard- Familie von Hash-Funktionen wie SHA-1 usw. Anschauen
quelle
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.
quelle
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.
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:
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).
quelle
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 (splitmix64
und andere Mixe). Hier ist das Code-Snippet in C:Pelle bietet auch eine eingehende Analyse des im letzten Schritt von
MurmurHash3
und der neueren Varianten verwendeten 64-Bit-Mischers .quelle