Einzigartig URLs mit einer 64-Bit-Zahl zur Bezeichnung

Question

Dies ist im Grunde ein mathematisches Problem, aber sehr programing verwandte: wenn ich eine Milliarde Zeichenkette enthalten URLs, und ich nehme die ersten 64 Bits des MD5-Hash eines jeden von ihnen, welche Art von Kollisionsfrequenz sollte ich erwarten

Wie funktioniert die Antwort ändern, wenn ich nur 100 Millionen URLs?

Es scheint mir, dass Kollisionen extrem selten sein, aber diese Dinge sind in der Regel verwirrend sein.

mit etwas anderes als MD5

Wäre ich besser dran? Wohlgemerkt, ich bin nicht für die Sicherheit suchen, nur eine gute schnelle Hash-Funktion. Auch native Unterstützung in MySQL ist schön.

Bearbeiten : nicht ganz ein Duplikat

Answer 1

Wenn die ersten 64 Bits des MD5 einen Hash mit idealer Verteilung gebildet wird, würde das Geburtstagsparadoxon bedeutet noch würden Sie Kollisionen bekommen für jeden 2 ^ 32 URLs. Mit anderen Worten, ist die Wahrscheinlichkeit einer Kollision der Anzahl der URL durch 4294967296 dividiert. Siehe http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem .

würde ich fühle mich nicht wohl nur die Bits in MD5 Hälfte wegzuwerfen; es wäre besser, die hohe und niedrige 64-Bit-Worte XOR ihnen eine Chance zu mischen zu geben. Dann wieder ist MD5 keineswegs schnell oder sicher, so würde ich mit ihm überhaupt nicht gestört. Wenn Sie Verblindung Geschwindigkeit mit guter Verteilung wollen, aber keinen Anspruch an Sicherheit, können Sie die 64-Bit-Versionen von MurmurHash versuchen. Siehe http://en.wikipedia.org/wiki/MurmurHash für Details und Code.

Answer 2

Sie markiert haben dies als „Geburtstag-Paradox“, ich glaube, Sie kennen die Antwort bereits .

P(Collision) = 1 - (2^64)!/((2^64)^n (1 - n)!)

, wobei n 1 Milliarde in Ihrem Fall.

Sind Sie ein bisschen besser etwas anderes dann MD5 verwenden, da MD5 haben pratical Kollusion Problem .

Answer 3

Von dem, was ich sehe, Sie brauchen eine Hash-Funktion, mit folgenden Anforderungen,

1. Hash beliebige Zeichenfolge auf einen 64-Bit-Wert
   • Seien Sie gut - Vermeiden von Kollisionen
   • Nicht unbedingt one-way (Sicherheit nicht erforderlich)
   • Vorzugsweise schnell - das ist eine notwendige Eigenschaft für eine Nicht-Sicherheits-Anwendung ist

Hashfunktion Umfrage kann zum Bohren bis auf die Funktion am besten geeignet für Sie nützlich sein. < br> Ich werde vorschlagen, mehrere Funktionen von hier ausprobieren und für Ihre wahrscheinlich Eingabemenge charakterisierende (ein paar Milliarden URL auswählen, die Sie denken, Sie werden sehen).

Sie können tatsächlich generieren eine andere Spalte wie dieser Test Umfrage für Ihren Test URL-Liste zu charakterisieren und wählen Sie aus dem bestehenden oder irgendwelchen neuen Hash-Funktionen (mehr Zeilen in dieser Tabelle), die Sie vielleicht prüfen wollen. Sie haben MSVC ++ Quellcode zu beginnen ( Bezug auf ZIP Link ).

Ändern der Hash-Funktionen, um Ihre Ausgabebreite anpassen (64-Bit) gibt Ihnen eine genauere Charakterisierung für Ihre Anwendung.

Answer 4

Wenn Sie 2 ^ n Hash-Möglichkeiten haben, gibt es über eine 50% ige Chance einer Kollision, wenn man 2 ^ (n / 2) Gegenstände.

z. wenn Ihr Hash 64 Bits ist, haben Sie 2 ^ 64 Hash-Möglichkeiten, würden Sie eine 50% ige Chance einer Kollision, wenn Sie 2 ^ 32 Elemente in einer Auflistung haben.

Answer 5

Nur durch einen Hash verwenden, gibt es immer eine Chance von Kollisionen. Und Sie wissen nicht im Voraus, ob Kollisionen einmal passieren wird oder zweimal oder sogar hunderte oder tausende Male in der Liste der URLs.

Die Wahrscheinlichkeit ist nach wie vor nur eine Wahrscheinlichkeit. Es ist wie ein Würfel 10 oder 100 mal werfen, was sind die Chancen, alle Sechsen bekommen? Die Wahrscheinlichkeit sagt, es ist niedrig, aber es kann immer noch passieren. Vielleicht sogar viele Male in Folge ...

Während also die Geburtstagsparadox rel="nofollow zeigt Ihnen, wie die Wahrscheinlichkeiten zu berechnen, müssen Sie noch zu entscheiden, ob Kollisionen akzeptabel ist oder nicht.

... und Kollisionen sind akzeptabel, und Hashes ist immer noch der richtige Weg zu gehen; finden Sie einen 64-Bit-Hash-Algorithmus, anstatt sich auf „halb-a-MD5“, um eine gute Verteilung. (Obwohl es wahrscheinlich hat ...)