algorithm - 使用 32 位散列时的冲突概率

Question

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

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

Answer 1

完美 32 位 crc的预期碰撞重复

答案参考了这篇文章：http ://arstechnica.com/civis/viewtopic.php?f=20&t=149670

找到下面的图片：http: //preshing.com/20110504/hash-collision-probabilities

Answer 2

在您引用的情况下，基本上可以保证至少发生一次碰撞。至少发生一次碰撞的概率约为 1 - 3x10 ^-51。您预期的平均碰撞次数约为 116。

一般来说，k个样本中的平均碰撞次数，每个样本都是从n 个可能值中随机选择的：

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

在您的情况下，n = 2 ³²和k = 10 ⁶。

在您的情况下，三向碰撞的概率约为 0.01。请参阅生日问题。