7

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

如果我只有 1 亿个 URL，答案会如何变化？

在我看来，碰撞将极为罕见，但这些事情往往令人困惑。

使用MD5以外的东西会更好吗？请注意，我不是在寻找安全性，只是一个很好的快速哈希函数。此外，MySQL 的原生支持也很好。

编辑：不完全重复

4

5 回答 5

6

如果 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。

于 2009-07-08T07:24:21.020 回答
2

您已将此标记为“生日悖论”，我想您已经知道答案了。

P(Collision) = 1 - (2^64)!/((2^64)^n (1 - n)!)

在你的情况下，n 是 10 亿。

使用 MD5 以外的东西会更好一些，因为 MD5 有实际的共谋问题。

于 2009-07-08T07:22:59.197 回答
2

据我所知，您需要一个具有以下要求的哈希函数，

  1. 将任意长度的字符串散列为 64 位值
    • 保持良好 - 避免碰撞
    • 不一定是单向的（不需要安全性）
    • 最好快——这是非安全应用程序的必要特征

此哈希函数调查可能有助于深入了解最适合您的函数。
我会建议从这里尝试多个函数，并为您可能的输入集（选择您认为会看到的数十亿个 URL）描述它们的特征。

实际上，您可以为您的测试 URL 列表生成另一个列，例如此测试调查，以表征和选择您可能想要检查的现有或任何新哈希函数（该表中的更多行）。他们有 MSVC++ 源代码开始（参考 ZIP 链接）。

更改散列函数以适合您的输出宽度（64 位）将为您的应用程序提供更准确的表征。

于 2009-07-08T07:39:46.323 回答
2

如果您有 2^n 个哈希可能性，那么当您有 2^(n/2) 个项目时，发生冲突的可能性超过 50%。

例如，如果您的散列是 64 位，则您有 2^64 种散列可能性，如果集合中有 2^32 个项目，您将有 50% 的机会发生冲突。

于 2009-07-08T20:01:01.580 回答
1

仅仅通过使用哈希，总是有可能发生冲突。而且您事先不知道冲突是否会在您的 url 列表中发生一次或两次，甚至数百次或数千次。

概率仍然只是概率。就像掷骰子 10 次或 100 次一样，得到所有 6 的机会有多大？概率说它很低，但它仍然可能发生。甚至可能连续多次...

因此，虽然生日悖论向您展示了如何计算概率，但您仍然需要确定碰撞是否可以接受。

...并且冲突是可以接受的，散列仍然是正确的方法；找到一个 64 位散列算法，而不是依赖具有良好分布的“half-a-MD5”。（虽然它可能有......）

于 2009-07-08T08:02:12.223 回答