Object.GetHashCode（）的默认实现

问题描述 投票：145回答：6

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

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

.net hash gethashcode
6个回答
83
投票
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的完整实现相当大，因此更容易链接到the C++ source code。

83
投票

对于一个类，默认值基本上是引用相等，这通常很好。如果编写一个结构，更常见的是覆盖相等（尤其是避免装箱），但是你编写一个结构是非常罕见的！

当重写相等时，你应该总是有一个匹配的Equals()和GetHashCode()（即两个值，如果Equals()返回true，它们必须返回相同的哈希码，但不需要反过来） - 并且通常也提供== / !=operators ，并经常实施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（^）等，这可能很常见。

7
投票

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

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

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

4
投票

由于我找不到解释为什么我们应该为自定义结构覆盖GetHashCode和Equals以及为什么默认实现“不太可能适合用作哈希表中的键”的答案，我将留下一个链接this blog post，它解释了为什么会出现问题的实例。

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

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

CLR的设计方式，每次调用System.ValueType或System.Enum类型中定义的成员[可]导致拳击分配[...]

散列函数的实现者面临一个两难问题：对散列函数进行良好的分配或使其快速。在某些情况下，它们都可以实现它们，但在ValueType.GetHashCode中很难做到这一点。

结构的规范哈希函数“组合”所有字段的哈希码。但是，在ValueType方法中获取字段哈希码的唯一方法是使用反射。因此，CLR作者决定在分布上交易速度，默认的GetHashCode版本只返回第一个非空字段的哈希码，并使用类型id“...”对其进行“管理”这是一种合理的行为，除非它是不。例如，如果你运气不够并且结构的第一个字段对于大多数实例具有相同的值，那么哈希函数将始终提供相同的结果。而且，正如您可能想象的那样，如果这些实例存储在哈希集或哈希表中，这将导致严重的性能影响。

[...]基于反射的实施很慢。非常慢。

[...] ValueType.Equals和ValueType.GetHashCode都有一个特殊的优化。如果一个类型没有“指针”并且被正确打包[...]则使用更优的版本：GetHashCode迭代一个实例和4个字节的XORs块，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作为哈希表或Dictionary中的键。 我还建议在这种情况下实施IEquatable<T>，以避免拳击。

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

1
投票

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

检查Foo A，B时使用等于;

如果（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，您可以根据内部值而不是对象引用来报告相等性。

0
投票

如果您只是处理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;
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.