JDK源码解析——Object的hashCode方法

目录


前言

这几天在准备面试,在阅读Java底层代码时经常会看到 native 关键字,这就意味着这个方法的底层实现无法直接看见。作为一个Java程序员,我还是想了解一些底层JDK代码的。但我在学习的过程中发现网上的资料比较零散,因此,在此记录下自己阅读JDK源代码一些心得。我不能保证我文章中的每个字都是正确的,但是我能保证每个字都是经过我反复推敲,认真思考后写下的。

说明

  1. 本文的阅读门槛较低,只要对编程有一定了解的小伙伴都可以读懂,如果对于JVM基础不是非常了解,则不建议一口气全部阅读完,建议按照顺序,消化理解后,再继续往下阅读
  2. 本文涉及到的源代码为OpenJDK 9,如有需要,请去官网下载
  3. 涉及到的虚拟机为HotSpot
  4. 本文会涉及到一些Java对象头和锁的概念,提前了解可以帮助理解
  5. 本人C++和汇编的水平并不是很高,如有错误,可以留言或私信我,我会尽快修改

一、源码目录结构

(1).JDK目录

openjdk
├ corba:不流行的多语言、分布式通讯接口
├ hotspot:Java 虚拟机
├ jaxp:XML 处理
├ jaxws:一组 XML web services 的 Java API
├ jdk:java 开发工具包
├ langtools:Java 语言工具
└ nashorn:JVM 上的 JavaScript 运行时

(2).hotspot目录

hotspot
├─agent                            Serviceability Agent的客户端实现
├─make                             用来build出HotSpot的各种配置文件
├─src                              HotSpot VM的源代码
│  ├─cpu                            CPU相关代码(汇编器、模板解释器、ad文件、部分runtime函数在这里实现)
│  ├─os                             操作系相关代码
│  ├─os_cpu                         操作系统+CPU的组合相关的代码
│  └─share                          平台无关的共通代码
│      ├─tools                        工具
│      │  ├─hsdis                      反汇编插件
│      │  ├─IdealGraphVisualizer       将server编译器的中间代码可视化的工具
│      │  ├─launcher                   启动程序“java”
│      │  ├─LogCompilation             将-XX:+LogCompilation输出的日志(hotspot.log)整理成更容易阅读的格式的工具
│      │  └─ProjectCreator             生成Visual Studio的project文件的工具
│      └─vm                           HotSpot VM的核心代码
│          ├─adlc                       平台描述文件(上面的cpu或os_cpu里的*.ad文件)的编译器
│          ├─asm                        汇编器接口
│          ├─c1                         client编译器(又称“C1”)
│          ├─ci                         动态编译器的公共服务/从动态编译器到VM的接口
│          ├─classfile                  类文件的处理(包括类加载和系统符号表等)
│          ├─code                       动态生成的代码的管理
│          ├─compiler                   从VM调用动态编译器的接口
│          ├─gc_implementation          GC的实现
│          │  ├─concurrentMarkSweep      Concurrent Mark Sweep GC的实现
│          │  ├─g1                       Garbage-First GC的实现(不使用老的分代式GC框架)
│          │  ├─parallelScavenge         ParallelScavenge GC的实现(server VM默认,不使用老的分代式GC框架)
│          │  ├─parNew                   ParNew GC的实现
│          │  └─shared                   GC的共通实现
│          ├─gc_interface               GC的接口
│          ├─interpreter                解释器,包括“模板解释器”(官方版在用)和“C++解释器”(官方版不在用)
│          ├─libadt                     一些抽象数据结构
│          ├─memory                     内存管理相关(老的分代式GC框架也在这里)
│          ├─oops                       HotSpot VM的对象系统的实现
│          ├─opto                       server编译器(又称“C2”或“Opto”)
│          ├─prims                      HotSpot VM的对外接口,包括部分标准库的native部分和JVMTI实现
│          ├─runtime                    运行时支持库(包括线程管理、编译器调度、锁、反射等)
│          ├─services                   主要是用来支持JMX之类的管理功能的接口
│          ├─shark                      基于LLVM的JIT编译器(官方版里没有使用)
│          └─utilities                  一些基本的工具类
└─test                             单元测试

由于JDK版本不同,上面的目录结构可能存在出入,不过不影响我们阅读源代码。

JDK目录来源
hotspot目录来源


二、基础知识

如果大家对Java的对象头和锁有过了解,可以跳过这里

(1).Object Header(对象头)

我们都知道,Java中的对象存在堆内存中,以64位Java虚拟机为例,下标为Java对象的结构示意图

名称 字段名称 备注
对象头 Mark Word (标记字) 占64位,主要用来表示对象的线程锁状态,也可以用来配合GC、存放对象的HashCode
Klass Pointer (类指针) 占64位,指向方法区中Class信息的指针,对象可以随时知道自己是哪个类的实例
Length (数组长度,可选) 占用大小不确定,当对象是数组对象时才会有
对象体 对象的属性值 1 占用空间取决于对象的属性数量和类型,用于保存对象的属性和值
对象的属性值 2
对象的属性值 3
对象的属性值 4
......
对齐字节 对齐字节 JVM要求Java对象占的内存大小为8bit的倍数,因此本字段用于填充大小

下面,我来解释一下上面表格中的问题

为啥有些博客上写明了对象头的数组长度在64位虚拟机的环境下是64位的,而我这里写的是大小不确定呢?

首先,进入/openjdk/hotspot/src/share/vm/oops目录,找到oop.hpp文件,在类oopDesc中,我们可以看到普通对象的对象头有如下定义:

private:
 	volatile markOop _mark;
	union _metadata {
    	Klass*      _klass;
    	narrowKlass _compressed_klass;
  	} _metadata;
  	// Fast access to barrier set. Must be initialized.
  	static BarrierSet* _bs;

由此可见,_mark就是标记字,_metadata为union,其中的_klass就是类指针,而下面的_bs为快速存取使用的字段,那么这里是不是多了点什么?
经过追踪,我们就可以发现narrowKlass的秘密:

// If compressed klass pointers then use narrowKlass.
typedef juint narrowKlass;

一看注释,恍然大悟!
对哦,JVM里面有这么一个选项:-XX:+UseCompressedOops,其作用为启用压缩指针。当启用压缩指针以后,64位的Klass*指针会被压缩成narrowKlass -> juint -> uint32_t -> unsigned int,即32位,但这里使用了union,也就是说,_metadata还是会占用64位,那么剩下的32位用到哪里去了呢?
接下来,我们找到arrayOop.hpp文件,在类arrayOopDesc中,我们可以看到它继承了类oppDesc

// arrayOopDesc is the abstract baseclass for all arrays.  It doesn't
// declare pure virtual to enforce this because that would allocate a vtbl
// in each instance, which we don't want.

// The layout of array Oops is:
//
//  markOop
//  Klass*    // 32 bits if compressed but declared 64 in LP64.
//  length    // shares klass memory or allocated after declared fields.

class arrayOopDesc : public oopDesc {
  	friend class VMStructs;
  	friend class arrayOopDescTest;

  	// Interpreter/Compiler offsets

  	// Header size computation.
 	// The header is considered the oop part of this type plus the length.
  	// Returns the aligned header_size_in_bytes.  This is not equivalent to
  	// sizeof(arrayOopDesc) which should not appear in the code.
  	static int header_size_in_bytes() {
    	size_t hs = align_size_up(length_offset_in_bytes() + sizeof(int),
                              HeapWordSize);

这么大一段注释,看的我头皮发麻,于是我用上了毕生所学的散装英语尝试理解它:

  1. 数组的对象头由markOop(标记字)Klass*(类指针)length(数组长度)组成
  2. 在64位虚拟机上被压缩时,Klass*将会占32位
  3. length会共享klass的内存,或者在声明的字段后分配
  4. header_size_in_bytes()为计算头部大小的函数

看到这里,我相信大家已经知道前面为什么说对象头的数组长度大小不确定了,在此总结一下:
当JVM设置成启用压缩指针时,Klass*的大小会被压缩成32位,但是_metadata还是占用了64位,如果此时的对象为数组对象时,它的length会去占用_metadata没有使用到的32位;而在没有启用压缩指针的情况下,length会追加到内嵌的实例数据的最后,这时候还需要考虑对齐字节,也就无法给出实际大小了。
虽然上面一直在解释数组对象中对象头的数组长度占用空间大小问题,但是看到这里你,相信你现在已经对对象头有了比较全面的了解,至于文中没有提到的具体实现,大家可以自己翻阅源代码,在这里也就不详细展开了。


(2).Lock(锁)

在了解完对象头后,我们还需要了解下Java中锁的几个状态。
在Java中,锁有四种状态:无锁偏向锁轻量级锁重量级锁。同时,这些状态只有升级,没有降级。
这里必须说明一下,在Java中,确实存在锁升级和锁降级的概念,但是它们说的不是同一个事情。锁升级指的是synchronized关键字在JDK1.6以后做的优化;锁降级是为了保证数据的可见性而在当前拥有写锁的情况下,再获取读锁,然后释放写锁的过程。这里主要探讨的是锁的四种状态以及升级的过程。

状态 描述 升级条件
无锁 不存在竞争 有一个线程使用同步锁
偏向锁 同步锁只有一个线程访问,不存在多线程竞争,锁会偏向当前进程 有别的线程也想使用同步锁
轻量级锁 有多个线程竞争锁,没有抢到锁的线程会自旋 自旋次数超过阈值
重量级锁 当线程发现当前的锁是重量级锁时,直接将自己挂起,等待被唤醒
上表为这些锁的基本概念,下面我们来了解一下锁状态转换过程(具体的源代码暂时先不深入分析了)

1. 无锁 => 偏向锁

当一个对象处于可偏向状态时,线程会尝试使用CAS操作将自己的线程ID写入对象的Mark Word中:

CAS是一种乐观锁的机制,他用到了三个基本操作数:内存地址A、需要修改的值B、修改后的值C。
当使用CAS操作更新变量时,只有当内存中A位置的值与B相同时,才将值改为C;反之,不做任何操作,并可以再次尝试。
如果操作成功,则认为已经获取到对象的偏向锁,执行同步代码。而当同步代码执行完成以后,线程不会将对象Mark Word中的线程ID改回原值,这样做的目的是:当这个对象在下次被同样的线程加锁时(中途没有被其他线程加锁),无需修改Mark Word,直接认为偏向成功。 如果操作失败,表示已经有另外一个线程获取了这个偏向锁,此时,需要将偏向锁撤销,并升级成为轻量级锁(该操作需要等待全局安全点JVM SafePoint,也就是没有线程在执行字节码的时间点)。

当一个对象处于已偏向状态时,则需要判断Mark Word线程ID是否为本线程的ID

如果ID相同,则认为本线程已经获取到偏向锁,可以直接往下执行同步代码。 如果ID不同,表示该对象目前偏向于其他线程,需要撤销偏向锁,并将其升级为轻量级锁。

偏向锁的撤销
当存在超过一个线程竞争某一对象时,才需要执行撤销操作。在撤销完成以后,对象可能会处于以下两种状态:

  1. 不可偏向的无锁状态
    之前获取偏向锁线程的同步代码块已经执行完毕,对象处于“空闲状态”,也就是说,原有的偏向锁已经过期无效了,此时对象应该被转换为不可偏向的无锁状态。

  2. 被轻量级锁加锁的状态
    之前获取偏向锁线程的同步代码块没有全部执行完毕,偏向锁依然有效,此时对象应该被转换为被轻量级锁加锁的状态。

2. 偏向锁 => 轻量级锁

  • 首先,根据标志位判断对象是否处于不可偏向的无锁状态
  • 若处于不可偏向的无锁状态时,竞争者向JVM提交一个安全点(Safe Point)请求
  • 在安全点的时候(Safe Point),JVM线程(VM Thread)会在持有锁的线程的栈帧(Stack Frame)中创建用于存储锁记录(Lock Record)的空间,将对象头的Mark Word复制到锁记录中,也就是官方说的Displaced Mark Word
  • 然后,将对象的Mark Word更新为轻量级锁模式(也就是将Mark Word更新为指向轻量级锁的指针)
  • 最后,唤醒持有锁的线程,这样它就会认为自己持有轻量级锁了,竞争者也会去按照轻量级锁的模式去竞争
    • 竞争者通过CAS操作将Mark Word替换位指向锁记录的指针
    • 如果成功,则表示获得锁
    • 如果失败,则表示对象已经加锁,竞争者进行自旋,当自旋次数超过阈值时,锁会升级至重量级锁

3. 轻量级锁 => 重量级锁

此过程依赖于操作系统的互斥量(mutex),它会导致进程在用户态与内核态之间切换,是一个开销较大的操作。

  • 在锁膨胀时, 被锁对象的Mark Word会被通过CAS操作尝试更新为一个数据结构的指针,这个数据结构中包含了指向操作系统互斥量(mutex) 和条件变量(condition variable)的指针

(3).Mark Word(标记字)

在了解完对象头和锁以后,我们就可以关注标记字了,因为标记字与锁息息相关,我们探讨的hashCode()方法也与这些字段相关。
首先,进入/openjdk/hotspot/src/share/vm/oops目录,打开markOop.hpp文件,可以看到有关标记字结构的注释:

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)
unused:25 hash:31 -->| cms_free:1 age:4    biased_lock:1 lock:2 (COOPs && normal object)
JavaThread*:54 epoch:2 cms_free:1 age:4    biased_lock:1 lock:2 (COOPs && biased object)
narrowOop:32 unused:24 cms_free:1 unused:4 promo_bits:3 ----->| (COOPs && CMS promoted object)
unused:21 size:35 -->| cms_free:1 unused:7 ------------------>| (COOPs && CMS free block)

[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
                                           not valid at any other time

大体上就是下表

锁状态 64位标记字 特征
56bit 1bit 4bit 1bit 2bit
left right biased_lock lock
无锁 unused:25bit hashCode:31bit unused age 0 01
偏向锁 thread:54bit epoch:2bit unused age 1 01 仅需比较Thread ID
轻量级锁 ptr_to_lock_record(栈中锁记录的指针) 00 自旋
重量级锁 ptr_to_heavyweight_monitor(重量级锁的指针) 10 依赖操作系统的互斥量(mutex)
GC标记 11 标记
其中的epoch(时间戳)主要用于偏向锁的再偏向操作,在这里暂时先略过。

三、hashCode()的C++源代码

(1). 寻找hashCode方法

因为我们需要找的时Object的hashCode方法,因此,我们进入/openjdk/jdk/src/java.base/share/native/libjava目录,找到并打开Object.c文件,我们可以看到

static JNINativeMethod methods[] = {
    {"hashCode",    "()I",                    (void *)&JVM_IHashCode},
    {"wait",        "(J)V",                   (void *)&JVM_MonitorWait},
    {"notify",      "()V",                    (void *)&JVM_MonitorNotify},
    {"notifyAll",   "()V",                    (void *)&JVM_MonitorNotifyAll},
    {"clone",       "()Ljava/lang/Object;",   (void *)&JVM_Clone},
};

追踪一下JNINativeMethod,我们也可以知道,结构体里面存放的分别是方法的名称、签名和函数指针,大家也可以javah一下Object.class文件,看看签名是否一致。

/*
 * used in RegisterNatives to describe native method name, signature,
 * and function pointer.
 */
typedef struct {
    char *name;
    char *signature;
    void *fnPtr;
} JNINativeMethod;

之后,追踪一下JVM_IHashCode,发现它是在jvm.h里面定义的方法,在jvm.cpp里面的实现如下所示。

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

在此,我们终于揭开hashCode()的神秘面纱:它是ObjectSynchronizer类的FastHashCode(Thread * Self, oop obj)方法


(2). FastHashCode(Thread * Self, oop obj)源代码解读

下面,我将直接在源代码中注释,来解释它的实现。

1. 判断对象是否使用了偏向锁

  if (UseBiasedLocking) {
    // 注意:JVM中的许多地方都不希望在这里使用safe point,尤其是在perm gen对象上的大多数操作。
    //      然而,我们只对Java实例进行了偏向,并且检查了可能撤销偏向的identity_hash的所有调用
    //      站点,以确保它们能够处理safe point。偏差模式的附加检查是为了避免对线程本地存储的无
    //      用调用。

    // 判断对象是否处于“已偏向”状态
    if (obj->mark()->has_bias_pattern()) {
      // 将obj对象包装成一个句柄(为了下面的STW safe point)
      Handle hobj(Self, obj);
      // 保证程序的执行条件:(Universe正在进行验证)或(当前不在安全点(safe point))
      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());
      // 根据Handle类定义的无参函数对象,将obj取出
      obj = hobj();
      // 检测一下是否成功撤销
      assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");
    }
  }
  • perm gen:永久代
    • 方法区是JVM的一种规范,存放类信息、常量、静态变量、即时编译器编译后的代码等。
    • 永久代是HotSpot的一种具体实现,实际指的就是方法区。
  • identity_hash:就是前文提到对象头中Mark Word中的HashCode
  • Safe Point:安全点
    • SafePoint是一个线程可能暂停的位置,在这个位置时,堆对象的状态是确定一致的,JVM可以安全地进行操作。
  • Universe
    • Universe是一个在JVM中保存已知的系统类和对象的命名空间。
  • Handle:句柄
    • Handle可以简单的理解为引用,在handles.hpp有提到,句柄是一个值对象,可以将其作为值传递,可以使用&传递作为参数,也可以作为返回值返回。

2. 做一些基本判断

  // 确保当前的执行路径不处于safe point
  assert(Universe::verify_in_progress() || DumpSharedSpaces ||
         !SafepointSynchronize::is_at_safepoint(), "invariant");
  // 确保当前线程是个Java线程
  assert(Universe::verify_in_progress() || DumpSharedSpaces ||
         Self->is_Java_thread() , "invariant");
  // 确保当前线程没有被阻塞
  assert(Universe::verify_in_progress() || DumpSharedSpaces ||
         ((JavaThread *)Self)->thread_state() != _thread_blocked, "invariant");

  ObjectMonitor* monitor = NULL;
  markOop temp, test;
  intptr_t hash;
  // 读出一个稳定的标记字,防止对象正处于锁膨胀状态,如果正在膨胀,就等它膨胀完,再读出来
  markOop mark = ReadStableMark(obj);

  // 确保对象不处于"已偏向"状态
  assert(!mark->has_bias_pattern(), "invariant");

3. 当对象处于中性时

  // 判断当前对象是否处于中性
  if (mark->is_neutral()) {
    // 尝试获取标记字中的hashCode
    hash = mark->hash();
    // 如果存在hashCode,则直接返回
    if (hash) {
      return hash;
    }
    // 当不存在时,需要根据hashCode的算法规则生成一个hashCode
    hash = get_next_hash(Self, obj);
    // 将生成的hashCode放到标记字中,并将新的值给temp
    temp = mark->copy_set_hash(hash);
    // 使用CAS操作修改标记字
    test = (markOop) Atomic::cmpxchg_ptr(temp, obj->mark_addr(), mark);
    if (test == mark) {
      // 操作成功,返回hash
      return hash;
    }
    // 如果操作失败,要将标记字膨胀为重量级锁
  }
  • 为啥在操作失败后,直接膨胀到重量级锁?

    • 当CAS操作失败时,肯定存在以下问题
      • 至少存在两个线程正在竞争锁,此时,如果要加锁,应该加轻量级锁
      • 这里的CAS操作包含自旋,CAS失败,表示自旋超过阈值
      • 因此,需要膨胀成重量级锁
  • mark->is_neutral()

    • 将64位的对象头和3(D)进行操作,当结果为1时,标记字中的低三位为001(B),也就是无锁状态,可以参考以下源代码
  #ifdef _LP64
  const int LogBytesPerWord    = 3;
  #else
  const int LogBytesPerWord    = 2;
  #endif
  
  const int LogBitsPerByte     = 3;
  const int LogBitsPerWord     = LogBitsPerByte + LogBytesPerWord;
  const int BitsPerWord        = 1 << LogBitsPerWord;
  const intptr_t OneBit        = 1;
  
  #define nth_bit(n)        (((n) >= BitsPerWord) ? 0 : (OneBit << (n)))
  #define right_n_bits(n)   (nth_bit(n) - 1)
  enum { 
  		 ...
         lock_bits                = 2,
         biased_lock_bits         = 1,
         ...
  };
  enum { 
    	 lock_shift               = 0,
    	 ...
  };
  enum { 
  		 ...
         biased_lock_mask         = right_n_bits(lock_bits + biased_lock_bits),
         biased_lock_mask_in_place= biased_lock_mask << lock_shift,
         ...
  };
  inline intptr_t mask_bits      (intptr_t  x, intptr_t m) { return x & m; }
  
  bool is_neutral()  const { return (mask_bits(value(), biased_lock_mask_in_place) == unlocked_value); }
  • Atomic::cmpxchg_ptr(…)
    • 此方法为CAS操作的具体实现,追踪一下,我们就可以看到它在不同操作系统下具体的实现,由于本人汇编能力有限,因此在这里只例举三个操作系统:Linux_s390、Linux_x86和Windows_x86,其他操作系统的实现也是大同小异。
  • Linux_s390
jlong Atomic::cmpxchg(jlong xchg_val, volatile jlong* dest, jlong cmp_val, cmpxchg_memory_order unused) {
  unsigned long old;

  __asm__ __volatile__ (
    "   CSG      %[old],%[upd],%[mem]    \n\t" // 使用CSG指令来修改mem位置的值
    // 输出
    : [old] "=&d" (old)      // dest位置(地址)在操作完成后的值,只写,与原值无关
    , [mem] "+Q"  (*dest)    // 需要修改的位置,读/写,内存将自动更新
    // 输入
    : [upd] "d"   (xchg_val) // 期望修改后的值
    ,       "0"   (cmp_val)  // 比较的值(dest位置(地址)原始的值),只读,[old]的初始值,(操作数 #0)
    // clobbered域
    : "cc"
  );

  return (jlong)old;
}

这是C++内联汇编的代码,这是AT&T汇编的语法,花了些时间,找了篇文档大概看了下,下面写个例子,大家可以参考一下

int main() {    
    int input = 10;
    int output = 0;
    __asm__ __volatile__(
        "movl %%eax, %%ebx \n\t"	// 将寄存器EAX的值MOV到EBX
        "subl $0x1, %%ebx \n\t"		// 将寄存器EBX的值SUB 0x1(就是将EBX的值-1),然后赋值给EBX
        : "=b"(output)				// 输出,将EBX寄存器的值赋给output
        : "a"(input)				// 输入,将input的值赋给EAX
        : "memory"					// Clobber/Modify域,告诉GCC当前内联汇编可能会影响的寄存器或内存
    );
    printf("output:%d\n", output);	// 最后输出 output:9
    return 1;
}

AT&T汇编与Intel汇编最大的不同是:

  1. AT&T汇编中,立即数需要用’$'作为前缀
  2. AT&T汇编中,寄存器名前要加’%’
  3. AT&T汇编和Intel汇编的源操作数与目的操作数的位置正好相反
  4. AT&T汇编中,操作数的字长由操作符的最后一个字母决定。b:(字节,1B,8b),w:(字,2B,16b),l:(长字,4B,32b)
  • Linux_x86
// 为多核机器上的指令添加锁定前缀,也就是将0和mp对应的寄存器比较大小,然后决定是否加锁,cmp是比较指令,je 1f就是跳转到'1:'后
#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "

inline jlong Atomic::cmpxchg (jlong exchange_value, volatile jlong* dest, jlong compare_value, cmpxchg_memory_order order) {
  // 判断系统是否是多处理器
  bool mp = os::is_MP();
  // cmpxchgq: 将累加器(AL/AX/EAX/RAX,这里是下面a对应的EAX寄存器)的值与(%3)地址的值比较:
  //	 	   如果相等,则将%1装载到(%3)地址,zf置1;
  //		   如果不等,(%3)地址的值装载到(AL/AX/EAX/RAX,这里是下面a对应的EAX寄存器)并将zf清0
  __asm__ __volatile__ (LOCK_IF_MP(%4) "cmpxchgq %1,(%3)"	
  						// 输出,对应%0,操作结束后dest位置(地址)的值
                        : "=a" (exchange_value)
                        // 输入,对应%1:期望修改后的值,%2:比较的值(dest位置(地址)原始的值),%3:需要修改的地址,%4:是否是多核处理器
                        : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                        // 这个在前面的注释介绍了
                        : "cc", "memory");
  return exchange_value;
}
  • Windows_x86(看完上面两个汇编,会发现Windows的CAS操作看起来友好多了,这里以jint为例)
// 为多核机器上的指令添加锁定前缀,不同的是,这里没有将锁前缀放在同一行,官方给出的理由是VC++不支持
#define LOCK_IF_MP(mp) __asm cmp mp, 0  \	// 比较
                       __asm je L0      \	// 跳转
                       __asm _emit 0xF0 \	// _emit的后面跟的是机器码:1111 0000,也就是LOCK指令
                       __asm L0:

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value, cmpxchg_memory_order order) {
  //判断系统是否是多处理器
  int mp = os::is_MP();
  __asm {
    mov edx, dest				// 将需要修改位置的地址存入edx
    mov ecx, exchange_value		// 将期望修改后的值存入ecx
    mov eax, compare_value		// 将比较的值(dest位置(地址)原始的值)存入eax
    LOCK_IF_MP(mp)				// 多核,则加锁
    //cmpxchg: 将edx寄存器中的值(dest),间接寻址后与寄存器eax的值进行比较:
    //		   如果相等,则将ecx寄存器中的值装载到dest对应的位置(地址),
    //         如果不相等,则将dest地址对应位置的值,赋值到eax寄存中。
    cmpxchg dword ptr [edx], ecx	
  }
}

4. 当对象处于重量级锁状态时

  // 判断当前对象是否处于重量级锁状态
  else if (mark->has_monitor()) {
    // 获得重量级锁
    monitor = mark->monitor();
    // 获取对象头
    temp = monitor->header();
    // 确保当前对象头处于无锁中立状态
    assert(temp->is_neutral(), "invariant");
    // 尝试获取hashCode
    hash = temp->hash();
    if (hash) {
      // 如果hashCode存在,则返回
      return hash;
    }
  }
  • mark->has_monitor()
    • 将64位的对象头和2(D)进行与操作,当结果不为0时,标记字中的lock位为10(B),也就是重量级锁
  enum { 
  		 ...
         monitor_value            = 2,
         ...
  };
  
  bool has_monitor() const {
    return ((value() & monitor_value) != 0);
  }

5. 本线程拥有此对象时

  // 判断本线程是否拥有此对象的锁
  else if (Self->is_lock_owned((address)mark->locker())) {
    // displaced并取出标记字
    temp = mark->displaced_mark_helper();
    // 验证当前对象是否中性
    assert(temp->is_neutral(), "invariant");
    // 将生成的hashCode放到标记字中,并将新的值给temp
    hash = temp->hash();
    if (hash) {
      // hashCode存在,则返回
      return hash;
    }
  }

6. 不符合上述条件,或上述条件执行完未返回时

  // 将锁膨胀以设置hashCode
  monitor = ObjectSynchronizer::inflate(Self, obj, inflate_cause_hash_code);
  // 加载锁头,看看有没有hashCode
  mark = monitor->header();
  // 验证膨胀后的对象标记字是否符合中性标准
  assert(mark->is_neutral(), "invariant");
  // 尝试获取hashCode
  hash = mark->hash();
  if (hash == 0) {
    // 如果hashCode还是没有,就自己使用get_next_hash(Self, obj)造一个
    hash = get_next_hash(Self, obj);
    // 将生成的hashCode放到标记字中,并将新的值给temp
    temp = mark->copy_set_hash(hash);
    // 验证...
    assert(temp->is_neutral(), "invariant");
    // 使用CAS操作修改标记字
    test = (markOop) Atomic::cmpxchg_ptr(temp, monitor, mark);
    if (test != mark) {
      // 在监视器中唯一更新对象头的情况是设置hashCode,如果更新时有新的操作,需要再次就该代码
      hash = test->hash();
      // 验证...
      assert(test->is_neutral(), "invariant");
      // 验证hashCode不为0
      assert(hash != 0, "Trivial unexpected object/monitor header usage.");
    }
  }
  // 最终,返回这个hashCode
  return hash;

以上,即为FastHashCode的源代码,但是,大家会发现,在这一部分没有具体生成hashCode的代码,下面,就来介绍我们真正的主角,get_next_hash(Thread * Self, oop obj)

(3). get_next_hash(Thread * Self, oop obj)源代码解读

在源代码中,我们会看到一个全局变量hashCode,我们可以通过如下设置来修改hashCode从而让JVM改变哈希的生成策略:

-XX:+UnlockExperimentalVMOptions -XX:hashCode=0

1. hashCode=0

if (hashCode == 0) {
    value = os::random();
}

它使用了os的random()方法

long os::random() {
  /* standard, well-known linear congruential random generator with
   * next_rand = (16807*seed) mod (2**31-1)
   * see
   * (1) "Random Number Generators: Good Ones Are Hard to Find",
   *      S.K. Park and K.W. Miller, Communications of the ACM 31:10 (Oct 1988),
   * (2) "Two Fast Implementations of the 'Minimal Standard' Random
   *     Number Generator", David G. Carta, Comm. ACM 33, 1 (Jan 1990), pp. 87-88.
  */
  const long a = 16807;
  const unsigned long m = 2147483647;
  const long q = m / a;        assert(q == 127773, "weird math");
  const long r = m % a;        assert(r == 2836, "weird math");

  // compute az=2^31p+q
  unsigned long lo = a * (long)(_rand_seed & 0xFFFF);
  unsigned long hi = a * (long)((unsigned long)_rand_seed >> 16);
  lo += (hi & 0x7FFF) << 16;

  // if q overflowed, ignore the overflow and increment q
  if (lo > m) {
    lo &= m;
    ++lo;
  }
  lo += hi >> 15;

  // if (p+q) overflowed, ignore the overflow and increment (p+q)
  if (lo > m) {
    lo &= m;
    ++lo;
  }
  return (_rand_seed = lo);
}

这是一个线性同余随机发生器,具体的计算公式如下:
X n + 1 = ( a X n + c )   m o d   m \mathtt{X}_{n+1}=(a\mathtt{X}_{n} + c) \ mod \ m Xn+1​=(aXn​+c) mod m
在这里, a = 16807 a=16807 a=16807, c = 0 c=0 c=0, m = 2 31 − 1 m=2^{31} - 1 m=231−1,但是,当同一时间有很多线程调用此方法时,生成的随机数将会是同一个。

2. hashCode=1|4

  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 addrBits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom;
  }
  else if (hashCode == 4) {
    value = cast_from_oop<intptr_t>(obj);
  }
template <class T> inline T cast_from_oop(oop o) {
  return (T)(CHECK_UNHANDLED_OOPS_ONLY((void*))o);
}

当hashCode=4时,哈希的值为oop的地址;当hashCode=1时,哈希会在此基础上通过算法(先位移,再与随机数异或)减少碰撞,使最终得到的值更加散列化。

3. hashCode=2

  else if (hashCode == 2) {
    value = 1;
  }

哈希值恒为1,主要用于灵敏度(对哈希值的敏感程度)测试。

4. hashCode=3

  else if (hashCode == 3) {
    value = ++GVars.hcSequence;
  }

自增常数,容易出现碰撞。

5. 其它hashCode(默认实现)

  else {
    // Marsaglia's xor-shift scheme with thread-specific state
    // This is probably the best overall implementation -- we'll
    // likely make this the default in future releases.
    unsigned t = Self->_hashStateX;
    t ^= (t << 11);
    Self->_hashStateX = Self->_hashStateY;
    Self->_hashStateY = Self->_hashStateZ;
    Self->_hashStateZ = Self->_hashStateW;
    unsigned v = Self->_hashStateW;
    v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    Self->_hashStateW = v;
    value = v;
  }

使用了Marsaglia’s xor-shift算法,使用一个与当前线程有关的随机数和三个确定值生成哈希值,具有不错的性能和良好的散列性。

6. 最终验证

  //主要用来防止value太长
  value &= markOopDesc::hash_mask;
  //当value为0时,给一个固定值
  if (value == 0) value = 0xBAD;
  //验证value不为0
  assert(value != markOopDesc::no_hash, "invariant");
  TEVENT(hashCode: GENERATE);
  return value;

至此,我们终于获得了哈希值。


参考文章

写在最后

看到这里,相信大家对Java中Object类的hashCode()方法已经有所了解了,也许你期望的答案仅仅是第三点的具体计算方式,但是在读完全文后你会发现,一个看似简单的hashCode竟然会涉及到JVM底层这么多东西。就像计算机中的一些协议,我们在使用时可能很少会接触到真正底层的实现,那是因为有许许多多的计算机科学家已经帮我们完成封装,而我们需要做的仅仅是使用它,也许在当今快节奏的工作生活中,知道如何使用就可以为我们带来最高的效率,但是,真正让我喜欢上计算机、喜欢上编程的,恰恰是这些巨人敲下的一个一个字母。

—— 一个正在努力的大四学生

上一篇:golang面向对象分析


下一篇:赶紧Mark!再也不怕领导偷偷出现在身后了,你才是最强摸鱼王