如何在CLR和JVM中实现Object.GetHashCode()？

Question

我一直在思考这个问题:如何Object.GetHashCode在CLR或Java中实现？此方法的合同是,如果在同一对象实例上调用它,它应始终返回相同的值.

请注意,我在谈论GetHashCode()的默认实现.派生类不需要覆盖此方法.如果他们选择不这样做,它们本质上将具有引用语义:在哈希表和c中使用时,默认情况下等于"指针相等".这意味着,不知何故,运行时必须在整个生命周期内为对象提供一个常量哈希码.

如果我正在运行的机器是32位,并且如果对象实例从未在内存中移动,理论上可以返回对象的地址,重新解释为Int32.这样会很好,因为所有不同的对象都有不同的地址,因此会有不同的哈希码.

然而,这种方法存在缺陷,其中包括:

• 如果垃圾收集器将对象移动到内存中,则其地址会发生变化,因此违反协议的哈希码也会导致哈希码在对象的生命周期内应该是相同的.

• 在64位系统上,对象的地址太宽,无法容纳Int32.

• 由于托管对象倾向于与2的某个偶数幂对齐,因此最下面的位始终为零.当哈希码用于索引到哈希表时,这可能导致错误的分发模式.

在.NET中,System.Object由一个同步块和一个类型句柄组成,所以哈希码不能在实例本身中缓存.不知何故,运行时能够提供持久的哈希码.怎么样？Java,Mono和其他运行时如何做到这一点？

Answer 1

不,不是地址,不能与垃圾收集器移动对象一起使用.它直观简单,只要在生成后存储就可以是随机数.它确实存储在对象syncblk中.该字段存储多个对象属性,如果需要存储多个此类属性,则该字段将替换为已分配的syncblk的索引.

.NET算法使用托管线程ID,以便线程不可能生成相同的序列:

inline DWORD GetNewHashCode()
{
    // 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 = m_ThreadId*4 + 5;
    m_dwHashCodeSeed = m_dwHashCodeSeed*multiplier + 1;
    return m_dwHashCodeSeed;
}

种子是每线程存储的,因此不需要锁定.至少这是SSCLI20版本中使用的内容.不知道Java,我想它是相似的.