Hash
預期碰撞次數的公式
假設我們有一個雜湊函式產生 $ n $ 位輸出。從生日的問題，之後周圍 $ \sqrt{2^n} $ has 函式的不同輸入，我們可以預期會發生衝突。
說我們有 $ m $ 輸出。我們可以期待多少次碰撞 $ m $ 輸出？
如果有 $ k $ 所有具有相同輸出的輸入，我們說有 $ \binom{k}{2} $ 碰撞。
預期的碰撞次數（假設雜湊函式可以建模為隨機函式）正好是 $ 2^{-n}\binom{m}{2} $ ; 即，預期的值對數 $ x \ne y $ 和 $ H(x) = H(y) $ （因此，回答 Ricky 的問題， $ H(x) = H(y) = H(z) $ 將計為三次碰撞）。
推理是顯而易見的。有 $ \binom{m}{2} $ 分開的對，每一對都有一個機率 $ 2^{-n} $ 碰撞次數（因此預期的碰撞次數為 $ 2^{-n} $ )，並且一組機率值的期望總和是每個單獨值的期望值的總和。機率不是獨立的（例如，如果 $ H(x)=H(y) $ 和 $ H(y)\ne H(z) $ ， 我們知道 $ H(x) \ne H(z) $ ); 事實證明，預期總和不依賴於獨立性。