zin*_*ino 10 math sha1 probability hash-collision
如果我有一个URL索引,并通过SHA1哈希的前8个字符对它们进行ID,那么两个不同URL具有相同ID的概率是多少？
Nor*_*ray 22
@Teepeemm正确回答了相关的问题'给定8个十六进制数字的特定序列,另一个SHA-1哈希出现在相同的 8位数的几率是多少？' 这是一个非常小的数字.
然而,这个问题的关键是一个不同的问题:"鉴于大量的8位十六进制数字序列,它们中任何两个相同的可能性是多少？" 正如对问题的第一个评论所指出的,这与生日悖论有关,这不是"房间里有人和我生日相同的机会是什么？"而是" 任何两个人的机会是什么？" 这个房间有同样的生日吗？' 众所周知,仅有23人的可能性为50%.
哈希冲突问题本质上是相同的问题,但是从N = 365天推广到N = 16 ^ 8个 8字节序列,其大约是4.30e9.这就是'普遍的生日问题'.使用那里引用的表达式(n = sqrt(2*d*ln(1 /(1-p))),d = 4.30e9和p = 0.5,我们发现仅有77000次试验发生碰撞的几率为50%.如果绘制相应的函数,您会发现随着试验次数的增加,概率会迅速增加.
即使有16个字节的散列(所以d = 16 ^ 16),在仅有50亿次试验后,有50%的机会发生碰撞.
生日快乐!