Ho un campo chiave a 10 caratteri in un database. Ho usato CRC32 per hash in questo campo, ma sono preoccupato per i duplicati. Qualcuno potrebbe mostrarmi la probabilità di collisione in questa situazione?Probabilità di collisione quando si utilizza un hash a 32 bit
p.s. il mio campo stringa è unico nel database. Se il numero di campi stringa è 1 milione, qual è la probabilità di collisione?
duplicati di Expected collisions for perfect 32bit crc
La risposta fa riferimento questo articolo: http://arstechnica.com/civis/viewtopic.php?f=20&t=149670
Trovato l'immagine qui sotto da: http://preshing.com/20110504/hash-collision-probabilities
Nel caso che citi, almeno una collisione è essenzialmente garantita. La probabilità di almeno una collisione è di circa 1 - 3x10 -51. Il numero medio di collisioni che ci si aspetta è di circa 116.
In generale, il numero medio di collisioni in k campioni, ognuno una scelta casuale tra n possibili valori è:
La probabilità di almeno una collisione è:
Nel tuo caso, n = 2 e k = 10 .
La probabilità di uno tre -in caso di collisione nel vostro caso è di circa 0.01. Vedi lo Birthday Problem.
Grazie mille, mi chiedo che questa probabilità dipenda ancora dall'algoritmo CRC32? – nguyenngoc101
Qualsiasi buon algoritmo di hash a 32 bit darà esattamente lo stesso risultato. –