生日悖論（計算碰撞概率）

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;否則你可以輕鬆得到相同的關鍵:)