细说 Java hashCode

前言

写过 Java 程序的同学一定都知道 hashCode 方法,它是 Object 对象的一个 native 方法。无论是我们平常使用的 HashMap 还是重写 equals 方法的时候,都会接触到 hashCode 方法,那么它究竟是怎么生成的,又有什么作用呢?笔者带着这个疑问开始探寻。

hashCode 方法的定义

jdk api 中 关于 hashCode 有如下说明:

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.
As much as is reasonably practical, 
the hashCode method defined by class Object does return distinct integers for distinct objects. 
(This is typically implemented by converting the internal address of the object into an integer, 
    but this implementation technique is not required by the JavaTM programming language.)

其大致意思如下

只要在Java应用程序的执行过程中多次调用同一个对象,
hashCode方法必须始终返回相同的整数,
前提是在对象的equals比较中没有使用的信息被修改。  
从应用程序的一次执行到同一应用程序的另一次执行,此整数不必保持一致。  

如果两个对象按照equals(Object)方法相等,
那么在两个对象的每一个上调用hashCode方法必须产生相同的整数结果。  
如果两个对象根据equals(java.lang.Object)方法不相等,
则不要求对两个对象中的每个对象调用hashCode方法都必须产生不同的整数结果。  
但是,程序员应该知道,为不相等的对象生成不同的整数结果可以提高散列表的性能。  

尽可能多地合理实用,由类Object定义的hashCode方法确实为不同的对象返回不同的整数。  
这通常通过将对象的内部地址转换为整数来实现,但JavaTM编程语言不需要此实现技术。

所以由上可以得到两条有用的信息,同一个对象 hashcode 的值在一次运行中一定相等,并且不同对象的 hashcode 一定不同,但是他还备注通常使用内部地址转换,但是 JAVA 不是使用这种方式实现的,那么怎么实现的呢?

hashCode 实现原理

hashcode 源码

OpenJDK 的源码可以直接查看,所以我们就选择查看一下其源码一看究竟。 我们可以看到 src/share/vm/prims/jvm.hsrc/share/vm/prims/jvm.cpp两个文件中有关于 hashcode 的说明如下:

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

我们继续进入 FashHashCode里面查看,其位于 src/share/vm/runtime/synchronizer.cpp文件,相对代码比较多,我们只摘取关键部分:

// Inflate the monitor to set hash code
  monitor = ObjectSynchronizer::inflate(Self, obj);
  // Load displaced header and check it has hash code
  mark = 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 header
    assert (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 code
      hash = test->hash();
      assert (test->is_neutral(), "invariant") ;
      assert (hash != 0, "Trivial unexpected object/monitor header usage.");
    }
  }
  // We finally get the hash
  return hash;

monitor 相关代码我们先略过不理,通过 if 语句我们可以看出,当 hash为0时候需要调用 get_next_hash 生成一个新的 hash,那么我们便可以继续前行。

static inline intptr_t get_next_hash(Thread * Self, oop obj) {
  intptr_t value = 0 ;
  if (hashCode == 0) {
     // This form uses an unguarded global Park-Miller RNG,
     // so it's possible for two threads to race and generate the same RNG.
     // On MP system we'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 addrBits = cast_from_oop<intptr_t>(obj) >> 3 ;
     value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
  } else
  if (hashCode == 2) {
     value = 1 ;            // for sensitivity testing
  } else
  if (hashCode == 3) {
     value = ++GVars.hcSequence ;
  } else
  if (hashCode == 4) {
     value = cast_from_oop<intptr_t>(obj) ;
  } 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 ;
  }
  value &= markOopDesc::hash_mask;
  if (value == 0) value = 0xBAD ;
  assert (value != markOopDesc::no_hash, "invariant") ;
  TEVENT (hashCode: GENERATE) ;
  return value;

通过上述代码我们看到,其实 hashCode 的生成有6中方式

  1. 随机数
  2. 对象的内存地址的函数
  3. 固定值,这个只是为了进行灵敏度测试
  4. 递增序列
  5. int类型的该对象的内存地址
  6. 结合当前线程和xorshift生成

通过 globals.hpp 我们可以发现,JDK8 默认为5,也就是最后一种。 product(intx,hashCode,5,"(Unstable) select hashCode generation algorithm") 当然,OpenJDK6,7中用的都是第一种方案,那么问题又来了,既然都是随机数,那么怎么确保每次都一样的呢?

对象头

这里就需要引入一个 对象头的概念,每次对象生成以后,都需要找一个地方存储一下这个对象的hashCode和锁信息,这就是 对象头,英文称之为 MarkWord。这样一来我们就明白了,每次生成对象以后都会把它的 hashCode存起来,这样无论对象怎么在新生代,老年代之间 游走都不会改变其 hashCode的值,然而事实并没有那么简单。

偏向锁

这时候我们翻回来看刚才略过的内容, ObjectSynchronizer::FastHashCode()里面的其他逻辑。

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");
    }
  }

由上述代码我们可以得知,当前对象处于 偏向锁时,会清除 偏向锁通过从 上面取回 MarkWord 信息。为什么提到取回呢?之前消失了吗?是的,现在就需要解释一下 偏向锁了。 Hotspot 的作者经过以往的研究发现大多数情况下锁不仅不存在多线程竞争,而且总是由同一线程多次获得,为了让线程获得锁的代价更低而引入 了偏向锁。当一个线程访问同步块并获取锁时,会在对象头和栈帧中的锁记录里存储锁偏向的线程 ID,以后该线程在进入和退出同步块时不需要花费 CAS 操作来加锁和解锁,而只需简单的测试一下对象头的 MarkWord 里是否存储着指向当前线程的偏向锁,如果测试成功,表示线程已经获得了锁,如果测试失败,则需要再测试下 MarkWord 中偏向锁的标识是否设置成 1(表示当前是偏向锁),如果没有设置,则使用 CAS 竞争锁,如果设置了,则尝试使用 CAS 将对象头的偏向锁指向当前线程。所以我们便知道为什么有 取回这个概念了。然而代码带没有结束。

轻量级锁

轻量级锁相对比较简单, JVM会在当前的线程栈桢中创建用于存放锁的空间,同时将对象头中的 MarkWord复制到锁记录中,也称作 DisplacedMarkWord。比较复杂的是 重量级锁。

重量级锁

这个时候如果多个线程来竞争资源,就会发生 锁膨胀,这样因为需要保存竞争资源需要 wait的线程和相关信息,就引入了 monitor的概念。于是这时候就把 MarkWord存放到了 Monitor里面,当然 Monitor不仅仅用于存储对象的 MarkWord,具体的作用就不是本文的重点了。

hashCode 的用途

hashCode 的唯一性决定了他可以用来生成 HashMap的key,同时也能判断对象是否为同一个对象。另外我们再重写他的时候要多加注意,因为 JVM会根据它做一些性能优化。

总结

此文为笔者学习 hashCode 的笔记,如有问题欢迎指正。

参考文献

OpenJDK 源码

Oracle JDK Docs

本文分享自微信公众号 - Java架构沉思录(code-thinker)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 拜托,不要再问我三次握手和四次挥手了!

    三次握手和四次挥手是各个公司常见的考点,也具有一定的水平区分度,也被一些面试官作为热身题。很多小伙伴说这个问题刚开始回答的挺好,但是后面越回答越冒冷汗,最后就歇...

    黄泽杰
  • 计算机网络常见面试点,都在这里了!

    互联网服务提供商 ISP 可以从互联网管理机构获得许多 IP 地址,同时拥有通信线路以及路由器等联网设备,个人或机构向 ISP 缴纳一定的费用就可以接入互联网。

    黄泽杰
  • 浅析 Nginx 网络事件

    Nginx 是一个事件驱动的框架,所谓事件主要指的是网络事件,Nginx 每个网络连接会对应两个网络事件,一个读事件一个写事件。在深入了解 Nginx 各种原理...

    黄泽杰
  • YOLO Implementation

    使用OpenCV的cv2.imread()函数加载我们的图像。 因为,此函数将图像加载为BGR,我们将图像转换为RGB,以便我们可以使用正确的颜色显示它们 网...

    小飞侠xp
  • Azkaban 2.5 Documentation

    Azkaban was implemented at LinkedIn to solve the problem of Hadoop job dependenc...

    WindWant
  • 使用社交媒体上粉丝的帖子来衡量品牌之间的相似性(Multimedia)

    在这篇论文中,我们提出了一种新的测量方法,通过社交网络服务(SNS)上的品牌追随者的帖子来估计品牌之间的相似性。我们的方法是为了探索客户可能共同购买的品牌而开发...

    李欣颖6837176
  • 图像拼接--A multiresolution spline with application to image mosaics

    A multiresolution spline with application to image mosaics 《Acm Trans on Graphi...

    用户1148525
  • Using Gaussian processes for regression降维之高斯过程

    In this recipe, we'll use the Gaussian process for regression. In the linear mod...

    到不了的都叫做远方
  • 交互语义学理论(CS)

    本文的思想是通过一种依赖于信息交换的机制来描述。在离散系统间的交互中,使用协议对交换的字符冠以相同的命名。用交互形式(GIF)的游戏决策来补充不确定性协议,使其...

    N乳酸菌
  • PAT 1010 Radix

    1010. Radix (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 St...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券