Wie Mapping 100 Millionen Zeichenfolge in 100 Tausend int?

Question

Ich habe etwa 100 Millionen einfache Schlüssel-Wert-Paare (es ist Legacy-Daten, nie zu aktualisieren, und Schlüssel sind zufällige Zeichenfolge), und ich möchte sie in Redis für die Abfrage speichern.

mein Gedanke ist, dass ich die ersten vier Zeichen als Hash-Schlüssel verwenden, und speichern Sie sie in einen Hash-Typ, so gibt es etwa eine Million Hash-Schlüssel in redis, mit jedem Hash-Schlüssel hat etwa 1000 Unterschlüssel.

aber die Dinge laufen einfach nicht wie geplant. Aus irgendeinem Grund fand ich einige Hash-Schlüssel nur einen Unterschlüssel, aber einige haben mehr als 500.000 Unterschlüssel, die nicht sehr effizient im Speicher codiert werden können.

also würde ich gerne wissen, dass es gibt einige einfache verständliche Algorithmus, der meine 100 Millionen Zeichenfolge durchschnittlich in 100 Tausend Eimer (Int) teilen kann. Wenn ich eine Saite aufnehme, kann ich mit dem gleichen Algorithmus wissen, wohin sie geht.

danke !!

Answer 1

Wenn Sie nur einen kleinen Teil der Zeichenfolge zum Berechnen der Hash-Funktion verwenden, kann das ein Problem sein, da beispielsweise alle Zeichenfolgen dasselbe Präfix haben.

Es gibt eine Beschreibung von String-Hash-Funktionen, die die gesamte Zeichenfolge bei http://www.javamex.com/tutorials/collections/hash_function_technical_2.shtml und Good Hash Function for Strings nehmen (tatsächlich geben sie zwei verschiedene Beschreibungen der gleichen Funktion).

Eine Möglichkeit, dies zu betrachten, ist, dass es die Zeichen eines Strings als die Koeffizienten A, B, C eines Polynoms der Form A + Bx + Cx^2 + Dx^3 ... betrachtet Fall x ist 31 und Arithmetik ist Modulo 2^32. Wenn x gut gewählt ist, dann ist dies ein Schema, mit dem es viel Erfahrung und einige mathematische Kenntnisse geben können, die ihm gute Eigenschaften verleihen. Noch besser ist es, den arithmetischen Modulo die Größe der Hash-Tabelle zu machen und die Größe der Hash-Tabelle als Primzahl zu wählen. Wenn Ihre Daten statisch sind, könnte es sich lohnen, ein paar verschiedene Primzahlen Ihrer bevorzugten Tabellengröße und einiger verschiedener x-Werte auszuprobieren, und wählen Sie die Kombination aus, die Ihnen die gleichmäßigste Tabelle liefert.