【J2SE】hotspot中如何实现Object.hashCode

本文目录

• 一、基本概念
• 二、hotspot的实现
  • Object.hashCode()
    • mark word
    • get_next_hash(thread, obj)
  • System.identityHashCode(obj)
• 三、测试验证
  • 1.GC后对象内存地址改变但哈希值不变
  • 2.哈希值保存在对象头的mark word中
• 附注：openjdk7未移除偏向锁源码

一、基本概念

API注释：Object (Java SE 15 & JDK 15) (oracle.com)

Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by HashMap.

The general contract of hashCode is:

• Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
• If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
• It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

hashCode方法的返回值是一个int类型的哈希值，在J2SE集合框架那里一定会提到hashCode和equals方法的改写原则：

• 运行时hashCode()方法计算的哈希值要保持不变：例如你重写了hashCode方法，其哈希值的计算依赖于对象的name+age+others，在运行时就算你修改了对象的name和age或其他相关属性，你也要保持hashCode方法的返回值不变，否则你将一个对象放入集合框架，随后修改了name或age，结果你发现你在集合框架中再也找不着这个对象了，因为hashCode返回的哈希值变了，定位到了table[]数组不同的slot，所以改写hashCode的第一个原则就是运行时hashCode()方法计算的哈希值要保持不变；
• 如果两个对象通过equals方法相等，那么hashCode方法返回的哈希值也必须相等；
• 反过来不作强制要求，即两个对象hashCode返回的哈希值相等，并不要求equals一定相等，但在集合框架中为了更好的性能，不同的对象尽量返回不同的哈希值；

Object.hashCode()方法是一个native方法，在不同版本的API documentation中，注释文档有些许差异：

 JDK8 API documentation：

This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the Java™ programming language.

JDK9~12 API documentation：

The hashCode may or may not be implemented as some function of an object&＃39;s memory address at some point in time.

 JDK15 API documentation：

根据该方法不同版本的注释差异有：

• JDK8以前，哈希方法的典型实现是将对象的内部地址转换为一个int值，但Java编程语言不必如此；
• JDK9~12，Java哈希方法的实现可以依赖、也可以不依赖于对象的内存地址；
• JDK13以后，直接去掉这段注释，估计是怕误导Java程序员。

这摸棱两可的说法，简直了。

对于Java程序员来说，虽然只需要知道这两个方法的改写原则就行，但是我们想了解的内容不止于此。

question：

1. 如果Java的哈希方法依赖于对象的内存地址，那GC时会移动对象，对象的内存地址会发生变化，Object.hashCode()方法是怎么保持哈希值不变的呢？
2. 如果Java的哈希方法依赖于对象的内存地址，那GC时会移动对象，假设B对象移动到A对象的地址之后，B对象的hashCode()方法会返回相同的哈希值吗？
3. 如若不依赖对象的内存地址，那Object.hashCode()方法又是如何实现的呢？
4. 还有System.identityHashCode(object)又是怎么实现的呢？

接下来，我们去看看hotspot的源码。

二、hotspot的实现

1.Object.hashCode()

早期JVM版本（例如JDK8），Object.hashCode()方法在Object.c文件中声明，JDK15已经改到了jvm.h头文件中声明，本文也是基于JDK15的源码来作探究。

jdk/jvm.h at master · openjdk/jdk · GitHub

/*************************************************************************PART 1: Functions for Native Libraries************************************************************************/
/** java.lang.Object*/
JNIEXPORT jint JNICALL
JVM_IHashCode(JNIEnv *env, jobject obj);JNIEXPORT void JNICALL
JVM_MonitorWait(JNIEnv *env, jobject obj, jlong ms);JNIEXPORT void JNICALL
JVM_MonitorNotify(JNIEnv *env, jobject obj);JNIEXPORT void JNICALL
JVM_MonitorNotifyAll(JNIEnv *env, jobject obj);JNIEXPORT jobject JNICALL
JVM_Clone(JNIEnv *env, jobject obj);

 Object.hashCode()方法在jvm.cpp中实现：

jdk/jvm.cpp at master · openjdk/jdk · GitHub

JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))// as implemented in the classic virtual machine; return 0 if object is NULLreturn handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
JVM_END

ObjectSynchronizer类在synchronizer.hpp文件中声明，在synchronizer.cpp中实现：

 jdk/synchronizer.cpp at master · openjdk/jdk · GitHub

intptr_t ObjectSynchronizer::FastHashCode(Thread* current, oop obj) {while (true) {ObjectMonitor* mOnitor= NULL;markWord temp, test;intptr_t hash;markWord mark = read_stable_mark(obj);if (mark.is_neutral()) { // if this is a normal headerhash = mark.hash();if (hash != 0) { // if it has a hash, just return itreturn hash;}hash = get_next_hash(current, obj); // get a new hashtemp = mark.copy_set_hash(hash); // merge the hash into header// try to install the hashtest = obj->cas_set_mark(temp, mark);if (test == mark) { // if the hash was installed, return itreturn hash;}// Failed to install the hash. It could be that another thread// installed the hash just before our attempt or inflation has// occurred or... so we fall thru to inflate the monitor for// stability and then install the hash.} else if (mark.has_monitor()) {mOnitor= mark.monitor();temp = monitor->header();assert(temp.is_neutral(), "invariant: header=" INTPTR_FORMAT, temp.value());hash = temp.hash();if (hash != 0) {// It has a hash.// Separate load of dmw/header above from the loads in// is_being_async_deflated().// dmw/header and _contentions may get written by different threads.// Make sure to observe them in the same order when having several observers.OrderAccess::loadload_for_IRIW();if (monitor->is_being_async_deflated()) {// But we can&＃39;t safely use the hash if we detect that async// deflation has occurred. So we attempt to restore the// header/dmw to the object&＃39;s header so that we only retry// once if the deflater thread happens to be slow.monitor->install_displaced_markword_in_object(obj);continue;}return hash;}// Fall thru so we only have one place that installs the hash in// the ObjectMonitor.} else if (current->is_lock_owned((address)mark.locker())) {// This is a stack lock owned by the calling thread so fetch the// displaced markWord from the BasicLock on the stack.temp = mark.displaced_mark_helper();assert(temp.is_neutral(), "invariant: header=" INTPTR_FORMAT, temp.value());hash = temp.hash();if (hash != 0) { // if it has a hash, just return itreturn hash;}// WARNING:// The displaced header in the BasicLock on a thread&＃39;s stack// is strictly immutable. It CANNOT be changed in ANY cases.// So we have to inflate the stack lock into an ObjectMonitor// even if the current thread owns the lock. The BasicLock on// a thread&＃39;s stack can be asynchronously read by other threads// during an inflate() call so any change to that stack memory// may not propagate to other threads correctly.}// Inflate the monitor to set the hash.// An async deflation can race after the inflate() call and before we// can update the ObjectMonitor&＃39;s header with the hash value below.mOnitor= inflate(current, obj, inflate_cause_hash_code);// Load ObjectMonitor&＃39;s header/dmw field and see if it has a hash.mark = monitor->header();assert(mark.is_neutral(), "invariant: header=" INTPTR_FORMAT, mark.value());hash = mark.hash();if (hash == 0) { // if it does not have a hashhash = get_next_hash(current, obj); // get a new hashtemp = mark.copy_set_hash(hash) ; // merge the hash into headerassert(temp.is_neutral(), "invariant: header=" INTPTR_FORMAT, temp.value());uintptr_t v = Atomic::cmpxchg((volatile uintptr_t*)monitor->header_addr(), mark.value(), temp.value());test = markWord(v);if (test != mark) {// The attempt to update the ObjectMonitor&＃39;s header/dmw field// did not work. This can happen if another thread managed to// merge in the hash just before our cmpxchg().// If we add any new usages of the header/dmw field, this code// will need to be updated.hash = test.hash();assert(test.is_neutral(), "invariant: header=" INTPTR_FORMAT, test.value());assert(hash != 0, "should only have lost the race to a thread that set a non-zero hash");}if (monitor->is_being_async_deflated()) {// If we detect that async deflation has occurred, then we// attempt to restore the header/dmw to the object&＃39;s header// so that we only retry once if the deflater thread happens// to be slow.monitor->install_displaced_markword_in_object(obj);continue;}}// We finally get the hash.return hash;}
}

因为JDK15中已经废弃掉了偏向锁（见JEP 374: Disable and Deprecate Biased Locking，JDK 15 features 374），所以相比较之前的实现，在ObjectSynchronizer::FastHashCode方法中已经移除了偏向锁的判断，之前的版本在本文附注中贴出。 

ObjectSynchronizer::FastHashCode方法中有普通对象、重量级锁、轻量级锁几种情况，我们主要选取普通对象计算并保存哈希值的case来做研究，ObjectSynchronizer::FastHashCode方法逻辑是这样的：

1. 先拿到调用hashCode()方法的对象的对象头中的mark word；
2. 如果对象是一个普通对象：
   1. 如果mark word中已经保存哈希值，那么就返回该哈希值；
   2. 如果mark word中还不存在哈希值，那就调用get_next_hash(thread, obj)方法计算该对象的哈希值；
   3. 将计算的哈希值CAS保存到对象头的mark word中对应的bit位，成功则返回，失败的话可能有几下几种情形（见源码注释）：
      1. 其他线程也在install the hash并且先于当前线程成功，进入下一轮while获取哈希即可；
      2. 有可能当前对象作为监视器升级成了轻量级锁或重量级锁，进入下一轮while走其他case；
3. 如果对象是一个重量级锁monitor，那对象头中的mark word保存的是指向ObjectMonitor的指针，此时对象非加锁状态下的mark word保存在ObjectMonitor中，到ObjectMonitor中去拿对象的默认哈希值：
   1. 如果已经有默认哈希值，则直接返回；
   2. 否则，在方法结尾会计算默认哈希值并保存到mark word中后再返回；
4. 如果对象是轻量级锁状态并且当前线程持有锁，那就从当前线程栈中取出mark word：
   1. 如果已经有默认哈希值，则直接返回；
   2. 否则，The displaced header is strictly immutable. It can NOT be changed in ANY cases. So we have to inflate the header into heavyweight monitor even the current thread owns the lock. 需要膨胀成重量级锁，然后走重量级锁的逻辑，这里逻辑和case 3里ObjectMonitor中保存的mark word没有默认哈希值的逻辑大部分重合，所以提到了方法末尾，即if else的后面；
   3. 这一部分的源码和老版本保持一致，老版本lightweight monitor的注释和源码见附录；

上述hotspot对hashCode()方法的实现中标红部分有两个关键点：mark word和get_next_hash(thread, obj)方法。

A.mark word

关于mark word，在《Java对象的对齐规则》一文4.1章节谈对象头时，其源码和结构已经分析过了，如果你不太熟悉，可以先看看这一部分再往下阅读。

在32bit机器上，mark word中有25bit用于保存哈希值，64bit机器上，有31bit用于保存哈希值，源码注释中给的结构是这样的：


// 32 bits:
// --------
// hash:25 ------------>| age:4 biased_lock:1 lock:2 (normal object)
// JavaThread*:23 epoch:2 age:4 biased_lock:1 lock:2 (biased object)
// size:32 ------------------------------------------>| (CMS free block)
// PromotedObject*:29 ---------->| promo_bits:3 ----->| (CMS promoted object)
//
// 64 bits:
// --------
// unused:25 hash:31 -->| unused:1 age:4 biased_lock:1 lock:2 (normal object)
// JavaThread*:54 epoch:2 unused:1 age:4 biased_lock:1 lock:2 (biased object)
// PromotedObject*:61 --------------------->| promo_bits:3 ----->| (CMS promoted object)
// size:64 ----------------------------------------------------->| (CMS free block)//
// - the two lock bits are used to describe three states: locked/unlocked and monitor.
//
// [ptr | 00] locked ptr points to real header on stack
// [header | 0 | 01] unlocked regular object header
// [ptr | 10] monitor inflated lock (header is wapped out)
// [ptr | 11] marked used by markSweep to mark an object

所以上文第一个问题Object.hashCode()方法怎么保持哈希值不变就有了答案：

• 在没有调用对象hashCode()方法时，对象头mark word中对应的比特位为0；
• 一旦调用hashCode()方法，通过get_next_hash(thread, obj)计算出了对象的哈希值，就保存到对象头的mark word中对应的比特位；
• 后续再次调用的时候，直接返回对象头的mark word中保存的哈希值；

所以暂且不论get_next_hash(thread, obj)方法计算对象哈希值是否基于对象的内存地址，即便是基于对象内存地址，GC后对象移动，但是保存在其对象头的mark word中的哈希值还是第一次调用hashCode()方法得到得到哈希值。

我们在后续第三节测试验证的时候，会通过jol工具观察整个过程来做验证，jol工具（Java object layout）是openjdk开源的一款查看Java对象内存布局的工具，在《Java对象的对齐规则》一文中也有介绍。

B.get_next_hash(thread, obj)

static inline intptr_t get_next_hash(Thread* current, oop obj) {intptr_t value = 0;if (hashCode == 0) {// This form uses global Park-Miller RNG.// On MP system we&＃39;ll have lots of RW access to a global, so the// mechanism induces lots of coherency traffic.value = os::random();} else if (hashCode == 1) {// This variation has the property of being stable (idempotent)// between STW operations. This can be useful in some of the 1-0// synchronization schemes.intptr_t addr_bits = cast_from_oop(obj) >> 3;value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;} else if (hashCode == 2) {value = 1; // for sensitivity testing} else if (hashCode == 3) {value = ++GVars.hc_sequence;} else if (hashCode == 4) {value = cast_from_oop(obj);} else {// Marsaglia&＃39;s xor-shift scheme with thread-specific state// This is probably the best overall implementation -- we&＃39;ll// likely make this the default in future releases.unsigned t = current->_hashStateX;t ^= (t <<11);current->_hashStateX = current->_hashStateY;current->_hashStateY = current->_hashStateZ;current->_hashStateZ = current->_hashStateW;unsigned v = current->_hashStateW;v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));current->_hashStateW = v;value = v;}value &= markWord::hash_mask;if (value == 0) value = 0xBAD;assert(value != markWord::no_hash, "invariant");return value;
}

get_next_hash(thread, obj)方法中有五种哈希值计算方式：

• 0.随机数
• 1.基于对象内存地址的函数
• 2.恒等于1（用于敏感性测试）
• 3.自增序列
• 4.将对象的内存地址强转为int
• 5.Marsaglia&＃39;s xor-shift scheme with thread-specific state（基于线程具体状态的Marsaglias的异或移位方案）

到底用的哪一种计算方式，和参数hashCode有关系，这个参数在globals.hpp中有默认配置，你可以通过虚拟机启动参数-XX:hashCode=n来做修改。

• 在openjdk6、openjdk7中，采用的是随机数的方式

• 在openjdk8以后，采用的是Marsaglia异或移位方案

• 在截至今天github上最新的openjdk主线开发库，采用的还是基于线程具体状态的Marsaglia异或移位方案

对于Marsaglia异或移位方案，线程状态是指hotspot中Thread类的四个属性_hashStateW、_hashStateX、_hashStateY、_hashStateZ，这四个属性在Thread.hpp文件中定义：

jdk/thread.hpp at master · openjdk/jdk · GitHub

在Thread.cpp文件中赋值：

jdk/thread.cpp at master · openjdk/jdk · GitHub

最后在ObjectSynchronizer类中获取通过Marsaglia异或移位方案计算出对象默认哈希值。

所以，从openjdk的多个版本来看，Object.hashCode()方法的默认实现并没有采用对象的内存地址来计算。

所以第一和第二个问题，就不需要再纠结了。

2、System.identityHashCode(obj)

在hotspot中，java.lang.System.identityHashCode(Object)的实现是直接转调JVM_IHashCode，也就是说System.identityHashCode的实现就是Object.hashCode在hotspot中的实现。

jdk/System.c at master · openjdk/jdk · GitHub

JNIEXPORT jint JNICALL
Java_java_lang_System_identityHashCode(JNIEnv *env, jobject this, jobject x)
{return JVM_IHashCode(env, x);
}

所以，有如下几种情形

• 如果你没有重写Object.hashCode()方法，则走默认的哈希方法逻辑；
• 如果你重写了Object.hashCode()方法，每次调用的时候都会走你重写的hashCode()逻辑；
  • 如果你在重写的哈希方法中调用super.hashCode()，那么会走默认哈希方法逻辑，第一次调用会计算默认哈希值并存放到对象头的mark word中，以后直接从mark word获取返回；
• 在System.identityHashCode(Object)中直接转调Object.hashCode()的实现，也会将计算的默认哈希值保存到对象头的mark word中，如果已经保存过了那直接返回；

三、测试验证

这里需要用到openjdk的开源工具jol（Java object layout），查看Java对象内存布局的工具，工具在《Java对象的对齐规则》一文中已经介绍，如果你不熟悉，可以先看看这篇文章。

1.GC后对象内存地址改变但哈希值不变

Dummy类用于创建占位对象，用来创建4M的byte数组，用于触发GC。

/*** 占位资源，4M的字节数组，用于测试用触发GC操作* @author 王大锤* @date 2021年7月18日*/
public class Dummy {@SuppressWarnings("unused")private byte[] dummy = new byte[4 * 1024 * 1024];
}

jvm的启动参数：

-Xmx20m -Xmx20m -XX:+PrintGCDetails

测试代码，其中要用到jol工具的org.openjdk.jol.vm.VM类：

public static void main(String[] args) {Object object = new Object();System.out.println("GC前：");addressOf(object);new Dummy();new Dummy();new Dummy();System.gc();System.out.println("GC后：");addressOf(object);}private static void addressOf(T t) {long address = VM.current().addressOf(t);System.out.println(t + " hashCode is: " + t.hashCode() +", address is: " + address);}

测试结果，为了方便阅读，-XX:+PrintGCDetails打印的GC信息省略掉了：

GC前：
java.lang.Object@33f88ab hashCode is: 54495403, address is: 34359268032

GC后：
java.lang.Object@33f88ab hashCode is: 54495403, address is: 34200357760

gc前后对象默认的哈希值都是54495403，gc前对象的内存地址34359268032，gc后对象的内存地址变为了34200357760。

从上面的分析可知，默认哈希值保存到了对象头的mark word中，所以虽然GC移动了对象在内存中的位置，但是其默认哈希值并未改变。

至于将哈希值保存在对象头mark word中，请参看下一个测试。

2.哈希值保存在对象头的mark word中

测试代码，其中要用到jol工具的org.openjdk.jol.info.ClassLayout类：

Object object = new Object();System.out.println(ClassLayout.parseInstance(object).toPrintable());System.out.println(object.hashCode());System.out.println(ClassLayout.parseInstance(object).toPrintable());

测试结果：

java.lang.Object object internals:
OFF  SZ   TYPE DESCRIPTION               VALUE
  0   8        (object header: mark)     0x0000000000000001 (non-biasable; age: 0)
  8   4        (object header: class)    0x00002080
 12   4        (object alignment gap)    
Instance size: 16 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

2116908859
java.lang.Object object internals:
OFF  SZ   TYPE DESCRIPTION               VALUE
  0   8        (object header: mark)     0x0000007e2d773b01 (hash: 0x7e2d773b; age: 0)
  8   4        (object header: class)    0x00002080
 12   4        (object alignment gap)    
Instance size: 16 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

结果分析：

本机环境64bit widnows，开启压缩指针，所以对象头中前8字节是mark word，接着4字节是元数据指针_compressed_klass，最后4字节是Java默认的对象间8字节对齐所需要填补的对齐填充。

其中没调用hashCode方法前，mark word中对应的比特位值为0，调用之后，计算出的默认哈希值会填充到mark word对应的比特位，见下图：

附注：openjdk7未移除偏向锁源码

openjdk7中ObjectSynchronizer::FastHashCode源码，未移除偏向锁：

intptr_t ObjectSynchronizer::FastHashCode (Thread * Self, oop obj) {if (UseBiasedLocking) {// NOTE: many places throughout the JVM do not expect a safepoint// to be taken here, in particular most operations on perm gen// objects. However, we only ever bias Java instances and all of// the call sites of identity_hash that might revoke biases have// been checked to make sure they can handle a safepoint. The// added check of the bias pattern is to avoid useless calls to// thread-local storage.if (obj->mark()->has_bias_pattern()) {// Box and unbox the raw reference just in case we cause a STW safepoint.Handle hobj (Self, obj) ;// Relaxing assertion for bug 6320749.assert (Universe::verify_in_progress() ||!SafepointSynchronize::is_at_safepoint(),"biases should not be seen by VM thread here");BiasedLocking::revoke_and_rebias(hobj, false, JavaThread::current());obj = hobj() ;assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");}}// hashCode() is a heap mutator ...// Relaxing assertion for bug 6320749.assert (Universe::verify_in_progress() ||!SafepointSynchronize::is_at_safepoint(), "invariant") ;assert (Universe::verify_in_progress() ||Self->is_Java_thread() , "invariant") ;assert (Universe::verify_in_progress() ||((JavaThread *)Self)->thread_state() != _thread_blocked, "invariant") ;ObjectMonitor* mOnitor= NULL;markOop temp, test;intptr_t hash;markOop mark = ReadStableMark (obj);// object should remain ineligible for biased lockingassert (!mark->has_bias_pattern(), "invariant") ;if (mark->is_neutral()) {hash = mark->hash(); // this is a normal headerif (hash) { // if it has hash, just return itreturn hash;}hash = get_next_hash(Self, obj); // allocate a new hash codetemp = mark->copy_set_hash(hash); // merge the hash code into header// use (machine word version) atomic operation to install the hashtest = (markOop) Atomic::cmpxchg_ptr(temp, obj->mark_addr(), mark);if (test == mark) {return hash;}// If atomic operation failed, we must inflate the header// into heavy weight monitor. We could add more code here// for fast path, but it does not worth the complexity.} else if (mark->has_monitor()) {mOnitor= mark->monitor();temp = monitor->header();assert (temp->is_neutral(), "invariant") ;hash = temp->hash();if (hash) {return hash;}// Skip to the following code to reduce code size} else if (Self->is_lock_owned((address)mark->locker())) {temp = mark->displaced_mark_helper(); // this is a lightweight monitor ownedassert (temp->is_neutral(), "invariant") ;hash = temp->hash(); // by current thread, check if the displacedif (hash) { // header contains hash codereturn hash;}// WARNING:// The displaced header is strictly immutable.// It can NOT be changed in ANY cases. So we have// to inflate the header into heavyweight monitor// even the current thread owns the lock. The reason// is the BasicLock (stack slot) will be asynchronously// read by other threads during the inflate() function.// Any change to stack may not propagate to other threads// correctly.}// Inflate the monitor to set hash codemOnitor= ObjectSynchronizer::inflate(Self, obj);// Load displaced header and check it has hash codemark = monitor->header();assert (mark->is_neutral(), "invariant") ;hash = mark->hash();if (hash == 0) {hash = get_next_hash(Self, obj);temp = mark->copy_set_hash(hash); // merge hash code into headerassert (temp->is_neutral(), "invariant") ;test = (markOop) Atomic::cmpxchg_ptr(temp, monitor, mark);if (test != mark) {// The only update to the header in the monitor (outside GC)// is install the hash code. If someone add new usage of// displaced header, please update this codehash = test->hash();assert (test->is_neutral(), "invariant") ;assert (hash != 0, "Trivial unexpected object/monitor header usage.");}}// We finally get the hashreturn hash;
}

附注：本文如有错漏，烦请指正！