默认实现的Object.GetHashCode()方法

Question

GetHashCode()的默认实现是如何工作的？它是否能够有效地处理结构、类、数组等？

我正在尝试决定在哪些情况下应该自己打包，在哪些情况下可以安全地依赖默认实现。如果可能的话，我不想重新发明轮子。

- fung

---

请看我在这篇文章上留下的评论：https://dev59.com/8nRA5IYBdhLWcg3w9y10 - Paul Westcott

请参见https://dev59.com/LHM_5IYBdhLWcg3w-4nw。 - ChrisW

注意：即使GetHashCode()被重写，您也可以使用System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(obj)来获取默认哈希码。 - Marc Gravell

@MarcGravell 谢谢您为此做出的贡献，我正在寻找这个确切的答案。 - Andrew Savinykh

@MarcGravell 但是我该如何使用其他方法来实现这个？ - Tomáš Zato

Answer 1

对于一个类，默认情况下基本上是引用相等，通常这样就可以了。如果编写结构体，则更常见的是重写相等性（至少避免装箱），但很少会编写结构体！

在重写相等性时，应始终具有匹配的Equals()和GetHashCode()（即对于两个值，如果Equals()返回true，则它们必须返回相同的哈希码，但反之则不是必需的） - 并且通常还提供==/!=运算符，并且经常实现IEquatable<T>。

---

现在，在生成哈希时，HashCode实用程序类型非常有用；例如：

return HashCode.Combine(field1, field2); // multiple overloads available here

---

如果不可用：

生成哈希码时，常用的方法是使用分解和求和，因为这可以避免在成对值上发生冲突。例如，对于基本的 2 字段哈希：

unchecked // disable overflow, for the unlikely possibility that you
{         // are compiling with overflow-checking enabled
    int hash = 27;
    hash = (13 * hash) + field1.GetHashCode();
    hash = (13 * hash) + field2.GetHashCode();
    return hash;
}

这种方法的优点是：

• {1,2} 的哈希值不同于 {2,1} 的哈希值
• {1,1} 的哈希值不同于 {2,2} 的哈希值

等等，如果仅使用未加权的总和或异或 (^) 等，则这种情况可能很常见。

- Marc Gravell

---

关于分解和求和算法的好处，这是一个非常棒的观点；这是我之前没有意识到的！ - Loophole

以上所写的因式分解和可能会引起溢出异常，不是吗？ - sinelaw

@sinelaw 是的，应该执行"unchecked"。幸运的是，在C#中，默认情况下就是“unchecked”，但最好明确指定；已编辑。 - Marc Gravell

有人可以详细解释一下选择27和13的原因吗？ - oli

@oli 相当随意，老实说；现在，我会建议使用 HashCode.Combine 代替；事实上，我会编辑这个答案。 - Marc Gravell

Answer 2

namespace System {
    public class Object {
        [MethodImpl(MethodImplOptions.InternalCall)]
        internal static extern int InternalGetHashCode(object obj);

        public virtual int GetHashCode() {
            return InternalGetHashCode(this);
        }
    }
}

InternalGetHashCode在CLR中被映射到一个名为ObjectNative::GetHashCode的函数，其代码如下：

FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {  
    CONTRACTL  
    {  
        THROWS;  
        DISABLED(GC_NOTRIGGER);  
        INJECT_FAULT(FCThrow(kOutOfMemoryException););  
        MODE_COOPERATIVE;  
        SO_TOLERANT;  
    }  
    CONTRACTL_END;  

    VALIDATEOBJECTREF(obj);  

    DWORD idx = 0;  

    if (obj == 0)  
        return 0;  

    OBJECTREF objRef(obj);  

    HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);        // Set up a frame  

    idx = GetHashCodeEx(OBJECTREFToObject(objRef));  

    HELPER_METHOD_FRAME_END();  

    return idx;  
}  
FCIMPLEND

GetHashCodeEx的完整实现非常庞大，因此更容易只链接到C++源代码。

- David Brown

---

那份文件引用一定来自于早期版本。在现有的MSDN文章中已经不再这样写了，可能是因为它相当错误。 - Hans Passant

他们改变了措辞，但基本上仍然表达同样的意思：“因此，不应将此方法的默认实现用作唯一的对象标识符以进行哈希处理。” - David Brown

为什么文档声称实现对哈希并不特别有用？如果一个对象只等于其自身，任何哈希码方法都将始终为给定的对象实例返回相同的值，并且通常会为不同的实例返回不同的值，问题出在哪里呢？ - supercat

如果您想确定一个特定的实例是否已经添加到字典中，引用相等性是完美的。对于字符串，正如您所指出的那样，人们通常更关心是否已经添加了包含相同字符序列的字符串。这就是为什么 string 覆盖了 GetHashCode。另一方面，假设您想要计算各种控件处理 Paint 事件的次数。您可以使用一个 Dictionary<Object, int[]>（每个存储的 int[] 将只保存一个项目）。 - supercat

@It'sNotALie.然后感谢Archive.org保存了一份副本；-) - RobIII

Answer 3

由于我找不到一个解释为什么我们应该重写自定义结构的GetHashCode和Equals，以及默认实现“不太适合用作哈希表中的键”的答案，我会留下这篇博客文章的链接，其中通过一个真实案例来解释为什么需要重写。

我建议阅读整篇文章，但这里有一个总结（已加粗和澄清）。

默认结构哈希值慢且不太好的原因：

CLR的设计方式是，每次调用System.ValueType或System.Enum类型中定义的成员时，都可能导致装箱分配。实现哈希函数的人面临一个困境：要么使哈希函数具有良好的分布性，要么使其快速。在某些情况下，可以同时实现两者，但是在ValueType.GetHashCode中通常难以以一般化的方式实现这一点。结构体的规范哈希函数“组合”了所有字段的哈希码。但是，在ValueType方法中获取字段的哈希码的唯一方法是使用反射。因此，CLR作者决定在速度和分布之间进行权衡，并且默认的GetHashCode版本只返回第一个非空字段的哈希码并将其与类型ID“混合”。这是一个合理的行为，除非它不是。例如，如果您的结构体的第一个字段对于大多数实例具有相同的值，则哈希函数将始终提供相同的结果。正如您所想象的那样，如果这些实例存储在哈希集或哈希表中，这将导致严重的性能影响。基于反射的实现速度很慢。非常慢。ValueType.Equals和ValueType.GetHashCode都具有特殊的优化。如果类型没有“指针”并且已正确打包[...]，则使用更优化的版本：GetHashCode迭代实例并异或4字节块，而Equals方法使用memcmp比较两个实例[...]。但是优化非常棘手。首先，很难知道何时启用了优化[...]其次，内存比较不一定会给您正确的结果。这里是一个简单的例子：[...]-0.0和+0.0相等但具有不同的二进制表示。

这篇文章描述了一个现实世界中的问题：

private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
    // Empty almost all the time
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

我们使用了一个包含自定义结构体的元组，具有默认的相等性实现。不幸的是，这个结构体有一个可选的第一个字段，几乎总是等于[空字符串]。性能还好，直到集合中的元素数量显著增加，导致真正的性能问题，需要花费几分钟来初始化包含数万个项的集合。因此，至少在结构体的情况下，当您的自定义结构体可能被用作哈希表或字典中的键时，应该重写Equals和GetHashCode。我还建议在这种情况下实现IEquatable，以避免装箱。像其他答案所说，如果你正在编写一个类，使用引用相等性的默认哈希通常是可以的，所以在这种情况下我不会打扰，除非你需要覆盖Equals（那么你必须相应地覆盖GetHashCode）。

- geekley

Answer 4

< p > GetHashCode 方法的文档对于 Object 类型说道，"默认实现不应该用作唯一的对象标识符来进行哈希运算。" 对于 ValueType 类型说道，"如果你调用派生类型的 GetHashCode 方法，返回值不太适合在哈希表中用作键。"

基本数据类型如 byte、short、int、long、char 和 string 都实现了一个良好的 GetHashCode 方法。其他一些类和结构，如 Point 例如，实现了一个可能适合你特定需求的 GetHashCode 方法。你只需要尝试一下，看看它是否足够好。

每个类或结构的文档都可以告诉你它是否覆盖了默认实现。如果没有覆盖它，你应该使用自己的实现。对于任何你自己创建的需要使用 GetHashCode 方法的类或结构，你应该编写自己的实现，使用适当的成员来计算哈希码。

- Guffa

---

我不同意你应该例行添加自己的实现。简单来说，绝大多数类（特别是）永远不会被测试相等性 - 或者在它们被测试时，内置的引用相等性就足够了。在编写结构体的（已经很少见的）情况下，这将更为常见，确实如此。 - Marc Gravell

基本数据类型没有实现一个好的 GetHashCode 方法，至少在我的情况下是这样。例如，int 的 GetHashCode 返回数字本身：(123).GetHashCode() 返回 123。 - fdermishin

@user502144 那有什么问题呢？这是一个完美的唯一标识符，易于计算，并且在相等性方面没有误报。 - Richard Rast

@Richard Rast：除了在Hashtable中使用时可能会导致键分布不良之外，一切都还好。请看这个答案：https://dev59.com/AknSa4cB1Zd3GeqPMD3L#1388329 - fdermishin

除非你的哈希表使用了超过2万亿个部分的数组，否则你必须要处理哈希值... 一般会取一个质数的模。无论如何，在现实世界中，你不太可能需要一种不同于 Dictionary<TKey, TValue> 的哈希表，因为它已经解决了这个问题。 - Casey

Answer 5

到目前为止，object的默认GetHashCode实现与对象本身无关，并且对于每个对象应该是唯一的。以下是代码：

    inline DWORD GetNewHashCode()
    {
        LIMITED_METHOD_CONTRACT;
        // Every thread has its own generator for hash codes so that we won't get into a situation
        // where two threads consistently give out the same hash codes.
        // Choice of multiplier guarantees period of 2**32 - see Knuth Vol 2 p16 (3.2.1.2 Theorem A).
        DWORD multiplier = GetThreadId()*4 + 5;
        m_dwHashCodeSeed = m_dwHashCodeSeed*multiplier + 1;
        return m_dwHashCodeSeed;
    }

以下是调用堆栈：

Thread::GetNewHashCode

Object::ComputeHashCode

Object::GetHashCodeEx

- lty

Answer 6

一般来说，如果您重写了Equals方法，那么您需要重写GetHashCode方法。原因是两者都用于比较类/结构体的相等性。

在检查Foo A、B是否相等时，会使用Equals方法：

if (A == B)

由于我们知道指针不太可能匹配，因此我们可以比较内部成员。

Equals(obj o)
{
    if (o == null) return false;
    MyType Foo = o as MyType;
    if (Foo == null) return false;
    if (Foo.Prop1 != this.Prop1) return false;

    return Foo.Prop2 == this.Prop2;
}

GetHashCode通常用于哈希表。您的类生成的哈希码应始终对于给定状态的类相同。

我通常这样做，

GetHashCode()
{
    int HashCode = this.GetType().ToString().GetHashCode();
    HashCode ^= this.Prop1.GetHashCode();
    etc.

    return HashCode;
}

有些人会说hashcode应该只在对象生命周期内计算一次，但我不同意这个观点（也许我是错的）。

使用对象提供的默认实现，除非你有对你的类的相同引用，否则它们将不相等。通过重写Equals和GetHashCode，可以基于内部值而不是对象引用报告相等性。

- Ben

---

“^=”方法不是生成哈希的特别好的方法，它往往会导致许多常见/可预测的冲突 - 例如，如果Prop1 = Prop2 = 3。” - Marc Gravell

如果值相同，我认为碰撞没有问题，因为对象是相等的。不过，13 * Hash + NewHash 看起来很有趣。 - Bennett Dill

请尝试使用Obj1 { Prop1 = 12, Prop2 = 12 }和Obj2 { Prop1 = 13, Prop2 = 13 }进行测试。 - Tomáš Kafka

Answer 7

如果您只处理POCOs，您可以使用此实用程序来简化您的工作：

var hash = HashCodeUtil.GetHashCode(
           poco.Field1,
           poco.Field2,
           ...,
           poco.FieldN);

...

public static class HashCodeUtil
{
    public static int GetHashCode(params object[] objects)
    {
        int hash = 13;

        foreach (var obj in objects)
        {
            hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
        }

        return hash;
    }
}

- Dan Marshall