URL che identificano in modo univoco con un numero a 64 bit

Question

Questo è fondamentalmente un problema di matematica, ma molto legato alla programmazione:se ho 1 miliardo di stringhe contenenti URL e prendo i primi 64 bit dell'hash MD5 di ciascuna di esse, che 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 creare confusione.

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

MODIFICARE: non proprio un duplicato

Answer 1

Se i primi 64 bit del MD5 costituivano un hash con la distribuzione ideale, il paradosso del compleanno sarebbe ancora significa che si otterrebbe collisioni per ogni URL di 2 ^ 32. 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 vorrei stare tranquillo solo buttare via la metà dei bit in MD5; sarebbe meglio per XOR le parole alte e basse a 64 bit per dare loro la possibilità di mescolare. Poi di nuovo, MD5 non è affatto veloce o sicuro, quindi non mi preoccuperei con esso a tutti. Se si desidera che la velocità accecante con una buona distribuzione, ma nessuna pretesa di sicurezza, si potrebbe provare le versioni a 64 bit di MurmurHash. Vedere http://en.wikipedia.org/wiki/MurmurHash per i dettagli e il codice.

Answer 2

Hai etichettato questo come "paradosso del compleanno", penso di sì conosco già la risposta.

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

dove n è 1 miliardo nel tuo caso.

Ti sentirai un po' meglio usando qualcosa di diverso da MD5, perché MD5 lo ha problema pratico della collusione.

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
   • essere buono - evitare collisioni
   • Non necessariamente a senso unico (la sicurezza non richiesto)
   • Preferibilmente veloce - che è una caratteristica necessaria per un'applicazione non di sicurezza

funzione hash sondaggio può essere utile per il drill-down per la funzione più adatto per voi. < br> Io suggerisco di provare molteplici funzioni da qui e li caratterizza per il set di input probabile (scegliere un paio di miliardi di URL che si pensa si vedrà).

Si può effettivamente generare un'altra colonna come questo test sondaggio per l'elenco degli URL di prova per caratterizzare e selezionare dal eventuali nuove funzioni di hash (più righe in quella tabella) esistenti o che si potrebbe voler controllare. Hanno MSVC ++ codice sorgente per iniziare con ( riferimento al collegamento ZIP ).

La modifica delle funzioni di hash per soddisfare la larghezza di uscita (64-bit) vi darà una caratterizzazione più accurata per la propria applicazione.

Answer 4

Se avete 2 possibilità ^ n hash, c'è più di un 50% di probabilità di collisione quando si dispone di 2 ^ (n / 2) articoli.

es. Se il vostro hash è di 64 bit, si hanno 2 ^ 64 possibilità di hash, devi avere una probabilità del 50% di collisione se si dispone di 2 ^ 32 elementi in una collezione.

Answer 5

semplicemente utilizzando un hash, c'è sempre la possibilità di collisioni. E non si sa in anticipo che scendessimo collisioni accadrà una volta o due, o anche centinaia o migliaia di volte nella tua lista di URL.

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

Così, mentre i href="http://en.wikipedia.org/wiki/Birthday_problem" 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 il modo giusto per andare; trovare un algoritmo di hashing a 64 bit invece di basarsi su "una mezza MD5" avere una buona distribuzione. (Anche se probabilmente ha ...)