如何用JAVA源碼解析hashcode方法

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)如何用JAVA源碼解析hashcode方法，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

在開發(fā)過程中我們可能會(huì)經(jīng)常接觸到hashcode這個(gè)方法來生成哈希碼，那么底層是如何實(shí)現(xiàn)的？使用時(shí)有何注意點(diǎn)呢？

hashcode() 方法底層實(shí)現(xiàn)

hashcode()是Object的方法：

@HotSpotIntrinsicCandidate
public native int hashCode();

它是一個(gè)native的方法，并且被@HotSpotIntrinsicCandidate注解修飾，證明它是一個(gè)在HotSpot中有一套高效的實(shí)現(xiàn)，該高效實(shí)現(xiàn)基于CPU指令。

具體的實(shí)現(xiàn)參考源碼synchronizer.cpp：

static inline intptr_t get_next_hash(Thread* self, oop obj) {
  intptr_t value = 0;
  if (hashCode == 0) {
    value = os::random();
  } else if (hashCode == 1) {
    intptr_t addr_bits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
  } else if (hashCode == 2) {
    value = 1;           
  } else if (hashCode == 3) {
    value = ++GVars.hc_sequence;
  } else if (hashCode == 4) {
    value = cast_from_oop<intptr_t>(obj);
  } else {
    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 &= markWord::hash_mask;
  if (value == 0) value = 0xBAD;
  assert(value != markWord::no_hash, "invariant");
  return value;
}

可以看出，根據(jù)hashcode這個(gè)全局變量的取值，決定用何種策略生成哈希值，查看globals.hpp來看是哪一種變量：

 experimental(intx, hashCode, 5, "(Unstable) select hashCode generation algorithm")

發(fā)現(xiàn)是一個(gè)experimental的 JVM 變量，這樣的話，想要修改，必須添加額外的參數(shù)，如下所示：

-XX:+UnlockExperimentalVMOptions -XX:hashCode=2

并且，這個(gè)hashCode默認(rèn)為5。

哈希值是每次hashcode()方法調(diào)用重計(jì)算么？

對(duì)于沒有覆蓋hashcode()方法的類，實(shí)例每次調(diào)用hashcode()方法，只有第一次計(jì)算哈希值，之后哈希值會(huì)存儲(chǔ)在對(duì)象頭的 標(biāo)記字（MarkWord） 中。

如果進(jìn)入各種鎖狀態(tài)，那么會(huì)緩存在其他地方，一般是獲取鎖的線程里面存儲(chǔ)，恢復(fù)無鎖（即釋放鎖）會(huì)改回原有的哈希值。

關(guān)于對(duì)象頭結(jié)構(gòu)，以及對(duì)象存儲(chǔ)結(jié)構(gòu)，感興趣的話，可以參考：Java GC詳解 - 1. 理解Java對(duì)象結(jié)構(gòu)

-XX:hashCode=0 利用 Park-Miller 偽隨機(jī)數(shù)生成器生成哈希值

if (hashCode == 0) {
    value = os::random();
}

調(diào)用 os 的 random 方法生成隨機(jī)數(shù)。這個(gè)方法的實(shí)現(xiàn)方式是: os.cpp：

//初始seed，默認(rèn)是1
volatile unsigned int os::_rand_seed = 1;

static int random_helper(unsigned int rand_seed) {
  /* standard, well-known linear congruential random generator with
   * next_rand = (16807*seed) mod (2**31-1)
   * see
   * (1) "Random Number Generators: Good Ones Are Hard to Find",
   *      S.K. Park and K.W. Miller, Communications of the ACM 31:10 (Oct 1988),
   * (2) "Two Fast Implementations of the 'Minimal Standard' Random
   *     Number Generator", David G. Carta, Comm. ACM 33, 1 (Jan 1990), pp. 87-88.
  */
  const unsigned int a = 16807;
  const unsigned int m = 2147483647;
  const int q = m / a;        assert(q == 127773, "weird math");
  const int r = m % a;        assert(r == 2836, "weird math");

  // compute az=2^31p+q
  unsigned int lo = a * (rand_seed & 0xFFFF);
  unsigned int hi = a * (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 lo;
}

int os::random() {
  // Make updating the random seed thread safe.
  while (true) {
    unsigned int seed = _rand_seed;
    unsigned int rand = random_helper(seed);
    //CAS更新
    if (Atomic::cmpxchg(&_rand_seed, seed, rand) == seed) {
      return static_cast<int>(rand);
    }
  }
}

其中，random_helper 就是隨機(jī)數(shù)的生成公式的實(shí)現(xiàn)，公式是： 這里，a=16807, c=0, m=2^31-1

由于這些隨機(jī)數(shù)都是采用的同一個(gè)生成器，會(huì) CAS 更新同一個(gè) seed，如果有大量的生成的新對(duì)象并且都調(diào)用hashcode()方法的話，可能會(huì)有性能問題。重復(fù)調(diào)用同一個(gè)對(duì)象的hashcode()方法不會(huì)有問題，因?yàn)橹疤岬搅耸怯芯彺娴摹?/p>

-XX:hashCode=1或者4 基于對(duì)象指針 OOPs

OOPs（Ordinary Object Pointers）對(duì)象指針是對(duì)象頭的一部分。關(guān)于對(duì)象頭結(jié)構(gòu)，以及對(duì)象存儲(chǔ)結(jié)構(gòu)，感興趣的話，可以參考：Java GC詳解 - 1. 理解Java對(duì)象結(jié)構(gòu)?？梢院?jiǎn)單理解為對(duì)象在內(nèi)存中的地址的描述。

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 addr_bits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
}
else if (hashCode == 4) {
    value = cast_from_oop<intptr_t>(obj);
}

cast_from_oop很簡(jiǎn)單，就是獲取oop的實(shí)現(xiàn)基類oopDesc的指向地址(oopDesc描述了OOP的基本組成，感興趣可以參考：Java GC詳解 - 1. 理解Java對(duì)象結(jié)構(gòu))：

template <class T> inline T cast_from_oop(oop o) {
  return (T)(CHECK_UNHANDLED_OOPS_ONLY((oopDesc*))o);
}

當(dāng)-XX:hashCode=4，直接用oop的地址作為哈希值。-XX:hashCode=1則是經(jīng)過變換的，每次發(fā)生 Stop The World （STW）stw_random會(huì)發(fā)生改變，通過這個(gè)addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random變換減少哈希碰撞，讓哈希值更散列化。

想更深入了解 Stop the world，可以參考：JVM相關(guān) - SafePoint 與 Stop The World 全解(基于OpenJDK 11版本)

-XX:hashCode=2 敏感測(cè)試，恒定為1

else if (hashCode == 2) {
    value = 1;            // for sensitivity testing
}

主要用于測(cè)試某些集合是否對(duì)于哈希值敏感。

-XX:hashCode=3 自增序列

else if (hashCode == 3) {
    value = ++GVars.hc_sequence;
}

struct SharedGlobals {
  // omitted
  DEFINE_PAD_MINUS_SIZE(1, DEFAULT_CACHE_LINE_SIZE, sizeof(volatile int) * 2);
  // Hot RW variable -- Sequester to avoid false-sharing
  volatile int hc_sequence;
  DEFINE_PAD_MINUS_SIZE(2, DEFAULT_CACHE_LINE_SIZE, sizeof(volatile int));
};
static SharedGlobals GVars;

每創(chuàng)建一個(gè)新對(duì)象，調(diào)用哈希值，這個(gè)自增數(shù)+1，可以看出，散列性極差，很容易哈希碰撞。

-XX:hashCode=5 默認(rèn)實(shí)現(xiàn)

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

采用的算法是 Marsaglia's xor-shift 隨機(jī)數(shù)生成法。主要是這篇論文提出的一種快速并且散列性好的哈希算法。

特殊的哈希值導(dǎo)致某些場(chǎng)景的問題

我們經(jīng)常使用某個(gè)對(duì)象或者某個(gè)字段的哈希值，通過對(duì)于某個(gè)數(shù)組長(zhǎng)度取模，獲取到下標(biāo)，取出數(shù)組對(duì)應(yīng)下標(biāo)的對(duì)象，進(jìn)行進(jìn)一步處理。這在負(fù)載均衡，任務(wù)調(diào)度，線程分配很常見。那下面這段代碼是否有問題呢？

//獲取userId這個(gè)字符串的哈希值的絕對(duì)值
int index = Math.abs(userId.hashCode());
//返回哈希值取模之后的下標(biāo)的對(duì)象
return userAvatarList.get(index % userAvatarList.size()).getUrl();

通常大多數(shù)情況下，是沒有問題的，但是假設(shè)userId是這幾個(gè)哈希值為Integer.MIN_VALUE的字符串：

System.out.println("polygenelubricants".hashCode());
System.out.println("GydZG_".hashCode());
System.out.println("DESIGNING WORKHOUSES".hashCode());

輸出：

-2147483648
-2147483648
-2147483648

對(duì)于這些值，如果你用Math.abs()取絕對(duì)值的話，我們知道Math.abs(Integer.MIN_VALUE)還是等于Integer.MIN_VALUE，這是因?yàn)榈讓訉?shí)現(xiàn)：

public static int abs(int a) {
    return (a < 0) ? -a : a;
}

-Integer.MIN_VALUE和Integer.MIN_VALUE是相等的。Integer.MIN_VALUE取模還是負(fù)數(shù)，這樣取下標(biāo)對(duì)應(yīng)的對(duì)象的時(shí)候，就會(huì)報(bào)異常。

所以，需要修改為：

int index = Math.abs(userId.hashCode() % userAvatarList.size());
return userAvatarList.get(index).getUrl();

上述就是小編為大家分享的如何用JAVA源碼解析hashcode方法了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。