使用32位哈希时发生冲突的可能性

Question

我在数据库中有一个10个字符的字符串键字段.我已经使用CRC32来散列这个字段,但我担心重复.在这种情况下,有人能告诉我碰撞的可能性吗？

ps我的字符串字段在数据库中是唯一的.如果字符串字段的数量是100万,那么碰撞概率是多少？

Answer 1

在此输入图像描述

Answer 2

在您引用的情况下,至少可以保证一次碰撞.至少一次碰撞的概率约为1 - 3x10 ^-51.您期望的平均碰撞次数约为116次.

通常,k个样本中的平均冲突数,每个是n个可能值中的随机选择:

N(N,K)〜= K(K-1)/(2n)后

至少一次碰撞的概率是:

P(N,K)〜= 1-E ^( - K(K-1)/(2N))

在您的情况下,n = 2 ³²和k = 10 ⁶.

在你的情况下三次碰撞的概率大约是0.01.看生日问题.