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 ?

30
demandé sur Alex 2013-01-08 11:40:21

2 réponses

72
répondu Adam Morris 2017-05-23 10:29:54

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:

N(n,k)~=k(k-1)/(2n)

La probabilité d'au moins une collision est:

p(n,k)~=1-e^(-k(k-1)/(2n))

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 .

29
répondu Mark Adler 2013-01-08 21:17:57