database - DataBase中的生日悖论(计算碰撞概率)

Question

根据生日悖论:

如果我将它应用于数据库(如果我错了请纠正我):如果我们需要在数据库中存储 UNIQUE 散列数据，并且我们有一个可以生成 365 个唯一散列值的散列算法，则在前 23 个数据条目之后发生数据冲突的可能性为 50%，而 99.9% (!) 前 75 个数据库条目后发生冲突的可能性。

我们的算法可以生成的唯一哈希的数量和数据条目的数量可以呈指数增长，但冲突的概率将保持不变。如果这是对的？

我有一个巨大的交易表(用于电子商务)，并且我将“收据”字段设置为唯一。而实际的收据编号才是困扰我的地方。

收据编号示例:BHF2Z47E仅大写A-Z/0-9，长度为8个符号。

更新:

The Birthday Paradox

Answer 1

生日悖论只是指出，如果你在 n 的空间中随机生成值，当您存储 sqrt(n) 时，会发生从无碰撞到碰撞的快速相变。值 - 这就是概率增加到 50% 以上的地方。

在您的示例中，您有一个包含 26 + 10 个字符和 8 位数字的字母表；那就是36^8或大约 2.8 万亿个可能的 key ；在大约 160 万次输入后，您可以预期有超过 50% 的碰撞概率；那不是很好。即使是其中的一小部分，也有相当大的碰撞机会。

作为比较，假设您为每张收据生成了一个 160 位随 secret 钥(2^160 可能值)；那么你需要生成大约 2^80收据(大约 10^24 )以达到相同的碰撞概率。您可以将您的产品作为一家非常大的公司销售一辈子，但可能仍然看不到任何产品。另一种观点是，您的硬盘或计算机在您观察到碰撞之前就会发生故障。

The table in this article给你一些具体的数字。例如，使用 256 位哈希值和 10^31插入的值，您将获得 10^-15 的碰撞概率.根据那篇文章，这是围绕您的硬盘的不可纠正的错误率。这可能是您应该针对收据避免覆盖它们的目标。使值稍微大一点并不难。

当然，这取决于您使用随机数据正确播种 PRNG 的事实；否则你可以轻松获得相同的 key :)