JVM的字符串常量池和hashcode相关学习过程总结

2023-02-25 本文已影响0人 still_loving

Ⅰ. 背景

在研究String不可变特性的时候，因为比较好奇有关常量池的相关概念，就深入了一下到JVM源码进行了探究
在研究常量池的过程中，不可避免的又涉及到了Java中hashCode的相关概念，所以就顺带看了下JVM中关于hashCode的本地方法实现
本篇主要是记录一下整个探查的过程，算是给自己一个记录，方便后续查阅。

Ⅱ. 介绍

2.1 字符串常量池

Step 1

提到字符串常量池，我比较好奇它底层的存储数据格式到底是怎么样的？因此就需要深入去探查一下。因为是字符串常量池，所以就自然想到了String的一个方法 intern()，它的作用就是将字符串对象放入到字符常量池中，该方法是一个native方法，因此去找了下openJDK源码，这里用到的是github上openjdk的jdk8-b120 的tag版本。
String类的全部包名：java.lang.String，所以可以去找open JDK源码中share/native目录下按照包名往下找。
下载并打开该项目后，可以在jdk目录下：

image.png

native目录下一般存放的都是JDK中一些本地方法的对应C语言调用，这里要看的是String类下的intern方法，因此找到java/lang/String.c文件：

JNIEXPORT jobject JNICALL
Java_java_lang_String_intern(JNIEnv *env, jobject this)
{
    return JVM_InternString(env, this);
}

这里仅仅只是一个调用，具体的实现还得到具体的JVM实现厂商的源代码中去寻找，最常见的肯定就是hotspot虚拟机，这里可以到hotspot目录下去搜索相关实现。

这里全局搜一下JVM_InternString这个内容，可以发现在hotspot的src/share/vm/prims/jvm.cpp中出现了：

// String support ///////////////////////////////////////////////////////////////////////////

JVM_ENTRY(jstring, JVM_InternString(JNIEnv *env, jstring str))
  JVMWrapper("JVM_InternString");
  JvmtiVMObjectAllocEventCollector oam;
  if (str == NULL) return NULL;
  oop string = JNIHandles::resolve_non_null(str);
  oop result = StringTable::intern(string, CHECK_NULL);
  return (jstring) JNIHandles::make_local(env, result);
JVM_END

可以发现有一个StringTable调用了intern方法，那么就可以在项目中全局搜一下 class StringTable这个关键词，就可以看到有一个symbolTable.hpp文件里面出现了这个定义：

class StringTable : public Hashtable<oop, mtSymbol> {
    ......
    static oop intern(oop string, TRAPS);//这个方法的签名和上面的调用是一致的
    ......
}

这里可以看到，StringTable其实就是一个hashTable，内部有一个intern的静态方法，所以可以到对应的cpp文件里面找到具体的实现，下面贴出了部分源码，从上到下是按照一个方法的调用链贴出来的：

oop StringTable::intern(oop string, TRAPS)
{
  if (string == NULL) return NULL;
  ResourceMark rm(THREAD);
  int length;
  Handle h_string (THREAD, string);
  jchar* chars = java_lang_String::as_unicode_string(string, length, CHECK_NULL);
  oop result = intern(h_string, chars, length, CHECK_NULL); // 这里调用了当前文件内另外一个intern方法
  return result;
}

oop StringTable::intern(Handle string_or_null, jchar* name,
                        int len, TRAPS) {
    ......
    // 这里的the_table返回的就是当前的StringTable，所以它是调用了StringTable内部的那个basic_add方法
    return the_table()->basic_add(index, string, name, len,
                              hashValue, CHECK_NULL);
}

oop StringTable::basic_add(int index_arg, Handle string, jchar* name,
                           int len, unsigned int hashValue_arg, TRAPS) {
    ......
    HashtableEntry<oop, mtSymbol>* entry = new_entry(hashValue, string());
    add_entry(index, entry);
    return string();                           
}

这里可以看到，实际上StringTable中的存储是一个个HashtableEntry对象组成的，其中entry的key说字符串的hash值，value则是字符串引用（一种Handle类型）。

所以到了这里基本上就解开了我的疑惑：到底字符串常量池到底说一个什么数据结构存储的？

它实际上就是一系列的k-v组合成的Entry，然后将其通过index将整个entry塞入到hashTable中去；而entry的k-v结构中，k实际上就是字符串的hash值，value就是字符串本身的引用。

image.png

这个图中，String对象内部有一个value属性，它是字符数组，它内部存储的就是真正的字符串内容。当然JDK9开始这个字符数组已经改造为byte数组了，这个和本次主题无关，暂时只考虑JDK8的情况。

Step 2

前面因为看到了字符串常量池的存储格式，所以自然而然就关注到了hashCode，所以对于hashCode又做了一番深入，前面的探索中，在basic_add方法中，可以看到在构造entry对象的时候，key传入的是hashValue，这里的hashValue实际上来自于hash_string这个方法：

if (use_alternate_hashcode()) {
  hashValue = hash_string(name, len);
  index = hash_to_index(hashValue);
} else {
  hashValue = hashValue_arg;
  index = index_arg;
}
......
HashtableEntry<oop, mtSymbol>* entry = new_entry(hashValue, string());
add_entry(index, entry);
return string();

这个hash_string在symbolTable.cpp本身这个文件内就有定义：

unsigned int StringTable::hash_string(const jchar* s, int len) {
  return use_alternate_hashcode() ? AltHashing::murmur3_32(seed(), s, len) :
                                    java_lang_String::hash_code(s, len);
}

这里murmur3_32这块暂时不做考虑，这是hotspot虚拟机这边提供的一种hashCode算法，主要关注的是后面这个：java_lang_String::hash_code(s, len);

这么调用说明hash_code是java_lang_String内的一个静态方法，那就全局搜“class java_lang_String”，可以在javaClasses.hpp文件中找到它的定义：

// Compute the hash value for a java.lang.String object which would
// contain the characters passed in.
//
// As the hash value used by the String object itself, in
// String.hashCode().  This value is normally calculated in Java code
// in the String.hashCode method(), but is precomputed for String
// objects in the shared archive file.
// hash P(31) from Kernighan & Ritchie
//
// For this reason, THIS ALGORITHM MUST MATCH String.hashCode().
template <typename T> static unsigned int hash_code(T* s, int len) {
  unsigned int h = 0;
  while (len-- > 0) {
    h = 31*h + (unsigned int) *s;
    s++;
  }
  return h;
}

这里附带了它的注释，注释里面说明的很清楚：

计算一个包含传入字符的 java.lang.String 对象的哈希值。

String对象本身使用的哈希值是在Java代码中的String.hashCode()方法中计算的，但对于String对象，这个值已经在共享存档文件中预先计算了，使用了 Kernighan & Ritchie 中的hash P(31) 算法。

因此，这个算法必须与String.hashCode()方法匹配。

说白了这里的调用方法实际上就是和JDK中String类中重写的hashCode方法算法是一样的：

s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]

这里的“s”就是字符串中的每个字符，n是字符串的长度。

2.2 Object.hashCode()

因为String的hashCode，让我想到了Object中的hashCode，也就是如果没有重写hashCode，默认会调用Object中的hashCode，它不像字符串那样有具体的类型，因此它的hashCode可能就需要基于对象本身做计算，长久以来，我一直以为hashCode的生成和对象的地址有关，但是我这次经过探究以后发现并不是那么简单：

首先看到JDK中Object类中有hashCode的native方法定义：

public native int hashCode();

所以按照前面同样的套路，到openJDK源码中找到java/lang/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},
};
......

需要到hotspot虚拟机中找到“JVM_IHashCode”对应的实现：

//jvm.cpp

// java.lang.Object ///////////////////////////////////////////////

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

//同样全局搜关键词“class ObjectSynchronizer”，找到synchronizer.hpp
static intptr_t FastHashCode (Thread * Self, oop obj) ;
//synchronizer.cpp下找到对应实现
intptr_t ObjectSynchronizer::FastHashCode (Thread * Self, oop obj) {
    ......
    // 这里不考虑各种加锁的情况，只考虑最普通一种情况
    if (mark->is_neutral()) {
      hash = mark->hash();              // this is a normal header
      if (hash) {                       // if it has hash, just return it
        return hash;
      }
      hash = get_next_hash(Self, obj);  // allocate a new hash code
      temp = mark->copy_set_hash(hash); // merge the hash code into header
      // use (machine word version) atomic operation to install the hash
      test = (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.
    }
    ......
}

核心点可以看到有一个：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的数值，从0到4外加一个else，这是给出了六种生成策略。

这六种策略分别对应不同的场景：

hashCode=0: os.random()，使用随机数
hashCode=1: 使用对象的地址进行计算
hashCode=2: 始终返回1，主要用于灵敏度测试
hashCode=3: 使用一种序列号进行生成
hashCode=4: 输出对象的内存地址
其他情况：利用xor-shift算法产生伪随机数

这里我写了一个demo程序进行测试：

Object obj1 = new Object();
Object obj2 = new Object();
System.out.println(obj1.hashCode());
System.out.println(obj2.hashCode());

默认情况下，不做任何配置可以得到：

759156157
1635546341

这里的hashCode值可以通过jvm运行参数进行调整，这里从hashCode=0开始进行测试：

运行前增加参数：

-XX:hashCode=0

发现报错了：

Error: VM option 'hashCode' is experimental and must be enabled via -XX:+UnlockExperimentalVMOptions.
Error: The unlock option must precede 'hashCode'.
Error: Could not create the Java Virtual Machine.
Error: A fatal exception has occurred. Program will exit

大概的意思就是说：hashCode还是属于测试性的，如果要使用的话，必须开启UnlockExperimentalVMOptions属性。

所以添加该属性：

-XX:+UnlockExperimentalVMOptions -XX:hashCode=0

得到结果：

// 第一次：
1298937153
829925568
// 第二次：
2065458716
1546335363
// 第三次：
1458888444
146433569

可以看到，每次运行的结果都不一样，符合随机数的特征。

换一种hashCode=1，根据对象的地址进行一定的计算得到的，因为每次运行对象在内存中的地址可能都不一样，所以每次运行结果可能都有不同：

-XX:+UnlockExperimentalVMOptions -XX:hashCode=1
// 第一次
668599630
668599628
//第二次
629723300
629723302
// 第三次
1645286083
1645286081

hashCode=2，灵敏度测试，每次应该都返回1:

-XX:+UnlockExperimentalVMOptions -XX:hashCode=2

// 第一次
1
1
//第二次
1
1
// 第三次
1
1

从结果上看，没有问题。

hashCode=3，使用的是一种序列号：

-XX:+UnlockExperimentalVMOptions -XX:hashCode=3

// 第一次
902
903
//第二次
899
900
// 第三次
899
902

hashCode=4: 输出对象的内存地址

-XX:+UnlockExperimentalVMOptions -XX:hashCode=4

// 第一次
260070984
260071000
//第二次
260070656
260070672
// 第三次
260070984
260071000

hashCode>4: 伪随机数，生成一种和线程状态相关的整数

-XX:+UnlockExperimentalVMOptions -XX:hashCode=5

// 第一次
759156157
1635546341
//第二次
759156157
1635546341
// 第三次
759156157
1635546341

这个结果对比前面默认情况下不加任何参数得到的结果来看，两者的结果是一样的，因此可以推论出：当前我的JDK8版本默认的hashCode值是大于4的，通过网上搜索的一些信息来说，JDK8默认设置hashCode=5，这个结果看来是不矛盾的。

关于这个hashCode的值，可以到hotspot目录下找到：“src/share/vm/runtime/globals.hpp”文件下，找到下面这段代码：

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

可以看到这里传入的是5，也就是说默认情况下，默认传入的hashCode是5，但是我同时了解到，JDK6和7的版本与JDK8默认的hashCode是不一样的，这里可以直接到openJDK官网上去找对应的源码就可以找到，目的地址一样hotspot/src/share/vm/runtime/globals.hpp：

JDK7：https://github.com/openjdk/jdk/tree/jdk7-b147

JDK6：https://github.com/openjdk/jdk6

//JDK7:
product(intx, hashCode, 0,                                                \
         "(Unstable) select hashCode generation algorithm" )

//JDK6
product(intx, hashCode, 0,                                                \
         "(Unstable) select hashCode generation algorithm" )

这里可以看到，对于JDK6和7，默认的hashCode生成走的是前面六种策略的第一种：os.random()。可以发现实际上默认的hashCode生成和对象地址压根儿没什么关系。

2.3 hashCode=5

对于JDK8以及以后版本默认使用的最后一种hashCode生成策略，源码：

// 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 ;

这里的Self类型是：Thread *。自然联想到查看一下是否有thread.cpp这类的文件，搜索后还真发现了在hotspot下面有这么一个文件，打开后没什么发现，顺带就打开了它的头文件thread.hpp，搜索_hashStateX后，有了如下的发现，这里选择了hotspot/src/share/vm/runtime/thread.hpp：

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

所以可以看到，这里的 Y、Z、W都是固定值，只有X上使用的随机值。因此上面的计算中，核心的那句计算方法实际上应该是：

random = os::random();
v = (273326509 ^ (273326509 >> 19)) ^ (random ^ (random >> 8));

这里的os::random调用，实际上是来自于：hotspot/src/share/vm/runtime/os.cpp内实现的random方法，下面的代码中对注释做了处理，中文部分的注释是手动添加的：

static long random();   // 它返回的是一个32bit的伪随机数

// 对应cpp文件中的实现源码：
long os::random() {
  /* 标准、众所周知的线性全等随机生成器
   * next_rand = (16807*seed) mod (2**31-1)
   * see（这里注释中放了两个参考资料，但是没有地址，经过搜索已经查到对应的论文地址，贴在下面）
   * (1) https://dl.acm.org/doi/10.1145/63039.63042,
   * (2) https://dl.acm.org/doi/10.1145/76372.76379, 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); //这里的_rand_seed是前面定义的1.
  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);
}

Ⅲ. 总结

首先就是字符串常量池的内部，实际上是一个hashTable结构，这个hashTable内部是以Entry的形式存储的，Entry中有key和value，其中的key是字符串的hash值，value是字符串对象的引用地址
String重写了hashCode方法，是通过一个计算公式计算出每个String对象的hashCode值的：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

对于Object中定义的hashCode方法，它是native方法，需要到对应的JDK源码中查看对应的实现
目前hotspot虚拟机中，hashCode的实现方案有六种：
- hashCode=0: os.random()，使用随机数
- hashCode=1: 使用对象的地址进行计算
- hashCode=2: 始终返回1，主要用于灵敏度测试
- hashCode=3: 使用一种序列号进行生成
- hashCode=4: 输出对象的内存地址
- 其他情况：利用xor-shift算法产生伪随机数

hashCode的值可以通过jvm的启动参数-XX:hashCode=?来进行设置，对于JDK8以及以后的版本，默认的hashCode值都是5，JDK6和7默认是0。