Hashing-Funktion für vier ganze Zahlen ohne Vorzeichen (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 mit einem Hash versehen, damit ich die Ausgabe dieser Funktion mit zukünftigen Ausgaben vergleichen kann.

Ich habe allerdings Schwierigkeiten, eine anständige Hashing-Funktion zu schreiben. Als ich ursprünglich diesen Code schrieb, warf ich in einer einfachen Addition von jeder der vier ganzen Zahlen, die ich wusste, würde nicht ausreichen. Ich habe verschiedene andere Techniken ausprobiert, wie z. B. das Verschieben und Addieren, ohne Erfolg. Ich erhalte einen Hash, aber er ist von schlechter Qualität, und die Funktion erzeugt eine Menge Kollisionen.

Die Hash-Ausgabe kann entweder eine 32-Bit- oder eine 64-Bit-Ganzzahl sein. Die betreffende Funktion generiert viele Milliarden Hashes, so dass Kollisionen hier ein echtes Problem darstellen, und ich bin bereit, eine größere Variable zu verwenden, um sicherzustellen, dass es so wenige Kollisionen wie möglich gibt.

Kann mir jemand helfen, herauszufinden, wie man eine gute Hash-Funktion schreibt?

Answer 1

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

Wenn es um die Speicherung geht, können Sie eine der analysierten Hash-Funktionen verwenden ici .

Answer 2

Hier ist eine halbwegs vernünftige Hash-Funktion von 4 ganzen Zahlen zu 1 ganzen Zahl:

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

Bei gleichmäßig verteiltem Input ergibt sich ein gleichmäßig verteilter Output. Alle Bits der Eingabe sind an der Ausgabe beteiligt, und jeder Eingabewert (wenn auch nicht jedes Eingabebit) kann jedes Ausgabebit beeinflussen. Wahrscheinlich ist sie schneller als die Funktion, die die Ausgabe erzeugt, in diesem Fall gibt es keine Leistungsprobleme.

Es gibt andere Hashes mit anderen Eigenschaften, aber Akkumulieren-mit-Multiplikation-nach-Primzahlen ist ein guter Anfang, bis das Gegenteil bewiesen ist. Sie können auch versuchen, mit xor anstelle von Addition zu akkumulieren, wenn Sie möchten. So oder so ist es einfach, Kollisionen zu erzeugen (z. B. {1, 0, a, b} kollidiert mit {0, 37, a, b} für alle a, b), so dass Sie vielleicht eine Primzahl wählen sollten, von der Sie glauben, dass sie nichts mit einem plausiblen Implementierungsfehler in Ihrer Funktion zu tun hat. Wenn Ihre Funktion also viel Modulo-37-Arithmetik enthält, können Sie stattdessen 1000003 verwenden.

Answer 3

Da beim Hashing Kollisionen auftreten können, müssen Sie die Schlüssel ohnehin im Speicher halten, um diese Kollisionen zu entdecken. Hashmaps und andere Standard-Datenstrukturen tun dies in ihrer internen Buchführung.

Da der Schlüssel so klein ist, sollten Sie ihn direkt verwenden, anstatt ihn zu hashen. Dies ist schneller und gewährleistet, dass keine Kollisionen auftreten.

Answer 4

Ich stimme Vinko voll und ganz zu - vergleichen Sie sie einfach alle. Wenn Sie trotzdem eine gute Hash-Funktion haben wollen, müssen Sie die Verteilung Ihrer 4 unsinged integers analysieren. Dann müssen Sie Ihre Hash-Funktion so gestalten, dass das Ergebnis gleichmäßig über den gesamten Bereich des 32-Bit-Hash-Wertes verteilt ist.

Ein einfaches Beispiel: Gehen wir davon aus, dass das Ergebnis jeder Funktion meistens im Bereich von 0 bis 255 liegt. Dann könnten Sie einfach die unteren 8 Bits jeder Funktion in Ihren Hash einfügen. In den meisten Fällen würden Sie das Ergebnis direkt finden, nur manchmal (wenn eine Funktion ein größeres Ergebnis liefert) würde es zu einer Kollision kommen.

Zusammenfassend lässt sich sagen, dass wir Ihnen ohne Informationen darüber, wie die Ergebnisse der 4 Funktionen verteilt werden, nicht bei der Auswahl einer guten Hash-Funktion helfen können.

Answer 5

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