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

Question

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

Answer 1

大.

(对不起乔恩!)

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

有关显示设定大小与碰撞概率之间关系的图表,请参阅我关于此主题的文章:

http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

Answer 2

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

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

这就是你需要知道的一切.有一定情况下会出现冲突,并且有有要考虑到只有2个³²可能的散列码,而且更重要的是许多字符串-这样的鸽巢原理证明了至少一个散列码必须有一个以上的字符串生成它.但是,您应该相信哈希的设计非常合理.

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

请注意,在.NET 4中使用的算法,x86和x64之间是不同的,这样的例子可能不是这两个平台上有效.

Answer 3

我认为所有可能的说法都是"小而有限,绝对不是零" - 换句话说,你不能依赖于GetHashCode()为两个不同的实例返回唯一值.

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

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

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

Answer 4

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