唯一确定的网址一个有64位数

Question

这基本上是一个数学问题，但非常节目相关：如果我有1亿串含有的网址，并且我采取的第64位的MD5hash他们每个人，什么样的碰撞频率，我应该期待什么呢？

怎么回答的改变，如果我只有100万网址?

在我看来，冲突将极为罕见，但这些东西往往是混乱。

我会更好使用其他的东西比MD5?你要知道，我不是在寻找安全，只是一个良好的快速散列函数。此外，地支持在MySQL是很好的。

编辑: 没有一个相当重复

Answer 1

如果MD5的前64位构成与理想分配哈希，生日悖论仍然意味着你会得到碰撞，每2 ^ 32的URL。换句话说，发生碰撞的概率由4,294,967,296划分URL的数量。请参见 http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem 了解详情。

我不会感到舒服只是扔掉的MD5一半的比特;这将是更好的异或高和低64位的话，给他们一个机会，以混合。再说，MD5绝不是快还是安全的，所以我不会理会它在所有。如果你想惊人的速度与良好的分配，但没有安全的幌子，你可以尝试murmur哈希的64位版本。请参阅 http://en.wikipedia.org/wiki/MurmurHash 获取详细信息和代码。

Answer 2

您已经标记这是“生日悖论”，我想你知道答案已

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

其中n为1十亿你的情况。

您会好一点用其他的东西，然后MD5，因为MD5有勾结之实践问题

Answer 3

从我所看到的，你需要一散列函数的下列要求，

1. 哈希任意长串到64位价值
   • 是良好的--避免冲突
   • 不一定是一个向(安全不需要的)
   • 最好快--这是一个必要特征为一个非安全应用程序

此 散列函数的调查 可能是有用的钻井下的功能最适合你。
我将建议尝试了多种职能从这里和表征它们为你可能输入设置(挑选几十亿URL，你认为你会看见)。

实际上你可以产生 另一个列喜欢这个测试调查 你的测试的URL清单的表征和选择，从现有的或任何新的散列函数(更多的行为，表)，你可能想要检查。他们有MSVC++源码开始用(参考拉链链接).

改变散列函数来适应你的输出宽度(64位)将给你一个更准确的特性应用程序。

Answer 4

如果你有2 ^ n个哈希可能性，存在当你有2 ^（N / 2）项是在发生碰撞的可能性为50％。

E.G。如果你的哈希值是64位的，你有2 ^ 64哈希的可能性，你就会有碰撞的50％的机会，如果你有一个集合在2 ^ 32个项目。

Answer 5

只需通过使用散列，总有碰撞的机会。而你不事先知道阉碰撞会一次或两次，甚至成百上千次在你的URL列表发生。

的概率仍然只是一个概率。它像扔骰子10或100倍，是什么让所有乱七八糟的可能性有多大？概率说，这是低的，但它仍然可能发生。甚至很多时候在一排...

因此，尽管生日悖论向您展示如何计算概率，你仍然需要决定是否碰撞是可以接受的或不

...和碰撞是可以接受的，和散列仍然去正确的方式;找一个64位的哈希算法，而不是依靠“半一MD5”有一个良好的分布。 （虽然它可能有...）