使用一个64位数字唯一标识URL

Question

这基本上是一个数学问题,但编程很相关:如果我有10亿个包含URL的字符串,并且我采用每个字符串的MD5哈希的前64位,我应该期望什么样的冲突频率？

如果我只有1亿个网址,答案会如何变化？

在我看来,碰撞将非常罕见,但这些事情往往令人困惑.

使用MD5以外的其他东西会更好吗？请注意,我不是在寻找安全性,只是一个很好的快速哈希函数.此外,MySQL中的本机支持很好.

编辑:不太重复

Answer 1

如果MD5的前64位构成了具有理想分布的散列,那么生日悖论仍然意味着你会得到每2 ^ 32个URL的冲突.换句话说,碰撞的概率是URL的数量除以4,294,967,296.有关详细信息,请参见http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem.

只丢掉MD5中的一半,我感觉不舒服; 最好将高位和低位64位字进行异或,以便给它们混合的机会.再说一次,MD5绝不是快速或安全的,所以我根本不打扰它.如果你想要炫目的速度和良好的分布,但没有安全的假装,你可以尝试64位版本的MurmurHash.有关详细信息和代码,请参见http://en.wikipedia.org/wiki/MurmurHash.