生日悖论（计算碰撞概率）

Question

根据Birthday paradox：

如果我把它应用到数据库中（请纠正我，如果我错了）： 如果我们需要存储UNIQUE数据库中的散列数据和我们有一个可以生成365个唯一散列值的散列算法，在前75个数据库条目之后的前23个数据条目和99.9％（！）个碰撞机会之后，有50％的机会发生数据冲突。

我们的算法可以生成的唯一哈希的数量和数据条目的数量可以成指数增长，但碰撞的概率将保持不变。如果这个权利？

我有一个巨大的交易表（电子商务）和我有领域'收据'设置为唯一。而实际的收据号码是困扰我的东西。

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

UPDATE：

The Birthday Paradox

Answer 1

生日悖论只是说，如果你随意在n空间产生价值，也从没有冲突碰撞快速相变，当你存储sqrt(n)值 - 这是概率增加到50％以上的地方。

在你的例子中，你有一个26 + 10个字符和8位数的字母;所以这是36^8或约2.8万亿可能的键;在约160万条条目之后，您可能会有超过50％的碰撞概率;这不是很好。即使是其中的一小部分，碰撞的可能性也很大。

作为比较，假设您为每个收据生成了一个160位的随机密钥（2^160可能的值）;那么您将需要生成约2^80收据（约10^24）才能达到相同的碰撞概率。您可以将您的产品作为一个非常大的公司在您的整个生命中销售，并且可能还没有看到。另一个观点是在观察到碰撞之前，您的硬盘或计算机将失败。

The table in this article给出了一些具体的数字给你。例如，如果插入256位散列值和10^31值，则碰撞概率为10^-15。根据那篇文章，这是围绕你的硬盘的不可纠正的错误率。这可能是您应该针对收据避免覆盖它们的目标。让价值变得更大一点不难。

当然，这取决于您使用随机数据正确地播种您的PRNG;否则你可以轻松得到相同的关键:)