瞭解衝突定製我使用散列

Question

在我的應用程序如下：

base64.urlsafe_b64encode(str(random.getrandbits(20))).lower().replace('=', '') 

減號審美的變化：

base64.urlsafe_b64encode(str(random.getrandbits(20)) 

我如何去尋找出發生碰撞的可能性有多大？

Answer 1

由於外部函數是確定性的，所以它與另一個random.getrandbits(20)發生碰撞的可能性相同。

如果random.getrandbits輸出實際上，隨機 - 一個與另一個相撞機會爲1 /（2^20）或大約... 1百萬

對於n條目中，附加條目（條目n + 1）碰撞的機會是n /（2^20）。所以概率隨着字典中條目的數量呈線性增長。在1,048,576個條目中，保證下一個條目將發生衝突。

Answer 2

有2^20個不同的可能的隨機值。因此，兩個給定的隨機值相等的概率是1 /（2^20），或者大約百萬分之一（）。

但是，如果您正在創建多個值，則由於birthday paradox你只需要生成約2^10或約千不同的值擁有其中的兩個相等50％的機會！

爲了避免這種情況，我會推薦至少128位。這需要大約2^64（~18億十億）的值，纔有50％的碰撞機會。當編碼到base-64時，這將是22個字符長。