使用GetHashCode在Equals重写中测试相等性

Question

在Equals重写方法中，调用GetHashCode作为测试相等性的方法是否可行？

例如，这段代码是否可接受？

public class Class1
{
  public string A
  {
    get;
    set;
  }

  public string B
  {
    get;
    set;
  }

  public override bool Equals(object obj)
  {
    Class1 other = obj as Class1;
    return other != null && other.GetHashCode() == this.GetHashCode();
  }

  public override int GetHashCode()
  {
    int result = 0;
    result = (result ^ 397) ^ (A == null ? 0 : A.GetHashCode());
    result = (result ^ 397) ^ (B == null ? 0 : B.GetHashCode());
    return result;
  }
}

- Armbrat

---

作为开发人员，您应该充分了解何时使用哈希以及它们与哈希表的关系（由Dictionary和HashSet等实现）。 hashtable的维基百科文章是一个不错的起点：http://en.wikipedia.org/wiki/Hash_table - spender

@spender - 这正是这个问题向我解释的比我最初理解或能够回忆起的更详细的内容。 - Armbrat

不仅等式检查错误，代码也很奇怪。为什么要将零乘以397？我可以告诉你，答案肯定是零，所以为什么要让机器计算它呢？为什么要将零与一个值进行异或运算；这只是一个恒等操作而已。 - Eric Lippert

是的，那很愚蠢。我已经纠正了，希望现在是正确的。 - Armbrat

也应该看到这个 为什么要使用GetHashCode而不是Equals - nawfal

Answer 1

其他人是正确的，你的相等操作有问题。举个例子：

public static void Main()
{
    var c1 = new Class1() { A = "apahaa", B = null };
    var c2 = new Class1() { A = "abacaz", B = null };
    Console.WriteLine(c1.Equals(c2));
}

我猜想您希望该程序的输出为“false”，但根据CLR的某些实现，使用您的等式定义其结果为“true”。

请记住，哈希码只有大约40亿种可能。有比40亿个六位字符串更多的可能性，因此至少有两个字符串具有相同的哈希码。我向您展示了其中两个，还有无限多个。

通常情况下，如果有n个可能的哈希码，则在使用约根号n个元素时，发生碰撞的概率迅速上升。这就是所谓的“生日悖论”。关于为什么不应该依赖哈希码进行相等判断的文章，请点击这里。

- Eric Lippert

Answer 2

不，这不行，因为它并不是“相等性<=>哈希码相等性”。它只是“相等性=>哈希码相等性”，或者反过来，“哈希码不相等=>不相等”。引用自http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx：“如果两个对象比较相等，则每个对象的GetHashCode方法必须返回相同的值。但是，如果两个对象不相等，则两个对象的GetHashCode方法不必返回不同的值。”

- ulrichb

Answer 3

我认为，除非你希望Equals基本上意味着“具有与之相同的哈希码”对于你的类型，否则不行，因为两个字符串可能不同但共享相同的哈希码。这种情况发生的概率可能很小，但不为零。

- Dan Tao

Answer 4

这不是一种可接受的测试相等性的方式。两个不相等的值很可能具有相同的哈希码。这将导致您实现的Equals在应该返回false时返回true

- JaredPar

Answer 5

你不能仅仅因为哈希码相等就认为对象是相等的。

唯一的情况是，如果计算对象的哈希值比检查相等性要便宜得多（例如，因为你缓存了它），那么你才会在Equals内部调用GetHashCode。在这种情况下，你可以说if (this.GetHashCode() != other.GetHashCode()) return false;以便快速验证对象是否不相等。

那么什么时候会这样做呢？我编写了一些代码，定期拍摄屏幕截图，并尝试找出自上次更改屏幕以来的时间。由于我的屏幕截图大小为8MB，而且在屏幕截图间隔内变化的像素相对较少，因此在搜索它们的列表中查找相同的屏幕截图相当昂贵。哈希值很小，每个屏幕截图只需要计算一次，因此很容易消除已知的非相等项。实际上，在我的应用程序中，我决定具有相同哈希值足以被视为相等，因此我甚至没有费心去实现Equals重载，导致C#编译器警告我正在重载GetHashCode而没有重载Equals。

- Gabe

Answer 6

您可以调用GetHashCode来确定项目是否不相等，但如果两个对象返回相同的哈希码，这并不意味着它们相等。两个项目可以具有相同的哈希码，但不相等。

如果比较两个项目很昂贵，那么可以比较哈希码。如果它们不相等，那么可以退出。否则（哈希码相等），您必须进行完整的比较。

例如：

public override bool Equals(object obj)
  {
    Class1 other = obj as Class1;
    if (other == null || other.GetHashCode() != this.GetHashCode())
        return false;
    // the hash codes are the same so you have to do a full object compare.
  }

- Jim Mischel

---

使用许多对象时，这通常比使用内置比较要慢。如果对象相等，则最终会进行完整的比较和GetHashCode。如果它们不相等，则最终会调用GetHashCode，这可能会读取整个对象。另一方面，Equals可能仅读取足够的对象来确定对象不相等。话虽如此，在比较缓慢但具有快速GetHashCode方法（例如因为它是预先计算的）的复杂对象的情况下，此优化将非常有帮助。 - Brian

@Brian，我同意你的观点，出于你所说的原因，这种方法很少有用。我也认为预先计算的GetHashCode很少有用（尤其是如果你使用的是IEqualityComparer实现而不是默认的GetHashCode，那么它就更加不常用了）。然而，请看我的答案，其中提到了一种情况，即即使出于其他原因存储哈希码，Jim的方法仍然是有意义的。 - Jon Hanna

Answer 7

1. 这是错误的实现，正如其他人所说的。

2. 您应该使用GetHashCode来短路等式检查，例如：

   if (other.GetHashCode() != this.GetHashCode()
       return false;
   

   在Equals方法中仅当您确定随后的Equals实现比GetHashCode更昂贵时，而这并不是绝大多数情况。

3. 在您展示的这个实现中（99％的情况），它不仅有问题，而且速度也慢得多。 原因是？计算属性的哈希值几乎肯定比比较它们要慢，因此您甚至没有在性能方面获得优势。 实现适当的GetHashCode的优点在于，当您的类可以成为哈希表的键类型时，哈希只计算一次（并且该值用于比较）。 在您的情况下，如果它在集合中，则会多次调用GetHashCode。 即使GetHashCode本身应该很快，但它通常不比等效的 Equals更快。

   要进行基准测试，请在此处运行您的Equals（一个适当的实现，将当前基于哈希的实现排除在外）和GetHashCode

   var watch = Stopwatch.StartNew();
   for (int i = 0; i < 100000; i++) 
   {
       action(); //Equals and GetHashCode called here to test for performance.
   }
   watch.Stop();
   Console.WriteLine(watch.Elapsed.TotalMilliseconds);
   

- nawfal

Answer 8

有一种情况下，使用哈希码作为相等比较的快捷方式是有意义的。

考虑构建哈希表或哈希集合的情况。实际上，让我们只考虑哈希集合（哈希表通过还保存值来扩展，但这并不相关）。

有各种不同的方法可以采取，但在所有方法中，您都有一小部分插槽可用于放置哈希值，并且我们采用开放或封闭的方法（仅仅是为了好玩，有些人使用相反的术语）。如果我们在两个不同对象的相同插槽上发生碰撞，我们可以将它们存储在同一个插槽中（但是需要链表或类似的东西来存储实际存储的对象），或者重新探测以选择另一个插槽（有各种策略可供选择）。

现在，无论采用哪种方法，我们都会远离哈希表所需的O(1)复杂度，而向O(n)复杂度靠近。这种风险与可用插槽数量成反比，因此在一定大小后，我们会调整哈希表的大小（即使一切理想，如果存储的项目数大于插槽数，我们最终也必须这样做）。

重新调整大小时重新插入项目显然取决于哈希码。因此，虽然在对象中很少有必要记忆GetHashCode()（大多数对象上不经常调用它），但在哈希表本身内部记忆它肯定是有意义的（或者，记忆一个生成的结果，例如如果您使用Wang/Jenkins哈希重新哈希以减少由糟糕的GetHashCode()实现引起的损坏）。

现在，当我们来插入时，我们的逻辑将是：

1. 获取对象的哈希码。
2. 获取对象的插槽。
3. 如果插槽为空，请将对象放入其中并返回。
4. 如果插槽包含相等的对象，则对于哈希集合我们已完成，并且具有替换哈希表值的位置。执行此操作，并返回。
5. 根据碰撞策略尝试下一个插槽，并返回到第3项（如果我们循环太多次，则可能调整大小）。

因此，在这种情况下，我们必须在比较相等性之前获取哈希码。我们还预先计算了现有对象的哈希码以允许调整大小。这两个事实的组合意味着，我们可以将第4项的比较实现为：

private bool IsMatch(KeyType newItem, KeyType storedItem, int newHash, int oldHash)
{
  return ReferenceEquals(newItem, storedItem) // fast, false negatives, no false positives (only applicable to reference types)
    ||
    (
      newHash == oldHash // fast, false positives, no fast negatives
      &&
      _cmp.Equals(newItem, storedItem) // slow for some types, but always correct result.
    );
}

显然，这取决于_cmp.Equals的复杂性。 如果我们的键类型是int，那么这将是完全浪费。 如果我们的键类型是字符串，并且我们使用不区分大小写的Unicode规范化等式比较（因此甚至不能在长度上进行快捷方式），那么节省的时间可能是值得的。

通常情况下，备忘哈希码没有意义，因为它们不经常使用，无法提高性能，但将它们存储在哈希集或哈希表本身中是有意义的。

- Jon Hanna