URL di identificazione univoca con un numero a 64 bit

Question

Questo è fondamentalmente un problema di matematica, ma molto correlato alla programmazione: se ho 1 miliardo di stringhe contenenti URL, e prendo i primi 64 bit dell'hash MD5 di ciascuno di essi, cosa tipo di frequenza di collisione dovrei aspettarmi?

Come cambia la risposta se ho solo 100 milioni di URL?

Mi sembra che le collisioni saranno estremamente rare, ma queste cose tendono a essere confuse.

Sarebbe meglio usare qualcosa di diverso da MD5? Intendiamoci, non sto cercando sicurezza, solo una buona funzione di hash veloce. Inoltre, il supporto nativo in MySQL è bello.

EDIT: not quite a duplicate

Answer 1

Se i primi 64 bit dell'MD5 costituivano un hash con distribuzione ideale, il paradosso del compleanno significherebbe comunque che si otterrebbero collisioni per ogni 2^32 URL. In altre parole, la probabilità di una collisione è il numero di URL diviso per 4.294.967.296. Vedere http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem per i dettagli.

Non mi sentirei a mio agio buttando via metà dei bit in MD5; sarebbe meglio XOR le parole alte e basse a 64 bit per dare loro la possibilità di mixare. Poi di nuovo, MD5 non è affatto veloce o sicuro, quindi non mi preoccuperei affatto di questo. Se vuoi una velocità accecante con una buona distribuzione, ma senza pretesa di sicurezza, puoi provare le versioni a 64 bit di MurmurHash. Vedi http://en.wikipedia.org/wiki/MurmurHash per dettagli e codice.

Answer 2

Hai etichettato questa come "compleanno paradosso", penso che tu know the answer already.

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

dove n è 1 miliardo nel tuo caso.

Sarà un po 'meglio usare qualcosa di diverso da MD5, perché MD5 ha pratical collusion problem.

Answer 3

Da quello che vedo, hai bisogno di una funzione di hash con i seguenti requisiti,

1. hash arbitrarie stringhe di lunghezza ad un valore a 64 bit
   • Be buona - Evitare le collisioni
   • Non necessariamente a senso unico (sicurezza non richiesta)
   • Preferibilmente veloce - che è una caratteristica necessaria per un'applicazione non di sicurezza

Questo hash function survey può essere utile per eseguire il drill down sulla funzione più adatta a te.
Suggerirò di provare più funzioni da qui e di caratterizzarle per il tuo probabile set di input (scegli alcuni miliardi di URL che pensi di vedere).

È possibile generare effettivamente another column like this test survey per l'elenco di URL di prova da caratterizzare e selezionare dalle funzioni di hash esistenti o nuove (più righe in quella tabella) che si desidera controllare. Hanno il codice sorgente MSVC++ per iniziare (reference to ZIP link).

La modifica delle funzioni di hash per adattarsi alla larghezza di output (64 bit) offre una caratterizzazione più accurata per l'applicazione.

Answer 4

Solo utilizzando un hash, c'è sempre una possibilità di collisioni. E non sai in anticipo se le collisioni accadranno una o due volte, o anche centinaia o migliaia di volte nella tua lista di URL.

La probabilità è ancora solo una probabilità. È come lanciare un dado 10 o 100 volte, quali sono le probabilità di ottenere tutti i sei? La probabilità dice che è basso, ma può ancora succedere. Forse anche molte volte di seguito ...

Così mentre lo birthday paradox mostra come calcolare le probabilità, è ancora necessario decidere se le collisioni sono accettabili o meno.

... e le collisioni sono accettabili e gli hash sono ancora la strada giusta da percorrere; trovare un algoritmo di hashing a 64 bit invece di affidarsi a "half-a-MD5" con una buona distribuzione. (Anche se probabilmente è ...)

Answer 5

Se hai 2^n possibilità di hash, c'è più del 50% di possibilità di collisione quando hai 2^(n/2) elementi.

E.G. se il tuo hash è 64 bit, hai 2^64 possibilità di hash, avresti una probabilità del 50% di collisione se hai 2^32 elementi in una raccolta.