面试必问的HashCode技术内幕

3 hashCode的内幕

tips：面试常问/常用/常出错
hashCode到底是什么？是不是对象的内存地址？

1)  直接用内存地址？

目标：通过一个Demo验证这个hasCode到底是不是内存地址

1. public native int hashCode();

复制代码

com.hashcode.HashCodeTest

1. package com.hashcode;
3. import org.openjdk.jol.vm.VM;
5. import java.util.ArrayList;
6. import java.util.List;
9. public class HashCodeTest {
10.     //目标：只要发生重复，说明hashcode不是内存地址，但还需要证明（JVM代码证明）
11.     public static void main(String[] args) {
12.         List<Integer> integerList = new ArrayList<Integer>();
13.         int num = 0;
14.         for (int i = 0; i < 150000; i++) {
15.             //创建新的对象
16.             Object object = new Object();
17.             if (integerList.contains(object.hashCode())) {
18.                 num++;//发生重复（内存地址肯定不会重复）
19.             } else {
20.                 integerList.add(object.hashCode());//没有重复
21.             }
22.         }
23.         System.out.println(num + "个hashcode发生重复");
24.         System.out.println("List合计大小" + integerList.size() + "个");
26.     }
27. }

复制代码

15万个循环，发生了重复，说明hashCode不是内存地址（严格的说，肯定不是直接取的内存地址）

思考一下，为什么不能直接用内存地址呢？

• 提示：jvm垃圾收集算法，对象迁移……
  

那么它到底是什么？如何生成的呢
2) 不是地址那在哪里？

既然不是内存地址，那一定在某个地方存着，那在哪里存着呢？
答案：在对象头里！（画图。类在jvm内存中的布局）

对象头分为两部分，一部分是上面指向class描述的地址Klass，另一部分就是Markword
而我们这里要找的hashcode在Markword里！（标记位意义，不用记！）
32位：

64位：

3) 什么时候生成的？

new的瞬间就有hashcode了吗？？
show me the code！我们用代码验证

1. package com.hashcode;
3. import org.openjdk.jol.info.ClassLayout;
4. import org.openjdk.jol.vm.VM;
6. public class ShowHashCode {
8.         public static void main(String[] args) {
9.             ShowHashCode a = new ShowHashCode();
10.             //jvm的信息
11.             System.out.println(VM.current().details());
12.             System.out.println("-------------------------");
13.             //调用之前打印a对象的头信息
14.             //以表格的形式打印对象布局
15.             System.out.println(ClassLayout.parseInstance(a).toPrintable());
17.             System.out.println("-------------------------");
18.             //调用后再打印a对象的hashcode值
19.             System.out.println(Integer.toHexString(a.hashCode()));
20.             System.out.println(ClassLayout.parseInstance(a).toPrintable());
22.             System.out.println("-------------------------");
23.             //有线程加重量级锁的时候，再来看对象头
24.             new Thread(()->{
25.                 try {
26.                     synchronized (a){
27.                         Thread.sleep(5000);
28.                     }
29.                 } catch (InterruptedException e) {
30.                     e.printStackTrace();
31.                 }
32.             }).start();
33.             System.out.println(Integer.toHexString(a.hashCode()));
34.             System.out.println(ClassLayout.parseInstance(a).toPrintable());
35.         }
37. }

复制代码

结果分析


结论：在你没有调用的时候，这个值是空的，当第一次调用hashCode方法时，会生成，加锁以后，不知道去哪里了……
4) 怎么生成的？

接上文  ,  我们追究一下，它详细的生成及移动过程。
我们都知道，这货是个本地方法

1. public native int hashCode();

复制代码

那就需要借助上面提到的办法，通过JVM虚拟机源码，查看hashcode的生成
1）先从Object.c开始找hashCode映射
src\share\native\java\lang\Object.c

1. JNIEXPORT void JNICALL//jni调用
2. //全路径：java_lang_Object_registerNatives是java对应的包下方法
3. Java_java_lang_Object_registerNatives(JNIEnv *env, jclass cls)
4. {
5.          //jni环境调用；下面的参数methods对应的java方法
6.     (*env)->RegisterNatives(env, cls,
7.                             methods, sizeof(methods)/sizeof(methods[0]));
8. }

复制代码

JAVA--------------------->C++函数对应

1. //JAVA方法（返回值）----->C++函数对象
2. static JNINativeMethod methods[] = {
3.         //JAVA方法        返回值  （参数）                          c++函数
4.     {"hashCode",    "()I",                    (void *)&JVM_IHashCode},
5.     {"wait",        "(J)V",                   (void *)&JVM_MonitorWait},
6.     {"notify",      "()V",                    (void *)&JVM_MonitorNotify},
7.     {"notifyAll",   "()V",                    (void *)&JVM_MonitorNotifyAll},
8.     {"clone",       "()Ljava/lang/Object;",   (void *)&JVM_Clone},
9. };

复制代码

JVM_IHashCod在哪里呢？
2）全局检索JVM_IHashCode
完全搜不到这个方法名，只有这个还凑合有点像，那这是个啥呢？

src\share\vm\prims\jvm.cpp

1. /*
2. JVM_ENTRY is a preprocessor macro that
3. adds some boilerplate code that is common for all functions of HotSpot JVM API.
4. This API is a connection layer between the native code of JDK class library and the JVM.
6. JVM_ENTRY是一个预加载宏，增加一些样板代码到jvm的所有function中
7. 这个api是位于本地方法与jdk之间的一个连接层。
9. 所以，此处才是生成hashCode的逻辑！
10. */
11. JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
12.   JVMWrapper("JVM_IHashCode");
13.   //调用了ObjectSynchronizer对象的FastHashCode
14. return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
15. JVM_END

复制代码

3）继续，ObjectSynchronizer::FastHashCode


先说生成流程，留个印象：

1. intptr_t ObjectSynchronizer::FastHashCode (Thread * Self, oop obj) {
2.         //是否开启了偏向锁(Biased：偏向，倾向)
3.   if (UseBiasedLocking) {
4.         //如果当前对象处于偏向锁状态
5.     if (obj->mark()->has_bias_pattern()) {
6.       Handle hobj (Self, obj) ;
7.       assert (Universe::verify_in_progress() ||
8.               !SafepointSynchronize::is_at_safepoint(),
9.              "biases should not be seen by VM thread here");
10.                         //那么就撤销偏向锁（达到无锁状态，revoke：废除）
11.       BiasedLocking::revoke_and_rebias(hobj, false, JavaThread::current());
12.       obj = hobj() ;
13.                   //断言下，看看是否撤销成功（撤销后为无锁状态）
14.       assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now");
15.     }
16.   }
18.   // ……
20.   ObjectMonitor* monitor = NULL;
21.   markOop temp, test;
22.   intptr_t hash;
23.   //读出一个稳定的mark;防止对象obj处于膨胀状态；
24.   //如果正在膨胀，就等他膨胀完毕再读出来
25.   markOop mark = ReadStableMark (obj);
27.         //是否撤销了偏向锁（也就是无锁状态）（neutral：中立，不偏不斜的）
28.   if (mark->is_neutral()) {
29.     //从mark头上取hash值
30.     hash = mark->hash();
31.            //如果有，直接返回这个hashcode（xor）
32.     if (hash) {                       // if it has hash, just return it
33.       return hash;
34.     }
35.                 //如果没有就新生成一个(get_next_hash)
36.     hash = get_next_hash(Self, obj);  // allocate a new hash code
37.     //生成后，原子性设置，将hash放在对象头里去，这样下次就可以直接取了
38.     temp = mark->copy_set_hash(hash); // merge the hash code into header
39.     // use (machine word version) atomic operation to install the hash
40.     test = (markOop) Atomic::cmpxchg_ptr(temp, obj->mark_addr(), mark);
41.     if (test == mark) {
42.       return hash;
43.     }
44.     // If atomic operation failed, we must inflate the header
45.     // into heavy weight monitor. We could add more code here
46.     // for fast path, but it does not worth the complexity.
47.     //如果已经升级成了重量级锁，那么找到它的monitor
48.     //也就是我们所说的内置锁(objectMonitor)，这是c里的数据类型
49.     //因为锁升级后，mark里的bit位已经不再存储hashcode，而是指向monitor的地址
50.     //而升级的markword呢？被移到了c的monitor里
51.   } else if (mark->has_monitor()) {
52.     //沿着monitor找header，也就是对象头
53.     monitor = mark->monitor();
54.     temp = monitor->header();
55.     assert (temp->is_neutral(), "invariant") ;
56.     //找到header后取hash返回
57.     hash = temp->hash();
58.     if (hash) {
59.       return hash;
60.     }
61.     // Skip to the following code to reduce code size
62.   } else if (Self->is_lock_owned((address)mark->locker())) {
63.     //轻量级锁的话，也是从java对象头移到了c里，叫helper
64.     temp = mark->displaced_mark_helper(); // this is a lightweight monitor owned
65.     assert (temp->is_neutral(), "invariant") ;
66.     hash = temp->hash();              // by current thread, check if the displaced
67.     //找到，返回
68.     if (hash) {                       // header contains hash code
69.       return hash;
70.     }
71.   }
72.        
73.   
74.   ......略

复制代码

问：
为什么要先撤销偏向锁到无锁状态，再来生成hashcode呢？这跟锁有什么关系？
答：
mark word里，hashcode存储的字节位置被偏向锁给占了！偏向锁存储了锁持有者的线程id
（参考上面的markword图）
扩展：关于hashCode的生成算法（了解）

1. // hashCode() generation :
2. // 涉及到c++算法领域，感兴趣的同学自行研究
3. // Possibilities:
4. // * MD5Digest of {obj,stwRandom}
5. // * CRC32 of {obj,stwRandom} or any linear-feedback shift register function.
6. // * A DES- or AES-style SBox[] mechanism
7. // * One of the Phi-based schemes, such as:
8. //   2654435761 = 2^32 * Phi (golden ratio)
9. //   HashCodeValue = ((uintptr_t(obj) >> 3) * 2654435761) ^ GVars.stwRandom ;
10. // * A variation of Marsaglia's shift-xor RNG scheme.
11. // * (obj ^ stwRandom) is appealing, but can result
12. //   in undesirable regularity in the hashCode values of adjacent objects
13. //   (objects allocated back-to-back, in particular).  This could potentially
14. //   result in hashtable collisions and reduced hashtable efficiency.
15. //   There are simple ways to "diffuse" the middle address bits over the
16. //   generated hashCode values:
17. //
18. static inline intptr_t get_next_hash(Thread * Self, oop obj) {
19.   intptr_t value = 0 ;
20.   if (hashCode == 0) {
21.      // This form uses an unguarded global Park-Miller RNG,
22.      // so it's possible for two threads to race and generate the same RNG.
23.      // On MP system we'll have lots of RW access to a global, so the
24.      // mechanism induces lots of coherency traffic.
25.      value = os::random() ;//返回随机数
26.   } else if (hashCode == 1) {
27.      // This variation has the property of being stable (idempotent)
28.      // between STW operations.  This can be useful in some of the 1-0
29.      // synchronization schemes.
30.      //和地址相关，但不是地址；右移+异或算法
31.      intptr_t addrBits = cast_from_oop<intptr_t>(obj) >> 3 ;
32.      value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;//随机数位移异或计算
33.   } else  if (hashCode == 2) {
34.      value = 1 ;            // 返回1
35.   } else  if (hashCode == 3) {
36.      value = ++GVars.hcSequence ;//返回一个Sequence序列号
37.   } else  if (hashCode == 4) {
38.      value = cast_from_oop<intptr_t>(obj) ;//也不是地址
39.   } else {
40.      //常用
41.      // Marsaglia's xor-shift scheme with thread-specific state
42.      // This is probably the best overall implementation -- we'll
43.      // likely make this the default in future releases.
44.      //马萨利亚教授写的xor-shift 随机数算法（异或随机算法)
45.      unsigned t = Self->_hashStateX ;
46.      t ^= (t << 11) ;
47.      Self->_hashStateX = Self->_hashStateY ;
48.      Self->_hashStateY = Self->_hashStateZ ;
49.      Self->_hashStateZ = Self->_hashStateW ;
50.      unsigned v = Self->_hashStateW ;
51.      v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
52.      Self->_hashStateW = v ;
53.      value = v ;
54.   }

复制代码

5）总结

通过分析虚拟机源码我们证明了hashCode不是直接用的内存地址，而是采取一定的算法来生成
hashcode值的存储在mark word里，与锁共用一段bit位，这就造成了跟锁状态相关性

• 如果是偏向锁：
  

一旦调用hashcode，偏向锁将被撤销，hashcode被保存占位mark word，对象被打回无锁状态

• 那偏偏这会就是有线程硬性使用对象的锁呢？
  

对象再也回不到偏向锁状态而是升级为重量级锁。hash code跟随mark word被移动到c的object monitor，从那里取

本文由传智教育博学谷 - 狂野架构师教研团队发布
如果本文对您有帮助，欢迎关注和点赞；如果您有任何建议也可留言评论或私信，您的支持是我坚持创作的动力
转载请注明出处！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！