Object.GetHashCode()的默认实现

对于一个类,默认值本质上是引用相等,这通常很好。如果编写结构,更常见的是重写相等(不仅仅是为了避免装箱),但无论如何编写结构是非常罕见的!

重写相等时,应始终具有匹配的 Equals() 和 GetHashCode() (即,对于两个值,如果 他们返回真的 不 必需)-并且通常还提供 == != 运营商,并经常实施 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}的哈希不同

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

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

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

InternalGetHashCode 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

全面执行 GetHashCodex 相当大,因此只需链接到 the C++ source code .

因为我找不到解释的答案 我们应该超越 GetHashCode 和 Equals this blog post ,这就解释了为什么会发生这样的问题。

我建议阅读整篇文章,但这里有一个总结(增加了重点和澄清)。

结构的默认哈希速度慢且不是很好的原因:

CLR的设计方式,对中定义的成员的每次调用 System.ValueType 或 System.Enum 类型[可能]导致 装箱分配 [...]

哈希函数的实现者面临着一个两难境地:是使哈希函数分布良好,还是使其快速。在某些情况下,两者都可以实现,但事实确实如此 ValueType.GetHashCode .

ValueType 方法是 使用反射 . 因此,CLR的作者决定在发行版和默认版本之间权衡速度 方法 只返回第一个非空字段的哈希代码 用类型id“咀嚼”它[…]这是合理的行为,除非它不是。例如, 如果运气不好,并且结构的第一个字段对于大多数实例具有相同的值,则哈希函数将提供相同的结果

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

[…]两者 ValueType.Equals ValueType.GetHashCode 有一个特殊的优化。如果某个类型没有“指针”,并且已正确打包[…],则会使用更优化的版本: 方法 迭代实例和4字节的XOR块,并 等于 方法使用 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; }
}

. 性能正常,直到集合中的元素数量显著增加,导致真正的性能问题,需要几分钟来初始化包含数万项的集合。

因此,要回答“在什么情况下我应该打包自己的,在什么情况下我可以安全地依赖默认实现”的问题,至少在 结构 等于 和 方法 Dictionary
我还建议实施 IEquatable<T> 在这种情况下,要避免拳击。

班 你需要重写 等于 方法

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

基本数据类型如下 byte , short , int long , char string Point 例如,实现一个 方法 可能适合或不适合您特定需求的方法。你只要试一下,看看是否足够好。

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

一般来说,如果要重写Equals,则需要重写GetHashCode。这是因为两者都用于比较类/结构的相等性。

如果(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应该在每个对象生命周期中只计算一次,但我不同意这一点(我可能错了)。

使用object提供的默认实现,除非您对其中一个类具有相同的引用,否则它们将彼此不相等。通过重写Equals和GetHashCode,可以基于内部值而不是对象引用报告相等性。

如果您只是在处理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;
    }
}