为什么ValueType.GetHashCode()实现得像？

Question

从 ValueType.cs

**Action: Our algorithm for returning the hashcode is a little bit complex. We look 
**        for the first non-static field and get it's hashcode.  If the type has no 
**        non-static fields, we return the hashcode of the type. We can't take the
**        hashcode of a static member because if that member is of the same type as 
**        the original type, we'll end up in an infinite loop.

今天当我使用KeyValuePair作为字典中的键(它存储了xml属性名称(枚举)和它的值(字符串))时,我被它咬了,并期望它根据其所有字段计算它的哈希码,但根据实施情况,它只考虑了关键部分.

示例(来自Linqpad的c/p):

void Main()
{
    var kvp1 = new KeyValuePair<string, string>("foo", "bar");
    var kvp2 = new KeyValuePair<string, string>("foo", "baz");

    // true
    (kvp1.GetHashCode() == kvp2.GetHashCode()).Dump();
}

我猜的第一个非静态字段意味着声明顺序中的第一个字段,这也可能因为任何原因在源中更改变量顺序而导致麻烦,并且认为它不会在语义上更改代码.

Answer 1

ValueType.GetHashCode()的实际实现与注释不完全匹配.它有两个版本的算法,快速和慢速.它首先检查结构是否包含引用类型的任何成员以及字段之间是否有任何填充.填充是结构值中的空白空间,在JIT编译器对齐字段时创建.在包含bool和int(3个字节)的结构中有填充,但是当它包含int和int时没有填充,它们紧密地结合在一起.

没有引用和没有填充,它可以执行快速版本,因为结构值中的每个位都是属于字段值的位.它一次只需4个字节.您将获得一个考虑所有成员的"好"哈希码..NET框架中的许多简单结构类型都以这种方式运行,如Point和Size.

如果没有通过测试,那就是慢速版本,反思的道德等价物.这就是你得到的,你的KeyValuePair <>包含引用.而这个只检查第一个候选字段,就像评论所说的那样.这肯定是一个性能优化,避免燃烧太多时间.

是的,令人讨厌的细节而不是众所周知的.当有人注意到他们的收集代码糟透了时,通常会发现它.

另一个令人难以忍受的细节:当结构包含十进制类型的字段时,快速版本有一个字节错误.12m和12.0m的值在逻辑上相等,但它们没有相同的位模式.GetHashCode()会说它们不相等.哎哟.

Answer 2

我没有实现它,我没有和那些做过的人交谈过.但我可以指出一些事情.

(在我继续之前,请注意,我在这里专门讨论用于平衡哈希表的哈希码,其中表的内容由非恶意用户选择.用于数字签名,冗余检查的哈希码的问题,或者当某些用户对表提供程序进行拒绝服务攻击时,确保哈希表的良好性能超出了本讨论的范围.)

首先,正如Jon正确指出的那样,给定的算法确实实现了GetHashCode所需的合同.它可能不是您的目的,但它是合法的.所需要的只是比较相等的东西具有相同的哈希码.

那么除了合同之外,还有什么"好东西"呢？一个好的哈希代码实现应该是:

1)快.非常快!请记住,首先,哈希码的重点是在哈希表中快速找到一个相对空的槽.如果散列码的O(1)计算实际上比天真地进行查找所花费的O(n)时间慢,那么散列码解决方案是净损失.

2)针对给定的输入分布,在32位整数空间内分布均匀.整个int的分布越差,就越像哈希表的天真线性查找.

那么,在给定这两个相互冲突的目标的情况下,如何为任意值类型制作哈希算法？任何时候你花在一个复杂的哈希算法上,保证良好的分布花费的时间很少.

一个常见的建议是"散列所有字段,然后将得到的哈希码与XOR一起".但那是在乞求这个问题; 当输入本身非常均匀且彼此不相关时,对两个32位整数进行异或运算只能提供良好的分布,这是不太可能的情况:

// (Updated example based on good comment!)
struct Control
{
    string name;
    int x;
    int y;
}

x和y在整个32位整数范围内均匀分布的可能性是多少？非常低.它们很小并且彼此接近的情况要好得多,在这种情况下,将它们的哈希码合并在一起会使事情变得更糟,而不是更好.将彼此接近的整数放在一起使大多数位都归零.

此外,这是字段数量的O(n)!具有许多小字段的值类型将花费相对长的时间来计算哈希码.

基本上我们在这里的情况是用户自己没有提供哈希码实现; 要么他们不关心,要么他们不希望这种类型被用作哈希表中的密钥.鉴于您没有任何关于类型的语义信息,最好的做法是什么？最好的事情是快速,并在大多数时间提供良好的结果.

大多数情况下,两个不同的结构实例在它们的大多数字段中都不同,而不仅仅是它们的一个字段,所以只选择其中一个并希望它是不同的那个似乎是合理的.

大多数时候,是不同的两种结构实例将在各自领域的一些冗余,所以结合许多领域的哈希值加在一起可能会降低,不会增加,熵的哈希值,甚至因为它消耗的时间,即哈希算法旨在保存.

将其与C#中的匿名类型设计进行比较.匿名类型,我们都知道这是很有可能的类型被用作一个关键的表.我们都知道,这是极有可能会出现跨越匿名类型的实例冗余(因为他们是笛卡尔积的结果或其它连接).因此,我们将所有字段的哈希码组合成一个哈希码.如果让你表现不好,由于过多数量被计算哈希码,您可以自由使用自定义的名义类型,而不是匿名类型.

Answer 3

GetHashCode即使字段顺序发生变化,它仍应遵守合同:在该过程的生命周期内,相等的值将具有相等的哈希码.

特别是:

• 不相等的值不必具有不相等的哈希码
• 散列代码不必跨进程保持一致(您可以更改实现,重建,并且一切都应该仍然有效 - 基本上您不应该持久化哈希代码)

现在我并不是说ValueType的实现是一个好主意 - 它会以各种方式引起性能损失......但我认为它实际上并没有被破坏.