logo标签列表

使用32位哈希时发生碰撞的概率

algorithmhashcollisionprobabilitycrc
57

我在数据库中有一个10个字符的字符串键字段。我已经使用CRC32哈希了这个字段，但是我担心会出现重复。是否可以告诉我在这种情况下碰撞的概率是多少？

顺便说一句：我的字符串字段在数据库中是唯一的。如果字符串字段的数量为100万，那么发生碰撞的概率是多少？

2个回答
117
4
那么，答案是什么？ - Tommix
从技术上讲，陨石落在你家的可能性是0，除非你的房子在轨道上。 - undefined
47
在您提到的情况下，至少会发生一次碰撞。至少发生一次碰撞的概率约为1-3x10-51。您预期的平均碰撞次数约为116。
通常情况下，在k个样本中，每个样本是从n个可能的值中随机选择的，平均碰撞次数为：

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

至少发生一次碰撞的概率是：

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

在您的情况下，n = 232，k = 106。
在您的情况下，三方碰撞的概率约为0.01。参见生日问题。
非常感谢，我想知道这个概率是否仍然依赖于CRC32算法？ - nguyenngoc101
2
任何好的32位哈希算法都会给出完全相同的结果。 - Mark Adler
1
你想让它显示“1中的1”吗？只需阅读答案：“至少一个碰撞基本上是保证的”。这意味着概率为1。100％。每一次。 - Mark Adler
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接