如何计算散列算法碰撞的几率有多大？ [英] How to calculate the odds of a collision in hash algorithms?

问题描述

说我有一个哈希算法，它的漂亮和流畅的（任何一个哈希值上来的几率是一样的任何其他值）。

Say I have a hash algorithm, and it's nice and smooth (The odds of any one hash value coming up are the same as any other value).

现在说，我知道，采摘2哈希的可能性，并有被碰撞是（为了讨论）50000：1

Now say that I know that the odds of picking 2 hashes and there being a collision are (For arguments sake) 50000:1.

现在说我挑选100哈希值。如何计算一组2那套100值范围内发生碰撞的可能性，因为碰撞的几率有多大？

Now say I pick 100 hashes. How do I calculate the odds of a collision within that set of 100 values, given the odds of a collision in a set of 2?

什么是一般的解决办法，让我可以拿出一些散的尝试之后，赔率低于一些可以接受的门槛？例如。我可以这样说一批49999哈希值创造了碰撞的机会很高。

What is the general solution to this, so that I can come up with a number of hash attempts after which the odds fall below some acceptable threshold? E.g. I can say things like "A batch of 49999 hash value creations has a high chance of collision".

推荐答案

这是一个泛化生日问题。

这篇关于如何计算散列算法碰撞的几率有多大？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！