Hash-Funktion für vier vorzeichenlose Ganzzahlen (C++)

Question

Ich schreibe gerade ein Programm, das vier vorzeichenlose 32-Bit-Ganzzahlen als Ausgabe von einer bestimmten Funktion erzeugt. Ich möchte diese vier Ganzzahlen hashen, damit ich die Ausgabe dieser Funktion mit zukünftigen Ausgaben vergleichen kann.

Ich habe Probleme beim Schreiben einer anständigen Hashing-Funktion. Als ich diesen Code ursprünglich schrieb, warf ich eine einfache Addition der vier ganzen Zahlen ein, von denen ich wusste, dass sie nicht ausreichen würden. Ich habe einige andere Techniken ausprobiert, wie Verschieben und Hinzufügen, ohne Erfolg. Ich bekomme einen Hash, aber es ist von schlechter Qualität und die Funktion erzeugt eine Menge Kollisionen.

Der Hash-Ausgang kann entweder eine 32-Bit- oder eine 64-Bit-Ganzzahl sein. Die fragliche Funktion erzeugt viele Milliarden Hashes, daher sind Kollisionen ein echtes Problem, und ich bin bereit, eine größere Variable zu verwenden, um sicherzustellen, dass möglichst wenige Kollisionen auftreten.

Kann mir jemand helfen, herauszufinden, wie man eine Qualitäts-Hash-Funktion schreibt?

Answer 1

Warum speichern Sie die vier Ganzzahlen nicht in einer geeigneten Datenstruktur und vergleichen sie alle? Der Vorteil, sie in diesem Fall zu hashen, erscheint mir zweifelhaft, es sei denn, die Speicherung ist ein Problem.

Wenn das Problem auftritt, können Sie eine der analysierten Hashfunktionen here verwenden.

Answer 2

Da Hashing Kollisionen erzeugen kann, müssen Sie die Schlüssel trotzdem im Speicher behalten, um diese Kollisionen zu entdecken. Hashmaps und andere Standarddatenstrukturen tun dies in ihrer internen Buchhaltung.

Da der Schlüssel so klein ist, verwenden Sie einfach den Schlüssel direkt anstelle von Hashing. Dies wird schneller und gewährleistet keine Kollisionen.

Answer 3

Warum ein Hash? Es scheint, als wäre ein std :: set oder std :: multi set besser geeignet, um diese Art von Ausgabe zu speichern. Alles, was Sie tun müssen, ist, die vier Ganzzahlen in eine Struktur zu schreiben und eine einfache Vergleichsfunktion zu schreiben.

Answer 4

Versuchen Sie, CRC oder FNV zu verwenden. FNV ist nett, weil es schnell ist und eine definierte Methode zum Falten von Bits hat, um "kleinere" Hash-Werte zu erhalten (d. H. 12-Bit/24-Bit/etc).

Auch der Vorteil der Generierung eines 64-Bit-Hash von einer 128-Bit (4 X 32-Bit) Nummer ist ein wenig fragwürdig, weil wie andere Leute vorgeschlagen haben, könnten Sie einfach den ursprünglichen Wert als Schlüssel in einem verwenden einstellen. Sie möchten wirklich, dass die Anzahl der Bits im Hash die Anzahl der ursprünglichen Werte darstellt. Wenn Ihr Dataset beispielsweise über 100.000 4X32-Bit-Werte verfügt, möchten Sie wahrscheinlich einen 17-Bit- oder 18-Bit-Hash-Wert, keinen 64-Bit-Hash.

Answer 5

Könnte ein bisschen übertrieben sein, aber denken Sie an Boost.Hash. Erzeugt sehr einfachen Code und gute Werte.

Answer 6

Ich stimme Vinko voll und ganz zu - vergleichen Sie sie alle. Wenn Sie weiterhin eine gute Hashing-Funktion haben möchten, müssen Sie die Verteilung Ihrer 4 ungegliederten Ganzzahlen analysieren. Dann müssen Sie Ihre Hashing-Funktion so erstellen, dass das Ergebnis gleichmäßig über den gesamten Bereich des 32-Bit-Hashing-Werts verteilt wird.

Ein einfaches Beispiel - lassen Sie uns einfach davon ausgehen, dass das Ergebnis von jeder Funktion in den meisten Fällen im Bereich von 0 bis 255 liegt. Dann könnten Sie die unteren 8 Bits aus jeder Funktion in Ihren Hash mischen. Meistens würden Sie das Ergebnis direkt finden, nur manchmal (wenn eine Funktion ein größeres Ergebnis liefert) würden Sie eine Kollision haben.

Um es zusammenzufassen - ohne Information, wie die Ergebnisse der 4 Funktionen verteilt sind, können wir Ihnen mit einer guten Hash-Funktion nicht helfen.

Answer 7

Hier ist eine ziemlich vernünftige Hash-Funktion aus 4 ganzen Zahlen 1 integer:

unsigned int hash = in[0]; 
hash *= 37; 
hash += in[1]; 
hash *= 37; 
hash += in[2]; 
hash *= 37; 
hash += in[3]; 

mit gleichmäßig verteilten Eingang gibt es gleichmäßig verteilt ausgegeben. Alle Bits des Eingangs nehmen am Ausgang teil, und jeder Eingangswert (obwohl nicht jedes Eingangsbit) kann jedes Ausgangsbit beeinflussen. Wahrscheinlich ist es schneller als die Funktion, die die Ausgabe erzeugt, in diesem Fall keine Leistung betrifft.

Es gibt andere Hashes mit anderen Eigenschaften, aber akkumulieren-mit-Multiplikation-durch-Prime ist ein guter Start, bis das Gegenteil bewiesen ist. Sie könnten versuchen, mit Xor statt Addition zu akkumulieren, wenn Sie möchten. Wie auch immer, es ist einfach, Kollisionen zu erzeugen (zum Beispiel kollidiert {1, 0, a, b} mit {0, 37, a, b} für alle a, b), also sollten Sie eine Primzahl auswählen, von der Sie denken, dass sie sie hat nichts mit einem plausiblen Implementierungsfehler in Ihrer Funktion zu tun haben. Wenn Ihre Funktion also eine Menge Modulo-37-Arithmetik enthält, verwenden Sie stattdessen vielleicht 1000003.