string.GetHashCode()唯一性和冲突

Question

鉴于两个不同的字符串,总是这样s.GetHashCode() != s1.GetHashCode()吗？

是不是整数的数量小于不同字符串的数量？

Answer 1

号就像一个简单的思想实验:有多少串在那里(提示:许多超过2 ³²,因此多少独特的哈希码才能有(提示:2 ³².看这个问题？)

哈希码只要求是平等的,只要Equals回报率,这两个对象是相等的.此外,每当两个哈希码不相等时,则对象本身不能相等.没有进一步的要求,但它们应该分布良好,以便哈希表可以很好地执行.所以基本上它是:

请注意省略相应的⇐变体.它不是等价的,仅仅是两个含义.

引用文档:

哈希函数必须具有以下属性:

1. 如果两个对象比较相等,则每个对象的GetHashCode方法必须返回相同的值.但是,如果两个对象的比较不相等,则两个对象的GetHashCode方法不必返回不同的值.

2. 只要没有对对象状态的修改来确定对象的Equals方法的返回值,对象的GetHashCode方法必须始终返回相同的哈希代码.请注意,这仅适用于当前应用程序的执行,并且如果再次运行应用程序,则可以返回不同的哈希代码.

3. 为获得最佳性能,哈希函数必须为所有输入生成随机分布.

Answer 2

要添加到@ Joey的语句,您主要不能使哈希码始终不相等.

有2 ^ 32个可能的哈希码但是无限的输入字符串.

保证散列冲突具有足够的(2 ^ 32 + 1)输入值.

实际上,由于生日问题,哈希冲突比人们想象的要普遍得多.当我做数学而回为使用64个的散列码系统(其中有办法比32位的散列码更可能哈希值,不只是加倍作为一个可能天真地认为),1亿的输入值是非常可能会有至少1个哈希冲突.我认为概率约为1%.