在字符串上调用GetHashCode（）时获取重复值的概率

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

大。

（对不起乔恩！）

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

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

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

大 – 如果你在谈论在任意字符串的大池中至少发生一次碰撞的可能性。小的个人概率与生日问题不匹配。

这就是你需要知道的一切。肯定存在会发生冲突的情况，并且必须给出只有2 ^32个可能的哈希码，并且超过许多字符串 – 因此，鸽巢原则certificate至少一个哈希码必须具有多个字符串它会产生它。但是，您应该相信哈希的设计非常合理。

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

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

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

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

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

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

万一你的问题意味着一组字符串中碰撞的概率是多少，

对于n个可用插槽和m个占用项目：
概率。在第一次插入时没有碰撞是1。
概率。在第二次插入时没有碰撞是（n-1）/ n
概率。在第3次插入时没有碰撞是（n-2）/ n
概率。第m次插入时没有碰撞的是（n – （m – 1））/ n

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

这简化为（n选择k）/（n ^ m）。

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

我对466k英文单词的数据库进行了测试，并使用string.GetHashCode()获得了48次碰撞。 MurmurHash给出了稍好的结果。更多结果如下： https ： //github.com/jitbit/MurmurHash.net

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