logo标签列表

如何正确地重写 object.GetHashCode()：一些通用建议和指南。

c#.nethashcodegethashcode
50
根据MSDN，哈希函数必须具备以下特性：

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

  2. 对象的GetHashCode方法必须在对象状态没有更改决定Equals方法的返回值的情况下一致地返回相同的哈希码。请注意，这仅适用于当前应用程序的执行，并且如果再次运行该应用程序，则可能返回不同的哈希码。

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

我经常遇到以下情况：我创建了一个类，实现了IEquatable<T>并重写了object.Equals(object)。MSDN指出：

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

然后我通常会卡住一些东西。因为如何正确地重写object.GetHashCode()？我从未真正知道从哪里开始，似乎有很多陷阱。 在StackOverflow这里，有很多与GetHashCode覆盖相关的问题，但大多数似乎都是关于相当特定的情况和具体问题。因此，我希望在这里获得一个好的编译。一个具有一般建议和指南的概述。该做什么、不该做什么、常见陷阱、从哪里开始等等。 我希望它特别针对C#，但我认为其他.NET语言也应该差不多吧(?)。

我认为最好的方法是每个主题创建一个答案，首先提供快速简短的答案（如果可能最好接近一行），然后可能提供更多信息，并以相关问题、讨论、博客文章等结束。如果有的话，那么我可以创建一个帖子作为已接受的答案（将其置于顶部），只包含“目录”。尽量保持简短明了。不要仅链接到其他问题和博客文章。试着摘取它们的精髓，然后链接到源代码（特别是因为源代码可能会消失）。此外，请尝试编辑和改进答案，而不是创建很多非常相似的答案。

我不是一个非常好的技术作家，但至少我会尝试格式化答案，使它们看起来像，创建目录等等。我还会尝试在这里搜索一些相关的问题，回答其中的一些部分，并可能摘出我能够处理的精髓。但由于我在这个主题上不是非常稳定，所以大部分时间我会尽量避免 ：p

11个回答
11

目录

以下是希望覆盖但尚未涉及到的内容：

  • 如何创建整数值（将对象“转换”为 int 并不明显）。
  • 应基于哪些字段生成哈希码。
    • 如果只应基于不可变字段，那么如果只有可变字段该怎么办？
  • 如何生成良好的随机分布。 (MSDN 第 3 条属性)
    • 其中一部分似乎是选择一个好的魔数（看到过使用 17、23 和 397），但怎样选择它，以及它的作用是什么？
  • 如何确保哈希码在对象生命周期内始终相同。 (MSDN 第 2 条属性)
    • 特别是当相等性基于可变字段时。 (MSDN 第 1 条属性)
  • 如何处理复杂类型的字段（不在内置的 C# 类型中）。
    • 复杂对象和结构、数组、集合、列表、字典、泛型类型等。
  • 例如，即使列表或字典是只读的，这并不意味着其中的内容也是只读的。
  • 如何处理继承类。
    • 你是否应该将base.GetHashCode()纳入到你的哈希码中？
  • 你是否可以仅仅返回0来偷懒？这会严重违反MSDN第三项指南，但至少可以确保第一条和第二条总是成立 :P
  • 常见陷阱和注意事项。
    • 8

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

    它们是质数。质数被用于创建哈希码，因为质数最大化了哈希码空间的使用。

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

    • 3 * 1 = 3 = 3(mod 8) = 0011
    • 3 * 2 = 6 = 6(mod 8) = 1010
    • 3 * 3 = 9 = 1(mod 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(mod 8) = 1001
    • 3 * 8 = 24 = 0(mod 8) = 0000
    • 3 * 9 = 27 = 3(mod 8) = 0011
    我们重新开始。但是您会注意到，我们的质数的连续倍数在开始重复之前生成了我们nybble中的每个可能位排列。我们可以使用任何质数和任意数量的位来获得相同的效果，这使得质数成为生成接近随机哈希代码的最佳选择。通常看到较大的质数而不是像上面示例中的3这样的小质数的原因是，在哈希码中有更多的位数时，使用小质数获得的结果甚至不是伪随机的-它们只是一个递增序列，直到遇到溢出。为了实现最佳随机性，应使用导致相当小系数溢出的质数，除非您可以保证您的系数不会很小。
    相关链接： - 为什么ReSharper GetHashCode override使用“397”？
    3

    为什么我需要重写 object.GetHashCode() 方法？

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

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

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

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

    相关链接：

    3
    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）。当然，这将抵消使用此类结构进行查找的任何好处。
    我可能漏掉了什么，但如果您在不同的属性中具有相同的值呢？例如，当objA.prop1 == objB.prop2且objA.prop2 == objB.prop1但objA.prop1！= objA.prop2。您可以连接字符串值，然后对其进行哈希处理。 - Eric Nicholson
    @Eric - 是的，你可以这样做，尽管上面的方法没有问题，因为虽然objA和objB具有相同的哈希码，但没有必要确保具有相同哈希码的对象是相等的，反之亦然。你的方法可能会为HashTable带来更好的性能，对于你提出的情况可能会更好。 - Lee
    2

    A) 如果要使用值相等（value equality）而不是默认的引用相等（reference equality），则必须重写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) 哈希码并不需要在对象生命周期中始终保持不变。然而，在作为哈希中的键参与时，它必须保持不可变。根据MSDN文档中Dictionary的描述：“只要一个对象在Dictionary<(Of <(TKey, TValue>)>) 中作为键使用，它就不能以任何影响其哈希值的方式进行更改。”如果必须更改键的值，请从字典中删除条目，更改键值，然后替换条目。

    D) 在我看来，如果您的值对象本身是不可变的，那么您的生活将更加简单。

    1

    何时重写 object.GetHashCode() 方法？

    正如 MSDN 所述：

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

    相关链接：

    0

    基于哪些字段生成哈希码？如果只应该基于不可变字段，那么如果只有可变字段呢？

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

    基于Svish提到的原因，将其基于不可变字段是一个好主意：“如果用作键的对象突然更改了其哈希码，则会“丢失”对象”。但我认为这取决于您使用对象的目的。 - Matthijs Wessels
    GetHashCode() 主要用于哈希表。"您不应该在可变引用类型上重写 Equals。这是因为重写 Equals 需要您还要重写 GetHashCode 方法，如前一节所述。这意味着可变引用类型实例的哈希码可以在其生命周期内发生更改，这可能会导致对象在哈希表中丢失。" https://learn.microsoft.com/en-us/dotnet/api/system.object.equals?view=netframework-4.7.2 - cactuaroid
    0

    如何确保哈希码在整个对象生命周期中保持不变。 (MSDN属性＃2) 特别是当相等性基于可变字段时。 (MSDN属性＃1)

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

    嗯...不太确定我是否理解。如果作为键的对象突然更改了其哈希码，那么你不是会“丢失”这个对象吗？ - Svish
    1
    我认为你不应该改变用作键的对象。因此，在这种意义上，基于不可变字段构建哈希是很好的。但是属性#2并没有说明这一点。这不是一个要求。 - Matthijs Wessels
    这实际上是一个要求，只是没有正式表述出来。的确，稳定的哈希码仅是Hashtable（和其他集合）实现的要求，而不是接口本身的要求，但这是一个相当强的要求。要求知道您的对象没有存储在哈希表中或更改的属性不会更改哈希值似乎是一个相当繁琐的要求（或对封装的公然无视）。因此，即使GetHashCode文档没有严格要求，不可变的哈希表也是一个实际需求。 - piers7
    我认为你不应该在Hashtable中使用这样的对象。如果对象发生了改变，equals方法也会随之改变，那么你就不能期望它得到相同的哈希值。比如说你有一个类Point，它有两个字段X和Y。假设你没有将这个类设置为不可变的，出于性能或其他原因，所以X和Y有公共的setter方法。现在你必须基于可变字段来计算哈希值。 - Matthijs Wessels
    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接