algorithm - resolucion - tablas hash estructura de datos
Probabilidad de colisión cuando se usa un hash de 32 bits (2)
Tengo un campo de clave de cadena de 10 caracteres en una base de datos. He usado CRC32 para hash este campo, pero me preocupan los duplicados. ¿Podría alguien mostrarme la probabilidad de colisión en esta situación?
ps mi campo de cadena es único en la base de datos. Si el número de campos de cadena es 1 millón, ¿cuál es la probabilidad de colisión?
En el caso que cites, al menos una colisión está esencialmente garantizada. La probabilidad de al menos una colisión es de aproximadamente 1 - 3x10 -51 . La cantidad promedio de colisiones que esperarías es alrededor de 116.
En general, el número promedio de colisiones en k muestras, cada una de ellas una elección aleatoria entre n posibles valores es:
La probabilidad de al menos una colisión es:
En tu caso, n = 2 32 yk = 10 6 .
La probabilidad de una colisión de tres vías en su caso es de aproximadamente 0.01. Vea el problema del cumpleaños .
Duplicado de colisiones esperadas para un crc perfecto de 32 bits
La respuesta hace referencia a este artículo: http://arstechnica.com/civis/viewtopic.php?f=20&t=149670
Encontré la imagen a continuación de: http://preshing.com/20110504/hash-collision-probabilities