Probabilité de collision lors de l'utilisation d'un hachage 32 bits
j'ai un champ de clé de chaîne de 10 caractères dans une base de données. J'ai utilisé CRC32 pour Hasher ce champ mais je m'inquiète des doublons. Quelqu'un pourrait-il me montrer la probabilité d'une collision dans cette situation?
p. S. mon champ string est unique dans la base de données. Si le nombre de champs de chaîne est de 1 million, Quelle est la probabilité de collision ?
2 réponses
Dupliquer Attendu collisions pour une parfaite 32 bits crc
la réponse fait référence à cet article: http://arstechnica.com/civis/viewtopic.php?f=20&t=149670
a trouvé l'image ci-dessous de: http://preshing.com/20110504/hash-collision-probabilities
Dans le cas que vous citez, au moins une collision est essentiellement assuré. La probabilité d'au moins une collision est d'environ 1 - 3x10 -51 . Le nombre moyen de collisions est d'environ 116.
en général, le nombre moyen de collisions dans les échantillons k , chaque choix aléatoire parmi n valeurs possibles est:
La probabilité d'au moins une collision est:
dans votre cas, n = 2 32 et k = 10 6 .
la probabilité d'une trois - collision dans votre cas est d'environ 0,01. Voir le problème D'anniversaire .