使用SHA1前8个字符时出现重复哈希的概率

Question

如果我有一个URL的索引，并且使用SHA1哈希的前8个字符对它们进行标识，那么两个不同的URL具有相同ID的概率是多少？

- zino

---

这些人在他们的公共网站上遭受了截断为7个十六进制数字的碰撞。8可能会好一点，但也许不值得冒险。http://blog.getsolid.io/birthday-paradox-coding-solid - nobody

以上网址不在此处：https://www.getsolid.io/blog/birthday-paradox-coding-solid/ - ssi-anik

Answer 1

@Teepeemm已经正确回答了相关问题“给定一个特定的8个十六进制数字序列，另一个SHA-1哈希出现相同的8个数字的概率是多少？” 这是一个非常小的数字。

然而，在这个问题中所涉及的是一个不同的问题：“给定大量的8个十六进制数字序列，任意两个序列相同的概率是多少？”正如问题的第一个评论所指出的那样，这与birthday paradox有关，它不是“房间里有人和我的生日相同的概率是多少？”，而是“这个房间里任意两个人生日相同的概率是多少？”众所周知，只要有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% 的冲突几率。

生日快乐！

- Norman Gray

---

好观点；我没有想到那个。我猜这取决于 OP 为什么要这样做。如果只是为了方便地哈希一些 URL，那么碰撞并不是什么大问题。但如果避免碰撞非常重要，那就另当别论了。 - Teepeemm

Answer 2

SHA-1哈希值有40个16进制数字。如果你只看前8个数字，那么第二个URL具有相同的8个数字的概率是(1/16)^8 ~ 2.32e-10。实际上，这并不取决于一开始有40个数字，甚至不是SHA-1。唯一的假设是SHA-1的前8个数字是独立且等概率分布的。

- Teepeemm