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

作者: still_loving | 来源:发表于2023-02-25 18:21 被阅读0次

JVM-常量池
java基础类型、String类理解、版本对比、1.8新特性
String为什么设计为不可变的？
深入浅出JVM常量池
彻底弄懂java中的常量池
由“String不可变”引发的一些思考
JVM（六）内存与圾回收|本地方法接口+字符串常量池
关于String和StringBuffer
JVM-常量池
字符串常量池

Ⅰ. 背景

在研究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。

JVM-常量池
JVM-常量池 JVM常量池分为 Class文件常量池运行时常量池全局字符串常量池基本类型包装类对象常量池 ...
java基础类型、String类理解、版本对比、1.8新特性
1、java基本数据类型及长度２、jvm的常量池： JVM常量池浅析Java常量池理解与总结 Java中的常量池...
String为什么设计为不可变的？
字符串常量池用作 HashMap 的 key 缓存 HashCode 线程安全
深入浅出JVM常量池
常量池在JVM中分为三种：字符串常量池，运行时常量池，Class常量池讨论范围 JDK 1.7版本及以后字符串常...
彻底弄懂java中的常量池
JVM有几种常量池主要分为： Class文件常量池、运行时常量池，全局字符串常量池，以及基本类型包装类对象常量池...
由“String不可变”引发的一些思考
字符串常量池 JVM为了字符串的服用，减少字符串对象的重复创建，特别维护了一个常量池。 jdk1....
JVM（六）内存与圾回收|本地方法接口+字符串常量池
本文介绍JVM的本地方法接口和字符串常量池。字符串常量池在前文内存与垃圾回收|运行时数据区（下）中也有提到...
关于String和StringBuffer
String 和 StringBuilder的区别 String类的学习（可以结合字符串常量池常量池运行时常量...
JVM-常量池
1，(全局)字符串常量池(String Constant Pool) 1）使用sun.jvm.hotspot.me...
字符串常量池
静态常量池，运行期常量池，字符串常量池静态常量池运行时常量池字符串常量池问题结果：验证new Stri...