Ⅰ. 背景

• 在研究String不可變特性的時(shí)候， 因?yàn)楸容^好奇有關(guān)常量池的相關(guān)概念，就深入了一下到JVM源碼進(jìn)行了探究

• 在研究常量池的過程中，不可避免的又涉及到了Java中hashCode的相關(guān)概念，所以就順帶看了下JVM中關(guān)于hashCode的本地方法實(shí)現(xiàn)

• 本篇主要是記錄一下整個(gè)探查的過程，算是給自己一個(gè)記錄，方便后續(xù)查閱。

Ⅱ. 介紹

2.1 字符串常量池

Step 1

• 提到字符串常量池，我比較好奇它底層的存儲(chǔ)數(shù)據(jù)格式到底是怎么樣的？因此就需要深入去探查一下。因?yàn)槭亲址Ａ砍?，所以就自然想到了String的一個(gè)方法 intern()，它的作用就是將字符串對(duì)象放入到字符常量池中，該方法是一個(gè)native方法，因此去找了下openJDK源碼，這里用到的是github上openjdk的jdk8-b120 的tag版本。

• String類的全部包名：java.lang.String，所以可以去找open JDK源碼中share/native目錄下按照包名往下找。

• 下載并打開該項(xiàng)目后，可以在jdk目錄下：

image.png

native目錄下一般存放的都是JDK中一些本地方法的對(duì)應(yīng)C語言調(diào)用，這里要看的是String類下的intern方法，因此找到j(luò)ava/lang/String.c文件：

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

這里僅僅只是一個(gè)調(diào)用，具體的實(shí)現(xiàn)還得到具體的JVM實(shí)現(xiàn)廠商的源代碼中去尋找，最常見的肯定就是hotspot虛擬機(jī)，這里可以到hotspot目錄下去搜索相關(guān)實(shí)現(xiàn)。

這里全局搜一下JVM_InternString這個(gè)內(nèi)容，可以發(fā)現(xiàn)在hotspot的src/share/vm/prims/jvm.cpp中出現(xiàn)了：

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

可以發(fā)現(xiàn)有一個(gè)StringTable調(diào)用了intern方法，那么就可以在項(xiàng)目中全局搜一下 class StringTable這個(gè)關(guān)鍵詞，就可以看到有一個(gè)symbolTable.hpp文件里面出現(xiàn)了這個(gè)定義：

class StringTable : public Hashtable<oop, mtSymbol> {
    ......
    static oop intern(oop string, TRAPS);//這個(gè)方法的簽名和上面的調(diào)用是一致的
    ......
}

這里可以看到，StringTable其實(shí)就是一個(gè)hashTable，內(nèi)部有一個(gè)intern的靜態(tài)方法，所以可以到對(duì)應(yīng)的cpp文件里面找到具體的實(shí)現(xiàn)，下面貼出了部分源碼，從上到下是按照一個(gè)方法的調(diào)用鏈貼出來的：

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); // 這里調(diào)用了當(dāng)前文件內(nèi)另外一個(gè)intern方法
  return result;
}

oop StringTable::intern(Handle string_or_null, jchar* name,
                        int len, TRAPS) {
    ......
    // 這里的the_table返回的就是當(dāng)前的StringTable，所以它是調(diào)用了StringTable內(nèi)部的那個(gè)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();                           
}

這里可以看到，實(shí)際上StringTable中的存儲(chǔ)是一個(gè)個(gè)HashtableEntry對(duì)象組成的，其中entry的key說字符串的hash值，value則是字符串引用（一種Handle類型）。

所以到了這里基本上就解開了我的疑惑：到底字符串常量池到底說一個(gè)什么數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的？

它實(shí)際上就是一系列的k-v組合成的Entry，然后將其通過index將整個(gè)entry塞入到hashTable中去；而entry的k-v結(jié)構(gòu)中，k實(shí)際上就是字符串的hash值，value就是字符串本身的引用。

image.png

這個(gè)圖中，String對(duì)象內(nèi)部有一個(gè)value屬性，它是字符數(shù)組，它內(nèi)部存儲(chǔ)的就是真正的字符串內(nèi)容。當(dāng)然JDK9開始這個(gè)字符數(shù)組已經(jīng)改造為byte數(shù)組了，這個(gè)和本次主題無關(guān)，暫時(shí)只考慮JDK8的情況。

Step 2

• 前面因?yàn)榭吹搅俗址Ａ砍氐拇鎯?chǔ)格式，所以自然而然就關(guān)注到了hashCode，所以對(duì)于hashCode又做了一番深入，前面的探索中，在basic_add方法中，可以看到在構(gòu)造entry對(duì)象的時(shí)候，key傳入的是hashValue，這里的hashValue實(shí)際上來自于hash_string這個(gè)方法：

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();

• 這個(gè)hash_string在symbolTable.cpp本身這個(gè)文件內(nèi)就有定義：

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這塊暫時(shí)不做考慮，這是hotspot虛擬機(jī)這邊提供的一種hashCode算法，主要關(guān)注的是后面這個(gè)：java_lang_String::hash_code(s, len);

這么調(diào)用說明hash_code是java_lang_String內(nèi)的一個(gè)靜態(tài)方法，那就全局搜“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;
}

這里附帶了它的注釋，注釋里面說明的很清楚：

計(jì)算一個(gè)包含傳入字符的 java.lang.String 對(duì)象的哈希值。

String對(duì)象本身使用的哈希值是在Java代碼中的String.hashCode()方法中計(jì)算的，但對(duì)于String對(duì)象，這個(gè)值已經(jīng)在共享存檔文件中預(yù)先計(jì)算了，使用了 Kernighan & Ritchie 中的hash P(31) 算法。

因此，這個(gè)算法必須與String.hashCode()方法匹配。

說白了這里的調(diào)用方法實(shí)際上就是和JDK中String類中重寫的hashCode方法算法是一樣的：

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

這里的“s”就是字符串中的每個(gè)字符，n是字符串的長度。

2.2 Object.hashCode()

因?yàn)镾tring的hashCode，讓我想到了Object中的hashCode，也就是如果沒有重寫hashCode，默認(rèn)會(huì)調(diào)用Object中的hashCode，它不像字符串那樣有具體的類型，因此它的hashCode可能就需要基于對(duì)象本身做計(jì)算，長久以來，我一直以為hashCode的生成和對(duì)象的地址有關(guān)，但是我這次經(jīng)過探究以后發(fā)現(xiàn)并不是那么簡單：

首先看到JDK中Object類中有hashCode的native方法定義：

public native int hashCode();

所以按照前面同樣的套路，到openJDK源碼中找到j(luò)ava/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虛擬機(jī)中找到“JVM_IHashCode”對(duì)應(yīng)的實(shí)現(xiàn)：

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

//同樣全局搜關(guān)鍵詞“class ObjectSynchronizer”，找到synchronizer.hpp
static intptr_t FastHashCode (Thread * Self, oop obj) ;
//synchronizer.cpp下找到對(duì)應(yīng)實(shí)現(xiàn)
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.
    }
    ......
}

核心點(diǎn)可以看到有一個(gè)：get_next_hash方法的調(diào)用，這里傳入的參數(shù)是線程對(duì)象本身以及待計(jì)算hash的對(duì)象：

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

這里就需要好好說一下了，先忽略掉所有細(xì)節(jié)，可以看到主要有六個(gè)分支，根據(jù)hashCode的數(shù)值，從0到4外加一個(gè)else，這是給出了六種生成策略。

這六種策略分別對(duì)應(yīng)不同的場景：

1. hashCode=0: os.random()，使用隨機(jī)數(shù)

2. hashCode=1: 使用對(duì)象的地址進(jìn)行計(jì)算

3. hashCode=2: 始終返回1，主要用于靈敏度測試

4. hashCode=3: 使用一種序列號(hào)進(jìn)行生成

5. hashCode=4: 輸出對(duì)象的內(nèi)存地址

6. 其他情況：利用xor-shift算法產(chǎn)生偽隨機(jī)數(shù)

這里我寫了一個(gè)demo程序進(jìn)行測試：

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

默認(rèn)情況下，不做任何配置可以得到：

759156157
1635546341

這里的hashCode值可以通過jvm運(yùn)行參數(shù)進(jìn)行調(diào)整，這里從hashCode=0開始進(jìn)行測試：

運(yùn)行前增加參數(shù)：

-XX:hashCode=0

發(fā)現(xiàn)報(bào)錯(cuò)了：

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

得到結(jié)果：

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

可以看到，每次運(yùn)行的結(jié)果都不一樣，符合隨機(jī)數(shù)的特征。

換一種hashCode=1，根據(jù)對(duì)象的地址進(jìn)行一定的計(jì)算得到的，因?yàn)槊看芜\(yùn)行對(duì)象在內(nèi)存中的地址可能都不一樣，所以每次運(yùn)行結(jié)果可能都有不同：

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

hashCode=2，靈敏度測試，每次應(yīng)該都返回1:

-XX:+UnlockExperimentalVMOptions -XX:hashCode=2

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

從結(jié)果上看，沒有問題。

hashCode=3，使用的是一種序列號(hào)：

-XX:+UnlockExperimentalVMOptions -XX:hashCode=3

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

hashCode=4: 輸出對(duì)象的內(nèi)存地址

-XX:+UnlockExperimentalVMOptions -XX:hashCode=4

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

hashCode>4: 偽隨機(jī)數(shù)，生成一種和線程狀態(tài)相關(guān)的整數(shù)

-XX:+UnlockExperimentalVMOptions -XX:hashCode=5

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

這個(gè)結(jié)果對(duì)比前面默認(rèn)情況下不加任何參數(shù)得到的結(jié)果來看，兩者的結(jié)果是一樣的，因此可以推論出：當(dāng)前我的JDK8版本默認(rèn)的hashCode值是大于4的，通過網(wǎng)上搜索的一些信息來說，JDK8默認(rèn)設(shè)置hashCode=5，這個(gè)結(jié)果看來是不矛盾的。

關(guān)于這個(gè)hashCode的值，可以到hotspot目錄下找到：“src/share/vm/runtime/globals.hpp”文件下，找到下面這段代碼：

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

可以看到這里傳入的是5，也就是說默認(rèn)情況下，默認(rèn)傳入的hashCode是5，但是我同時(shí)了解到，JDK6和7的版本與JDK8默認(rèn)的hashCode是不一樣的，這里可以直接到openJDK官網(wǎng)上去找對(duì)應(yīng)的源碼就可以找到，目的地址一樣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" ) 

這里可以看到，對(duì)于JDK6和7，默認(rèn)的hashCode生成走的是前面六種策略的第一種：os.random()?？梢园l(fā)現(xiàn)實(shí)際上默認(rèn)的hashCode生成和對(duì)象地址壓根兒沒什么關(guān)系。

2.3 hashCode=5

對(duì)于JDK8以及以后版本默認(rèn)使用的最后一種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 *。自然聯(lián)想到查看一下是否有thread.cpp這類的文件，搜索后還真發(fā)現(xiàn)了在hotspot下面有這么一個(gè)文件，打開后沒什么發(fā)現(xiàn)，順帶就打開了它的頭文件thread.hpp，搜索_hashStateX后，有了如下的發(fā)現(xiàn)，這里選擇了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上使用的隨機(jī)值。因此上面的計(jì)算中，核心的那句計(jì)算方法實(shí)際上應(yīng)該是：

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

這里的os::random調(diào)用，實(shí)際上是來自于：hotspot/src/share/vm/runtime/os.cpp內(nèi)實(shí)現(xiàn)的random方法，下面的代碼中對(duì)注釋做了處理，中文部分的注釋是手動(dòng)添加的：

static long random();   // 它返回的是一個(gè)32bit的偽隨機(jī)數(shù)

// 對(duì)應(yīng)cpp文件中的實(shí)現(xiàn)源碼：
long os::random() {
  /* 標(biāo)準(zhǔn)、眾所周知的線性全等隨機(jī)生成器
   * next_rand = (16807*seed) mod (2**31-1)
   * see（這里注釋中放了兩個(gè)參考資料，但是沒有地址，經(jīng)過搜索已經(jīng)查到對(duì)應(yīng)的論文地址，貼在下面）
   * (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);
}

Ⅲ. 總結(jié)

• 首先就是字符串常量池的內(nèi)部，實(shí)際上是一個(gè)hashTable結(jié)構(gòu)，這個(gè)hashTable內(nèi)部是以Entry的形式存儲(chǔ)的，Entry中有key和value，其中的key是字符串的hash值，value是字符串對(duì)象的引用地址

• String重寫了hashCode方法，是通過一個(gè)計(jì)算公式計(jì)算出每個(gè)String對(duì)象的hashCode值的：

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

• 對(duì)于Object中定義的hashCode方法，它是native方法，需要到對(duì)應(yīng)的JDK源碼中查看對(duì)應(yīng)的實(shí)現(xiàn)

• 目前hotspot虛擬機(jī)中，hashCode的實(shí)現(xiàn)方案有六種：

  • hashCode=0: os.random()，使用隨機(jī)數(shù)

  • hashCode=1: 使用對(duì)象的地址進(jìn)行計(jì)算

  • hashCode=2: 始終返回1，主要用于靈敏度測試

  • hashCode=3: 使用一種序列號(hào)進(jìn)行生成

  • hashCode=4: 輸出對(duì)象的內(nèi)存地址

  • 其他情況：利用xor-shift算法產(chǎn)生偽隨機(jī)數(shù)

• hashCode的值可以通過jvm的啟動(dòng)參數(shù)-XX:hashCode=?來進(jìn)行設(shè)置，對(duì)于JDK8以及以后的版本，默認(rèn)的hashCode值都是5，JDK6和7默認(rèn)是0。