Object.GetHashCode()的默认实现

Question

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

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

Answer 1

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

Answer 2

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

当重写等式,你应该始终有一个匹配的Equals()和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(^)等,这可能很常见.

Answer 3

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

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

结构的默认散列很慢并且不是很好的原因：

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

散列函数的实现者面临着两难选择：对散列函数进行良好的分布还是使其快速。在某些情况下，有可能实现他们两个，但它是很难笼统做到这一点在ValueType.GetHashCode。

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

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

[...]两者ValueType.Equals并ValueType.GetHashCode有专门的优化。如果一个类型没有“指针”并且被正确打包 [...] 然后使用更优化的版本：GetHashCode迭代一个实例和 4 个字节的 XOR 块和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; }
}

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

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

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

Answer 4

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

基本数据类型,例如byte,short,int,long,char以及string实现良好的GetHashCode方法.其他一些类和结构(Point例如,实现GetHashCode可能适合或不适合您的特定需求的方法).你只需要试一试,看看它是否足够好.

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