.net - Object.GetHashCode() 的默认实现

Question

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

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

score 94 · Accepted Answer

对于一个类，默认值本质上是引用相等，这通常很好。如果编写一个结构体，更常见的是重写相等性（尤其是为了避免装箱），但无论如何你都很少写一个结构体！

当覆盖相等性时，您应该始终有一个匹配的Equals()and GetHashCode()（即对于两个值，如果Equals()返回 true，它们必须返回相同的哈希码，但不需要相反） - 通常还提供==/!=运算符，并且经常也实施IEquatable<T>。

为了生成哈希码，通常使用因式总和，因为这样可以避免配对值的冲突——例如，对于基本的 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} 的哈希不同

等 - 如果仅使用未加权和或 xor ( ^) 等，这可能很常见。

score 90 · Accepted Answer

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++ 源代码。

score 10 · Accepted Answer

由于我找不到解释为什么我们应该重写GetHashCode和Equals自定义结构以及为什么默认实现“不太可能适合用作哈希表中的键”的答案，我将留下一个指向此博客的链接post，它通过一个实际发生的问题示例来解释原因。

我建议阅读整篇文章，但这里是一个摘要（添加了重点和说明）。

结构的默认哈希值很慢而且不是很好的原因：

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

我们使用了一个元组，其中包含一个具有默认相等实现的自定义结构。不幸的是，该结构有一个可选的第一个字段，几乎总是等于 [empty string]。性能还可以，直到集合中的元素数量显着增加导致真正的性能问题，需要几分钟来初始化包含数万个项目的集合。

因此，要回答“在什么情况下我应该自己打包以及在什么情况下我可以安全地依赖默认实现”的问题，至少在structs的情况下，您应该覆盖Equals并且GetHashCode每当您的自定义结构可能用作键入哈希表或Dictionary.
我还建议IEquatable<T>在这种情况下实施，以避免拳击。

正如其他答案所说，如果您正在编写一个class，使用引用相等的默认哈希通常很好，所以在这种情况下我不会打扰，除非您需要覆盖Equals（然后您必须GetHashCode相应地覆盖）。

score 7 · Accepted Answer

ObjectGetHashCode方法的文档说“此方法的默认实现不得用作散列目的的唯一对象标识符。” 而ValueType则说“如果调用派生类型的 GetHashCode 方法，则返回值不太可能适合用作哈希表中的键。” .

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

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

score 2 · Accepted Answer

一般来说，如果您要覆盖 Equals，则需要覆盖 GetHashCode。这样做的原因是因为两者都用于比较您的类/结构的相等性。

检查 Foo A, B 时使用 Equals；

如果（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;
}

有人会说，每个对象生命周期只应计算一次哈希码，但我不同意这一点（我可能错了）。

使用 object 提供的默认实现，除非您对某个类具有相同的引用，否则它们将不相等。通过覆盖 Equals 和 GetHashCode，您可以根据内部值而不是对象引用来报告相等性。

score 0 · Accepted Answer

如果您只是在处理 POCO，则可以使用此实用程序来简化您的生活：

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

.net - Object.GetHashCode() 的默认实现

6 回答 6

Related

Reference