对字符串调用GetHashCode()时获得重复值的概率

大

(对不起乔恩!)

在短字符串之间得到哈希冲突的概率非常大。给定一组只有一万个不同的短字符串，从普通单词中提取，在这个集合中至少有一个碰撞的概率大约是1%。如果你有8万个字符串，至少发生一次碰撞的概率超过50%。

关于显示集合大小和碰撞概率之间关系的图表，请参阅我的文章:

https://learn.microsoft.com/en-us/archive/blogs/ericlippert/socks-birthdays-and-hash-collisions

小——如果你谈论的是任意两个不相等字符串发生碰撞的可能性。(当然，这取决于字符串的"任意"程度——不同的上下文将使用不同的字符串。)

大-如果你谈论的是在一个大的任意字符串池中至少有一个碰撞的可能性。小的个体概率无法与生日问题相匹配。

这就是你所需要知道的。肯定会有碰撞的情况，并且有，因为只有2³²可能的哈希码，以及更多的字符串-所以鸽子洞原理证明至少一个哈希码必须有多个字符串生成它。但是，您应该相信散列的设计是相当合理的。

您可以依赖它作为缩小特定字符串可能匹配范围的好方法。这将是一组不寻常的自然发生的字符串，它产生了大量的碰撞——即使有一些碰撞，很明显，如果你能把候选搜索集从50K缩小到不到10个字符串，那将是一个相当大的胜利。但是不能依赖于它作为任何字符串的唯一值。

请注意，. net 4中使用的算法在x86和x64之间是不同的，因此示例可能在两个平台上都无效。

我认为所有可能说的是"小，但有限，绝对不是零"——换句话说，你不能依赖于GetHashCode()曾经为两个不同的实例返回唯一的值。

在我看来，当你想要快速判断两个实例是否不同——而不是它们是否相同时，最好使用哈希码。

换句话说，如果两个对象有不同的哈希码，您知道它们是不同的，不需要进行(可能昂贵的)更深层次的比较。

但是，如果两个对象的哈希码相同，则必须继续比较对象本身，以查看它们是否实际上相同。

我在一个包含466k个英语单词的数据库上运行了一个测试，与string.GetHashCode()有48次冲突。MurmurHash的结果稍好一些。更多结果在这里:https://github.com/jitbit/MurmurHash.net

如果你的问题是指在一组字符串中碰撞的概率是多少，

对于n个可用槽位和m个占用项:
概率。第一次插入没有碰撞的概率为1。
概率。第二次插入无碰撞的概率为(n - 1)/n
概率。第三次插入无碰撞的概率为(n - 2)/n
概率。(n - (m - 1))/n

插入m次后不发生碰撞的概率是上述值的乘积:(n - 1)!/(n - m)!* n^(m - 1))

化简为(n选k)/(n^m)

每个人都是对的，你不能假设0次碰撞，所以，说概率"低"可能是对的，但不允许你假设不会有碰撞。如果你在看哈希表，我认为标准是，当哈希表满了2/3的时候，你就会遇到严重的碰撞问题。

两个随机选择的字符串碰撞的概率是1 / 2^(bits in hash code)，如果哈希是完美的，这是不太可能或不可能的。