c# - 在 Equals 覆盖中使用 GetHashCode 测试相等性

Question

可以调用 GetHashCode 作为从 Equals 覆盖内部测试相等性的方法吗？

例如，此代码是否可接受？

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;
  }
}

score 15 · Accepted Answer

其他人是对的；你的平等操作被打破了。为了显示：

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));
}

我想您希望该程序的输出为“假”，但根据您对相等性的定义，在 CLR 的某些实现中它是“真”。

请记住，只有大约 40 亿个可能的哈希码。有超过 40 亿个可能的六字母字符串，因此其中至少有两个具有相同的哈希码。我给你看了两个；还有无限多。

一般来说，您可以预期，如果有 n 个可能的哈希码，那么一旦您拥有 n 个元素的平方根，发生冲突的几率就会急剧上升。这就是所谓的“生日悖论”。对于我关于为什么不应该依赖哈希码来实现相等性的文章，请参阅：

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

score 7 · Accepted Answer

不，这不好，因为它不是

equality <=> hashcode equality.

这只是

equality => hashcode equality.

或在另一个方向：

hashcode inequality => inequality.

引用http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx：

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

score 2 · Accepted Answer

我会说，除非您想要 forEquals基本上意味着“与您的类型具有相同的哈希码”，否则no，因为两个字符串可能不同但共享相同的哈希码。概率可能很小，但不是零。

score 1 · Accepted Answer

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

score 1 · Accepted Answer

您可以调用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.
  }

score 1 · Accepted Answer

您不能仅仅因为哈希码相等就说对象必须相等。

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

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

score 0 · Accepted Answer

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

考虑您正在构建哈希表或哈希集的情况。事实上，让我们只考虑哈希集（哈希表通过保存一个值来扩展它，但这不相关）。

可以采用多种不同的方法，但在所有这些方法中，您都有少量可以放置散列值的槽，我们采用开放式或封闭式方法（只是为了好玩，有些人使用相反的术语给别人）；如果我们为两个不同的对象在同一个槽上发生碰撞，我们可以将它们存储在同一个槽中（但有一个链表等对象实际存储的位置）或重新探测以选择不同的槽（有各种策略）。

现在，无论采用哪种方法，我们都在从我们想要的哈希表的 O(1) 复杂度转向 O(n) 复杂度。这样做的风险与可用槽的数量成反比，因此在一定大小后，我们调整哈希表的大小（即使一切都很理想，如果存储的项目数大于插槽）。

在调整大小时重新插入项目显然取决于哈希码。正因为如此，虽然在一个对象中记忆很少有意义GetHashCode()（它只是在大多数对象上调用得不够频繁），但在哈希表本身中记忆它肯定是有意义的（或者也许是记忆产生的结果，例如，如果您使用 Wang/Jenkins 散列重新散列以减少由错误GetHashCode()实现造成的损害）。

现在，当我们开始插入时，我们的逻辑将类似于：

获取对象的哈希码。
获取对象的插槽。
如果插槽为空，则将对象放入其中并返回。
如果 slot 包含相等的对象，我们就完成了一个哈希集，并且可以替换哈希表的值。这样做，然后返回。
根据碰撞策略尝试下一个插槽，然后返回第 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那么这将是一种完全的浪费。如果我们的 key type where string 并且我们使用不区分大小写的 Unicode 标准化相等比较（因此它甚至不能缩短长度），那么节省可能是值得的。

通常记忆散列码是没有意义的，因为它们的使用频率不足以赢得性能，但是将它们存储在散列集或散列表本身中是有意义的。

score 0 · Accepted Answer

这是错误的实施，正如其他人所说的那样。
您应该使用以下方法短路相等性检查GetHashCode：
```
if (other.GetHashCode() != this.GetHashCode()
    return false;
```
仅当您确定随后的 Equals 实现比绝大多数情况下要昂贵得多时，才在该Equals方法中。GetHashCode
在你展示的这个实现中（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);
```

c# - 在 Equals 覆盖中使用 GetHashCode 测试相等性

8 回答 8

Related

Reference