介绍

散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。
在Java中，每个Object都有一个hashCode方法，有需要可以进行重写。

Object类的hashCode

  1. public native int hashCode();

可以看到此方法为native方法，底层是调用了C++的函数，因为是在Object类中，翻开JDK源码的Object.c的定义

  1. #include <stdio.h>
  2. #include <signal.h>
  3. #include <limits.h>
  5. #include "jni.h"
  6. #include "jni_util.h"
  7. #include "jvm.h"
  9. #include "java_lang_Object.h"
  11. static JNINativeMethod methods[] = {
  12.     {"hashCode",    "()I",                    (void *)&JVM_IHashCode},
  13.     {"wait",        "(J)V",                   (void *)&JVM_MonitorWait},
  14.     {"notify",      "()V",                    (void *)&JVM_MonitorNotify},
  15.     {"notifyAll",   "()V",                    (void *)&JVM_MonitorNotifyAll},
  16.     {"clone",       "()Ljava/lang/Object;",   (void *)&JVM_Clone},
  17. };
  19. JNIEXPORT void JNICALL
  20. Java_java_lang_Object_registerNatives(JNIEnv *env, jclass cls)
  21. {
  22.     (*env)->RegisterNatives(env, cls,
  23.                             methods, sizeof(methods)/sizeof(methods[0]));
  24. }
  26. JNIEXPORT jclass JNICALL
  27. Java_java_lang_Object_getClass(JNIEnv *env, jobject this)
  28. {
  29.     if (this == NULL) {
  30.         JNU_ThrowNullPointerException(env, NULL);
  31.         return 0;
  32.     } else {
  33.         return (*env)->GetObjectClass(env, this);
  34.     }
  35. }

可以看到hashCode方法实际上调用的是JVM_IHashCode这个方法。查找这个方法发现在jvm.cpp中定义

  1. // java.lang.Object ///////////////////////////////////////////////
  4. JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
  5.   JVMWrapper("JVM_IHashCode");
  6.   // as implemented in the classic virtual machine; return 0 if object is NULL
  7.   return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
  8. JVM_END

从这里看出JVM_IHashCode实际又是调用的ObjectSynchronizer::FastHashCode这个方法，继续查找到这个方法的定义在synchronizer.cpp中：

FastHashCode函数

  1. intptr_t ObjectSynchronizer::FastHashCode (Thread * Self, oop obj) {
  2.    // 如果使用了偏向锁
  3.   if (UseBiasedLocking) {
  4.     // NOTE: many places throughout the JVM do not expect a safepoint
  5.     // to be taken here, in particular most operations on perm gen
  6.     // objects. However, we only ever bias Java instances and all of
  7.     // the call sites of identity_hash that might revoke biases have
  8.     // been checked to make sure they can handle a safepoint. The
  9.     // added check of the bias pattern is to avoid useless calls to
  10.     // thread-local storage.
  11.      // 对象处于偏向状态
  12.     if (obj->mark()->has_bias_pattern()) {
  13.       // Box and unbox the raw reference just in case we cause a STW safepoint.
  14.       Handle hobj (Self, obj) ;
  15.       // Relaxing assertion for bug 6320749.
  16.       assert (Universe::verify_in_progress() ||
  17.               !SafepointSynchronize::is_at_safepoint(),
  18.              "biases should not be seen by VM thread here");
  19.       // 撤销偏向锁
  20.       BiasedLocking::revoke_and_rebias(hobj, false, JavaThread::current());
  21.       obj = hobj() ;
  22.       // 保证对象没有偏向锁
  23.       assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");
  24.     }
  25.   }
  27.   // hashCode() is a heap mutator ...
  28.   // Relaxing assertion for bug 6320749.
  29.   // 达到安全点
  30.   assert (Universe::verify_in_progress() ||
  31.           !SafepointSynchronize::is_at_safepoint(), "invariant") ;
  32.   // 是java线程
  33.   assert (Universe::verify_in_progress() ||
  34.           Self->is_Java_thread() , "invariant") ;
  35.   // 线程没有被阻塞
  36.   assert (Universe::verify_in_progress() ||
  37.          ((JavaThread *)Self)->thread_state() != _thread_blocked, "invariant") ;
  39.   ObjectMonitor* monitor = NULL;
  40.   markOop temp, test;
  41.   intptr_t hash;
  42.   // 读出一个稳定的mark，如果对象处于锁膨胀，那么等待锁膨胀完毕再读
  43.   markOop mark = ReadStableMark (obj);
  45.    // 判断没有处于偏向锁状态
  46.   // object should remain ineligible for biased locking
  47.   assert (!mark->has_bias_pattern(), "invariant") ;
  49.    // 处于无锁状态 
  50.   if (mark->is_neutral()) {
  51.     hash = mark->hash();              // this is a normal header
  52.     // 有hash值直接返回
  53.     if (hash) {                       // if it has hash, just return it
  54.       return hash;
  55.     }
  56.     // 没有hash值，调用get_next_hash函数计算hash值
  57.     hash = get_next_hash(Self, obj);  // allocate a new hash code
  58.     temp = mark->copy_set_hash(hash); // merge the hash code into header
  59.     // use (machine word version) atomic operation to install the hash
  60.     test = (markOop) Atomic::cmpxchg_ptr(temp, obj->mark_addr(), mark);
  61.     if (test == mark) {
  62.       return hash;
  63.     }
  64.     // If atomic operation failed, we must inflate the header
  65.     // into heavy weight monitor. We could add more code here
  66.     // for fast path, but it does not worth the complexity.
  67.   } else if (mark->has_monitor()) {
  68.     monitor = mark->monitor();
  69.     temp = monitor->header();
  70.     assert (temp->is_neutral(), "invariant") ;
  71.     hash = temp->hash();
  72.     if (hash) {
  73.       return hash;
  74.     }
  75.     // Skip to the following code to reduce code size
  76.   } else if (Self->is_lock_owned((address)mark->locker())) {
  77.     temp = mark->displaced_mark_helper(); // this is a lightweight monitor owned
  78.     assert (temp->is_neutral(), "invariant") ;
  79.     hash = temp->hash();              // by current thread, check if the displaced
  80.     if (hash) {                       // header contains hash code
  81.       return hash;
  82.     }
  83.     // WARNING:
  84.     //   The displaced header is strictly immutable.
  85.     // It can NOT be changed in ANY cases. So we have
  86.     // to inflate the header into heavyweight monitor
  87.     // even the current thread owns the lock. The reason
  88.     // is the BasicLock (stack slot) will be asynchronously
  89.     // read by other threads during the inflate() function.
  90.     // Any change to stack may not propagate to other threads
  91.     // correctly.
  92.   }
  94.   // Inflate the monitor to set hash code
  95.   monitor = ObjectSynchronizer::inflate(Self, obj);
  96.   // Load displaced header and check it has hash code
  97.   mark = monitor->header();
  98.   assert (mark->is_neutral(), "invariant") ;
  99.   hash = mark->hash();
  100.   if (hash == 0) {
  101.     hash = get_next_hash(Self, obj);
  102.     temp = mark->copy_set_hash(hash); // merge hash code into header
  103.     assert (temp->is_neutral(), "invariant") ;
  104.     test = (markOop) Atomic::cmpxchg_ptr(temp, monitor, mark);
  105.     if (test != mark) {
  106.       // The only update to the header in the monitor (outside GC)
  107.       // is install the hash code. If someone add new usage of
  108.       // displaced header, please update this code
  109.       hash = test->hash();
  110.       assert (test->is_neutral(), "invariant") ;
  111.       assert (hash != 0, "Trivial unexpected object/monitor header usage.");
  112.     }
  113.   }
  114.   // We finally get the hash
  115.   return hash;
  116. }

以上分析出在对象头没有hash值的情况下，会调用get_next_hash函数计算出hash值，get_next_hash的定义如下：

get_next_hash函数

  1. static inline intptr_t get_next_hash(Thread * Self, oop obj) {
  2.   intptr_t value = 0 ;
  3.   if (hashCode == 0) {
  4.      // This form uses an unguarded global Park-Miller RNG,
  5.      // so it's possible for two threads to race and generate the same RNG.
  6.      // On MP system we'll have lots of RW access to a global, so the
  7.      // mechanism induces lots of coherency traffic.
  8.      // 系统产生随机数
  9.      value = os::random() ;
  10.   } else
  11.   if (hashCode == 1) {
  12.      // This variation has the property of being stable (idempotent)
  13.      // between STW operations.  This can be useful in some of the 1-0
  14.      // synchronization schemes.
  15.      // 内存地址做移位再和一个随机数做异或
  16.      intptr_t addrBits = cast_from_oop<intptr_t>(obj) >> 3 ;
  17.      value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
  18.   } else
  19.   if (hashCode == 2) {
  20.      // 固定返回1
  21.      value = 1 ;            // for sensitivity testing
  22.   } else
  23.   if (hashCode == 3) {
  24.      // 序列自增
  25.      value = ++GVars.hcSequence ;
  26.   } else
  27.   if (hashCode == 4) {
  28.      // 返回内存地址
  29.      value = cast_from_oop<intptr_t>(obj) ;
  30.   } else {
  31.      // Marsaglia's xor-shift 随机数算法
  32.      // Marsaglia's xor-shift scheme with thread-specific state
  33.      // This is probably the best overall implementation -- we'll
  34.      // likely make this the default in future releases.
  35.      unsigned t = Self->_hashStateX ;
  36.      t ^= (t << 11) ;
  37.      Self->_hashStateX = Self->_hashStateY ;
  38.      Self->_hashStateY = Self->_hashStateZ ;
  39.      Self->_hashStateZ = Self->_hashStateW ;
  40.      unsigned v = Self->_hashStateW ;
  41.      v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
  42.      Self->_hashStateW = v ;
  43.      value = v ;
  44.   }
  46.   value &= markOopDesc::hash_mask;
  47.   if (value == 0) value = 0xBAD ;
  48.   assert (value != markOopDesc::no_hash, "invariant") ;
  49.   TEVENT (hashCode: GENERATE) ;
  50.   return value;
  51. }

可以看到有6种hashCode的生成方法，根据hashCode变量指定不同的生成方案，可以通过在JVM启动参数中添加-XX:hashCode=?，改变默认的hashCode计算方式。
对于OpenJDK8，默认是用最后一种，使用的是Marsaglia’s xor-shift随机数算法。

  1. product(intx, hashCode, 5,"(Unstable) select hashCode generation algorithm")

此方法使用了三个固定值和一个随机数，在thread.cpp中定义

  1.  // thread-specific hashCode stream generator state - Marsaglia shift-xor form
  2. _hashStateX = os::random() ;
  3. _hashStateY = 842502087 ;
  4. _hashStateZ = 0x8767 ;    // (int)(3579807591LL & 0xffff) ;
  5. _hashStateW = 273326509 ;

所以，对于JDK8，对象在没有重写hashCode的情况下，hashCode的生成和内存地址无关，默认是根据Marsaglia’s xor-shift算法随机生成的。