如何在CLR和JVM中实现Object.GetHashCode（）？

我一直在沉思这一段时间：在CLR或Java中究竟是如何实现Object.GetHashCode？该方法的契约是，如果它在同一个对象实例上被调用，它应该总是返回相同的值。如何在CLR和JVM中实现Object.GetHashCode（）？

请注意，我在谈论GetHashCode（）的默认实现。派生类不需要重写此方法。如果他们选择不这样做，他们实质上将具有引用语义：在哈希表中使用时，默认情况下，默认情况下“默认等于”指针相等“& c。这意味着，运行时不得不在整个生命周期中为对象提供一个恒定的哈希码。

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

但是，这种方法是有缺陷的，除其他事情，因为：

如果垃圾收集器在内存中移动对象时，它的地址变化，所以会违反合同的散列码的哈希码在对象的生命周期中应该相同。
在64位系统上，对象的地址太宽，无法放入Int32。
由于被管理对象倾向于与某些偶数次幂对齐，所以最低位将始终为零。当散列码用于索引散列表时，这可能会导致分布模式不正确。

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

来源

2011-04-07 John Källén

不，不是地址，不能用垃圾回收器移动对象。它直观简单，只要它在生成后存储，它就可以是一个随机数。它确实得到存储在对象，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，我想它是相似的。

来源

2011-04-07 14:03:41

谢谢你的回答，这很有道理。我的想法被锁定在想法上，即同步块只能存储单个东西，但是您在此处绘制的机制解释了如何将多个额外属性按需添加到对象。 – 2011-04-07 14:07:49

我不确定你的意思是“在CLR或Java中如何实现Object.GetHashCode？”。 Java的“public int hashCode（）”具有合约，即类的作者应该为其定义hashCode（）实现。换句话说，它可能在不同班级之间有很大差异。我怀疑这对于.Net平台也是如此。

为对象的Javadoc描述了一种类似于你的想法的方法： http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Object.html#hashCode（）

尽可能多是合理可行的，按类对象定义的hashCode方法不会返回不同的整数针对不同的对象。（这是通常通过转换对象的内部地址转换成一个整数来实现，但这种实现技术是不被的JavaTM编程语言所需。）

这种方法是不恰当的，如果你已经定义了你的班级的平等是基于身份以外的东西。

来源

2011-04-07 13:46:42 Jolta

当你从Object类派生时，你不需要实现GetHashCode。通过不这样做，你已经实现了引用语义。上面的JavaDoc意味着“通常”，对象（以及任何派生类不超越其实现的GetHashCode）的哈希码将返回对象的地址。如果GC移动你的对象，你现在将拥有与GC之前相同的对象的不同哈希码。这与Hashtables不能很好地发挥，我猜测。 – 2011-04-07 13:51:16

你是对的，我没有要求，这就是为什么我把“应该”放在第二句话中，而不是“必须”。 =）我仍然认为这是一个很好的做法，就像Trent Gray-Donald在他的回答中所说的那样。 – Jolta 2011-04-12 08:37:18

作为一个JVM实现者，我可以说基础哈希码IS通常与对象的地址有关。这通常不是正确的地址，但有一些以合理的方式改变了地址。我们通过魔术来确保hashCode在对象的整个生命周期中保持稳定（甚至在GC上也是如此，即使对象移动等）。

我强烈建议为所有对象实现一个好的类型特定的hashCode将会哈希。该对象实现它并不意味着它是您使用的理想选择。

来源

2011-04-08 01:33:14

魔术。说真的，我并不是想回避，但它有时是竞争优势的来源。我可以说的是，我们的JVM的某些版本在我们头文件的“哈希和标志”部分保留了一些位。这通常不是完整的32位散列，所以使用了一些重复（并导致潜在熵的损失）。其他选项包括记住一个对象是否被散列，因此如果对象需要移动，则记住“原始”散列。它可能保存在某种脱机数据结构中，或者可能保存在对象的另一部分中。 – 2011-04-09 19:29:08

如何在CLR和JVM中实现Object.GetHashCode（）？

回答

相关问题