49

根据MSDN，哈希函数必须具有以下属性：

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

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

  3. 为了获得最佳性能，散列函数必须为所有输入生成随机分布。

我一直在以下场景中发现自己：我创建了一个类，实现IEquatable<T>并覆盖了object.Equals(object). MSDN指出：

覆盖 Equals 的类型也必须覆盖 GetHashCode ；否则，Hashtable 可能无法正常工作。

然后它通常对我来说有点停顿。因为，您如何正确覆盖object.GetHashCode()？永远不知道从哪里开始，而且似乎有很多陷阱。

在 StackOverflow 上，有很多与 GetHashCode 覆盖相关的问题，但其中大多数似乎是针对特定情况和特定问题的。所以，因此我想在这里得到一个很好的编译。包含一般建议和指南的概述。做什么，不做什么，常见的陷阱，从哪里开始等等。

我希望它特别针对 C#，但我认为它对其他 .NET 语言的工作方式也是一样的（？）。

我认为最好的方法可能是为每个主题创建一个答案，首先是一个快速而简短的答案（如果可能的话，接近单行），然后可能是更多的信息，并以相关的问题、讨论、博客文章等结束。 ，如果有的话。然后，我可以创建一个帖子作为接受的答案（将其放在首位），只需一个“目录”。尽量保持简短和简洁。不要只链接到其他问题和博客文章。尝试获取它们的本质，然后链接到源（特别是因为源可能会消失。另外，请尝试编辑和改进答案，而不是创建许多非常相似的答案。

我不是一个很好的技术作家，但我至少会尝试格式化答案，使它们看起来相似，创建目录等。我还将尝试在 SO 上搜索一些相关问题，以回答部分问题这些，也许会提取出我可以管理的那些精髓。但由于我在这个话题上不是很稳定，我会尽量远离：p

4

11 回答 11

11

目录

我想涵盖但尚未涵盖的内容：

  • 如何创建整数（无论如何，如何将对象“转换”为 int 对我来说并不是很明显）。
  • 哈希码基于哪些字段。
    • 如果它应该只在不可变字段上，如果只有可变字段怎么办？
  • 如何生成良好的随机分布。（MSDN 属性 #3）
    • 部分原因是，似乎选择了一个很好的魔法素数（已经使用过 17、23 和 397），但是您如何选择它，它究竟是为了什么？
  • 如何确保哈希码在整个对象生命周期内保持不变。（MSDN 属性 #2）
    • 特别是当相等性基于可变字段时。（MSDN 属性 #1）
  • 如何处理复杂类型的字段（不在内置 C# 类型中）。
    • 复杂的对象和结构、数组、集合、列表、字典、泛型类型等。
    • 例如，即使列表或字典可能是只读的，但这并不意味着它的内容是只读的。
  • 如何处理继承的类。
    • 您是否应该以某种方式合并base.GetHashCode()到您的哈希码中？
  • 从技术上讲，您可以只是懒惰并返回 0 吗？会严重违反 MSDN 准则 #3，但至少会确保 #1 和 #2 始终正确：P
  • 常见的陷阱和陷阱。
于 2009-09-04T12:17:55.880 回答
8

在 GetHashCode 实现中经常看到的那些神奇数字是什么？

它们是质数。素数用于创建哈希码，因为素数最大限度地利用了哈希码空间。

具体来说，从小素数 3 开始，只考虑结果的低阶nybbles：

  • 3 * 1 = 3 = 3(mod 8) =0011
  • 3 * 2 = 6 = 6(mod 8) =1010
  • 3 * 3 = 9 = 1（模 8）=0001
  • 3 * 4 = 12 = 4(mod 8) =1000
  • 3 * 5 = 15 = 7(mod 8) =1111
  • 3 * 6 = 18 = 2(mod 8) =0010
  • 3 * 7 = 21 = 5（模 8）=1001
  • 3 * 8 = 24 = 0(mod 8) =0000
  • 3 * 9 = 27 = 3(mod 8) =0011

我们重新开始。但是您会注意到，在开始重复之前，我们的素数的连续倍数在我们的 nybble 中产生了所有可能的位排列。我们可以使用任何素数和任意位数获得相同的效果，这使得素数最适合生成近随机哈希码。在上面的例子中，我们通常看到更大的素数而不是像 3 这样的小素数的原因是，对于我们的哈希码中的更多位数，使用小素数获得的结果甚至不是伪随机的——它们只是一个递增序列直到遇到溢出。为了获得最佳随机性，应使用会导致相当小的系数溢出的素数，除非您可以保证您的系数不会很小。

相关链接：

于 2009-09-04T12:20:30.547 回答
3

为什么我必须覆盖object.GetHashCode()？

重写此方法很重要，因为以下属性必须始终保持为真：

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

正如JaredPar在关于实现平等的博客文章中所述，原因是

许多类使用哈希码对对象进行分类。特别是哈希表和字典倾向于根据它们的哈希码将对象放在桶中。当检查一个对象是否已经在哈希表中时，它将首先在存储桶中查找它。如果两个对象相等但具有不同的哈希码，则它们可能会被放入不同的桶中，并且字典将无法查找该对象。

相关链接：

于 2009-09-04T11:53:52.793 回答
3

查看Eric Lippert的 GetHashCode 指南和规则

于 2011-03-01T13:35:47.387 回答
2

每当您对该类型的对象具有有意义的相等度量时，您都应该覆盖它（即您覆盖 Equals）。如果您知道该对象不会因任何原因被散列，您可以离开它，但您不太可能提前知道这一点。

哈希应该仅基于用于定义相等的对象的属性，因为被认为相等的两个对象应该具有相同的哈希码。一般来说，您通常会执行以下操作：


public override int GetHashCode()
{
    int mc = //magic constant, usually some prime
    return mc * prop1.GetHashCode() * prop2.GetHashCode * ... * propN.GetHashCode();
}

我通常假设将这些值相乘会产生一个相当均匀的分布，假设每个属性的哈希码函数都是一样的，尽管这很可能是错误的。使用这种方法，如果对象相等定义属性发生变化，那么哈希码也可能发生变化，这是可以接受的，因为您的问题中的定义 #2。它还以统一的方式处理所有类型。

您可以为所有实例返回相同的值，尽管这会使任何使用散列（例如字典）的算法非常慢 - 基本上所有实例都将被散列到同一个桶中，然后查找将变为 O(n) 而不是预期的O(1)。这当然否定了使用这种结构进行查找的任何好处。

于 2009-09-04T11:45:37.397 回答
2

A) 如果要使用值相等而不是默认引用相等，则必须同时覆盖 Equals 和 GetHashCode。对于后者，如果两个对象引用都引用同一个对象实例，则它们比较相等。与前者相比，如果它们的值相同，即使它们引用不同的对象，它们也是相等的。例如，您可能希望对 Date、Money 和 Point 对象使用值相等。

B) 为了实现值相等，您必须重写 Equals 和 GetHashCode。两者都应该依赖于封装值的对象的字段。例如，Date.Year、Date.Month 和 Date.Day；或 Money.Currency 和 Money.Amount；或 Point.X、Point.Y 和 Point.Z。您还应该考虑覆盖运算符 ==、运算符 !=、运算符 < 和运算符 >。

C) 哈希码不必在对象生命周期内始终保持不变。但是，当它作为密钥参与散列时，它必须保持不可变。来自 Dictionary 的 MSDN doco：“只要将对象用作 Dictionary<(Of <(TKey, TValue>)>) 中的键，它就不能以任何影响其哈希值的方式发生变化。” 如果您必须更改键的值，请从字典中删除条目，更改键值并替换条目。

D）IMO，如果您的价值对象本身是不可变的，您将简化您的生活。

于 2010-05-04T21:06:59.220 回答
1

我什么时候覆盖object.GetHashCode()？

正如MSDN所说：

覆盖 Equals 的类型也必须覆盖 GetHashCode ；否则，Hashtable 可能无法正常工作。

相关链接：

于 2009-09-04T11:36:09.677 回答
1

如何生成 GetHashCode() 和 Equals()

Visual Studio 2017
https://docs.microsoft.com/en-us/visualstudio/ide/reference/generate-equals-gethashcode-methods?view=vs-2017

ReSharper
https://www.jetbrains.com/help/resharper/Code_Generation__Equality_Members.html

于 2018-10-27T14:13:11.727 回答
0

哈希码基于哪些字段？如果它应该只在不可变字段上，如果只有可变字段怎么办？

它不需要仅基于不可变字段。我将基于确定 equals 方法结果的字段。

于 2010-01-14T13:34:04.983 回答
0

如何确保哈希码在整个对象生命周期内保持不变。（MSDN 属性 #2）尤其是当相等基于可变字段时。（MSDN 属性 #1）

您似乎误解了属性 #2。哈希码不需要在对象的整个生命周期中保持不变。只要确定 equals 方法结果的值没有改变，它就需要保持不变。因此，从逻辑上讲，您仅将哈希码基于这些值。那么应该问题不大。

于 2010-01-14T13:34:26.217 回答
-2 
public override int GetHashCode()
{
    return IntProp1 ^ IntProp2 ^ StrProp3.GetHashCode() ^ StrProp4.GetHashCode ^ CustomClassProp.GetHashCode;
}

在 customClass 的GetHasCode方法中做同样的事情。奇迹般有效。

于 2009-09-19T05:38:53.347 回答