这基本上是一个数学问题，但很编程相关的：如果我有一个包含URL 1个十亿字符串，我把他们每个人的MD5哈希的前64位，我应该期待什么样的碰撞频率的？
怎样的答案改变，如果我只能有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:
从我所看到的，你需要一个散列函数如下要求，
- 散列任意长度字符串到一个64位的值
- 好 - 避免碰撞
- 不一定是单向的（不要求安全性）
- 优选快速 - 这是一个非安全应用程序的必要特性
该散列函数的调查可能是向下钻取到最适合你的功能非常有用。
我会建议从这里尝试多种功能，并为您的设定可能的输入表征他们（挑选一个数十亿的网址，你认为你会看到）。
实际上，你可以生成这样的测试调查另一列用于测试的URL列表来描述，并从你可能要检查现有或任何新的散列函数（该表中更多的行）中进行选择。 他们有MSVC ++源代码开始（ 参照ZIP链接 ）。
更改散列函数，以满足您的输出宽度（64位）会给你的应用程序更准确的表征。
Answer 4:
如果你有2 ^ n个哈希的可能性，有过碰撞的几率为50％时，你有2 ^（N / 2）项目。
例如，如果你的哈希值是64位的，你有2 ^ 64哈希的可能性，你就会有碰撞的50％的机会，如果你有一个集合在2 ^ 32个项目。
Answer 5:
Just by using a hash, there is always a chance of collisions. And you don't know beforehand wether collisions will happen once or twice, or even hundreds or thousands of times in your list of urls.
The probability is still just a probability. Its like throwing a dice 10 or 100 times, what are the chances of getting all sixes? The probability says it is low, but it still can happen. Maybe even many times in a row...
So while the birthday paradox shows you how to calculate the probabilities, you still need to decide if collisions are acceptable or not.
...and collisions are acceptable, and hashes are still the right way to go; find a 64 bit hashing algorithm instead of relying on "half-a-MD5" having a good distribution. (Though it probably has...)
文章来源: Uniquely identifying URLs with one 64-bit number
