Wie bewerte ich die Hash-Kollisionswahrscheinlichkeit?

Ich denke, man sollte es nicht.

Allerdings sollten Sie, wenn Sie haben die Vorstellung von zwei gleiche Dateien mit unterschiedlichen (echten Namen, nicht auf md5-Basis). Wie, auf der Suche nach system zwei Dokument möglicherweise haben genau denselben Inhalt, aber unterschieden, denn Sie befinden sich an verschiedenen stellen.

InformationsquelleAutor der Antwort alamar

Kam ich mit einer Monte-Carlo-Ansatz, um in der Lage zu schlafen sicher, während die Verwendung der UUID für verteilte Systeme, die zu serialisieren, ohne Kollisionen.

from random import randint
from math import log
from collections import Counter

def colltest(exp):
    uniques = []
    while True:
        r = randint(0,2**exp)
        if r in uniques:
            return log(len(uniques) + 1, 2)
        uniques.append(r)

for k,v in Counter([colltest(20) for i in xrange(1000)]):
    print k, "hash orders of magnitude events before collission:",v

drucken würde so etwas wie:

5 hash orders of magnitude events before collission: 1
6 hash orders of magnitude events before collission: 5
7 hash orders of magnitude events before collission: 21
8 hash orders of magnitude events before collission: 91
9 hash orders of magnitude events before collission: 274
10 hash orders of magnitude events before collission: 469
11 hash orders of magnitude events before collission: 138
12 hash orders of magnitude events before collission: 1

Hörte ich die Formel vor: Wenn Sie zum speichern von log(x/2) - Tasten verwenden Sie eine Hash-Funktion, die mindestens Schlüsselraum e**(x).

Wiederholte Experimente zeigen, dass für eine Bevölkerung von 1000 Protokoll - -20 Plätze, Sie manchmal eine Kollision so früh wie log(x/4).

Für uuid4 die 122 bits, das heißt, ich Schlaf sicher bei mehreren Computern pick random uuid ' s bis ich über die 2**31 items. Peak-Transaktionen in das system, das ich bin denken ist etwa 10-20 Ereignissen pro Sekunde, ich bin bei einem Durchschnitt von 7. Das gibt mir ein Betriebssystem-Fenster von etwa 10 Jahren, gegeben, dass die extreme paranoia.

InformationsquelleAutor der Antwort Árni St. Sigurðsson