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

Question

我想知道在实例上调用GetHashCode()方法时获得重复值的概率。string例如，根据这篇博 blair文，brainlessness在 x86 机器上具有相同的哈希码 (1758039503)。

score 39 · Accepted Answer

大的。

（对不起乔恩！）

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

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

score 26 · Accepted Answer

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

大 - 如果您谈论的是在大量任意字符串中至少发生一次碰撞的可能性。小的个体概率是无法解决生日问题的。

这就是你需要知道的一切。肯定有会发生冲突的情况，并且必须给出只有 2 ^{32 个}可能的哈希码，并且超过那么多的字符串——所以鸽巢原理证明了至少一个哈希码必须有超过一个字符串生成它。但是，您应该相信哈希的设计非常合理。

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

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

score 14 · Accepted Answer

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

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

换句话说，如果两个对象具有不同的哈希码，您就知道它们是不同的，并且不需要进行（可能很昂贵）更深入的比较。

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

score 4 · Accepted Answer

我对一个包含 466k 英语单词的数据库进行了测试，并与string.GetHashCode(). MurmurHash 给出了稍微好一点的结果。更多结果在这里：https ://github.com/jitbit/MurmurHash.net

score 1 · Accepted Answer

以防万一您的问题是一组字符串中发生冲突的概率是多少，

对于 n 个可用插槽和 m 个占用项目：
概率。第一次插入时没有碰撞的概率是 1。
概率。第二次插入时没有碰撞的概率为 ( n - 1 ) / n
Prob。第 3 次插入时没有碰撞的概率是 (n - 2) / n
Prob。第 m 次插入时没有冲突的为 ( n - ( m - 1 ) ) / n

m 次插入后没有碰撞的概率是上述值的乘积：(n - 1)!/((n - m)! * n^(m - 1))。

这简化为 ( n 选择 k ) / ( n^m )。

每个人都是对的，你不能假设 0 次碰撞，所以说概率“低”可能是真的，但不允许你假设不会有碰撞。如果您正在查看哈希表，我认为标准是当您的哈希表已满 2/3 时，您开始遇到重大冲突的麻烦。

score -1 · Accepted Answer

如果哈希是完美的，那么两个随机选择的字符串之间发生冲突的概率1 / 2^(bits in hash code)是，这不太可能或不可能。

6 回答 6