27

ValueType.cs

**操作:我们返回哈希码的算法有点复杂。我们看
** 对于第一个非静态字段并获取它的哈希码。如果类型没有
** 非静态字段,我们返回类型的哈希码。我们不能接受
** 静态成员的哈希码,因为如果该成员与
** 原始类型,我们将陷入无限循环。

今天,当我使用 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();
}

我猜第一个非静态字段意味着声明顺序中的第一个字段,这也可能在出于任何原因更改源中的变量顺序时造成麻烦,并且相信它不会在语义上更改代码。

4

5 回答 5

45

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

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

未能通过该测试,它会执行慢速版本,相当于反思的道德。这就是你得到的,你的 KeyValuePair<> 包含引用。正如评论所说,这个只检查第一个候选字段。这肯定是一个性能优化,避免浪费太多时间。

是的,令人讨厌的细节,并不广为人知。当有人注意到他们的收藏代码很烂时,通常会发现它。

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

于 2010-10-01T19:43:47.050 回答
35

更新:这个答案(部分)是我写的一篇博客文章的基础,该文章详细介绍了GetHashcode. 感谢您提出有趣的问题!


我没有实施它,也没有与实施它的人交谈。但我可以指出几点。

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

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

那么,除了该合同之外,还有哪些“值得拥有的东西”呢?一个好的哈希码实现应该是:

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

2) 对于给定的输入分布,在 32 位整数空间中分布良好。整数之间的分布越差,哈希表就越像简单的线性查找。

那么,考虑到这两个相互冲突的目标,你将如何为任意值类型创建哈希算法呢?任何时间花在保证良好分布的复杂哈希算法上都是浪费时间。

一个常见的建议是“对所有字段进行哈希处理,然后对生成的哈希码进行异或运算”。但这是在乞求问题;对两个 32 位整数进行异或仅在输入本身分布非常好且彼此不相关时才能提供良好的分布,这是不太可能的情况:

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

x 和 y 在整个 32 位整数范围内均匀分布的可能性有多大?非常低。它们既靠近彼此的可能性要好得多,在这种情况下,将它们的哈希码异或在一起会使事情变得更糟,而不是更好。将彼此接近的整数异或在一起会使大多数位为零。

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

基本上我们在这里的情况是用户自己没有提供哈希码实现;要么他们不在乎,要么他们不希望这种类型被用作哈希表中的键。鉴于您没有关于该类型的任何语义信息,最好的办法是什么?最好的办法是在大多数情况下速度快且效果好。

大多数时候,两个不同的结构实例在它们的大部分字段中都会有所不同,而不仅仅是其中一个字段,因此只需选择其中一个并希望它是不同的那个似乎是合理的。

大多数情况下,两个不同的结构实例在它们的字段中会有一些冗余,因此将许多字段的哈希值组合在一起可能会减少而不是增加哈希值中的熵,即使它消耗了哈希算法是为了保存而设计的。

将此与 C# 中匿名类型的设计进行比较。对于匿名类型,我们确实知道该类型很可能被用作表的键。我们确实知道匿名类型的实例之间很有可能存在冗余(因为它们是笛卡尔积或其他连接的结果)。因此,我们确实将所有字段的哈希码组合成一个哈希码。如果由于计算的哈希码数量过多而导致性能不佳,则可以自由使用自定义名义类型而不是匿名类型。

于 2010-10-01T18:04:44.293 回答
9

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

尤其:

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

现在我并不是说 ValueType 的实现是一个好主意——它会以各种方式导致性能下降……但我认为它实际上并没有坏掉

于 2010-10-01T17:32:27.550 回答
3

好吧,任何实现GetHashCode(). 这些当然是我们在实现自己的时候权衡的事情,但是在这种情况下ValueType.GetHashCode()存在一个特别的困难,因为他们没有太多关于具体类型的实际细节的信息。当然,当我们创建一个抽象类或一个旨在成为类的基础的抽象类时,这经常发生在我们身上,这些类将在状态方面增加更多,但在这些情况下,我们有一个明显的解决方案,即只使用默认实现object.GetHashCode()除非派生类愿意在那里重写它。

由于ValueType.GetHashCode()他们没有这种奢侈,因为值类型和引用类型之间的主要区别在于,尽管谈论堆栈与堆的实现细节很受欢迎,但对于值类型等价与值相关的事实,而对于一个对象类型等价与身份相关(即使对象通过覆盖定义了不同形式的等价,Equals()并且GetHashCode()引用相等的概念仍然存在并且仍然有用。

因此,对于该Equals()方法,实现是显而易见的;检查这两个对象的类型是否相同,如果是,则还要检查所有字段是否相等(实际上有一个优化,在某些情况下会进行按位比较,但这是基于相同基本思想的优化)。

做什么GetHashCode()? 根本没有完美的解决方案。他们可以做的一件事是在每个字段上进行某种 mult-then-add 或 shift-then-xor。这可能会给出一个非常好的哈希码,但如果有很多字段可能会很昂贵(不要介意不建议使用具有很多字段的值类型,实现者必须考虑它们仍然可以,而且确实如此甚至有时它是有意义的,尽管老实说我无法想象它既有意义又对它进行散列也有意义的时候)。如果他们知道实例之间的某些字段很少有差异,他们可以忽略这些字段并且仍然具有相当好的哈希码,同时也非常快。最后,他们可以忽略大多数字段,并希望他们不会忽略的字段在大多数情况下的价值是不同的。

(当没有实例字段时做什么是另一回事,也是一个很好的选择,这样的值类型等于所有其他相同类型的实例,并且它们有一个与之匹配的哈希码)。

因此,如果您在第一个字段相同(或返回相同哈希码)的情况下对大量值进行散列处理,这是一个很糟糕的实现,但在其他情况下其他实现会很糟糕(Mono 将所有字段的哈希码异或在一起,在你的情况下更好,在其他情况下更糟)。

更改字段顺序的问题并不重要,因为哈希码已明确说明仅在进程的生命周期内保持有效,并且不适用于大多数情况下它们可以持续存在的情况(在某些缓存情况下可能很有用如果在代码更改后找不到正确的东西,也没有什么坏处)。

所以,不是很好,但没有什么是完美的。它表明,当使用对象作为键时,必须始终考虑“平等”意味着什么的两面。在您的情况下,它很容易通过以下方式修复:

public class KVPCmp<TKey, TValue> : IEqualityComparer<KeyValuePair<TKey, TValue>>, IEqualityComparer
{
  bool IEqualityComparer.Equals(object x, object y)
  {
      if(x == null)
        return y == null;
      if(y == null)
        return false;
      if(!(x is KeyValuePair<TKey, TValue>) || !(y is KeyValuePair<TKey, TValue>))
        throw new ArgumentException("Comparison of KeyValuePairs only.");
      return Equals((KeyValuePair<TKey, TValue>) x, (KeyValuePair<TKey, TValue>) y);
  }
  public bool Equals(KeyValuePair<TKey, TValue> x, KeyValuePair<TKey, TValue> y)
  {
      return x.Key.Equals(y.Key) && x.Value.Equals(y.Value);
  }
  public int GetHashCode(KeyValuePair<TKey, TValue> obj)
  {
      int keyHash = obj.GetHashCode();
      return ((keyHash << 16) | (keyHash >> 16)) ^ obj.Value.GetHashCode();
  }
  public int GetHashCode(object obj)
  {
      if(obj == null)
        return 0;
      if(!(obj is KeyValuePair<TKey, TValue>))
       throw new ArgumentException();
      return GetHashCode((KeyValuePair<TKey, TValue>)obj);
  }
}

在创建字典时使用它作为比较器,一切都应该很好(你只需要真正的通用比较器方法,但将其余的留在没有害处,有时会有用)。

于 2010-10-01T17:59:05.987 回答
0

谢谢大家非常非常有用的答案。我知道该决定必须有一些理由,但我希望它被更好地记录下来。我无法使用框架的 v4,所以没有,这就是我决定搭载structTuple<>的主要原因。KeyValuePair但我想没有偷工减料,我必须自己动手。再次感谢大家。

于 2010-10-02T14:15:56.443 回答