JDK核心JAVA源码解析(9) - hashcode 方法

忘是亡心i 2022-12-07 15:22 238阅读 0赞

> 本文基于 OpenJDK 11， HotSpot 虚拟机

在开发过程中我们可能会经常接触到`hashcode`这个方法来生成哈希码，那么底层是如何实现的？使用时有何注意点呢？

# hashcode() 方法底层实现 #

`hashcode()`是`Object`的方法：

@HotSpotIntrinsicCandidate
    public native int hashCode();

它是一个`native`的方法，并且被`@HotSpotIntrinsicCandidate`注解修饰，证明它是一个在HotSpot中有一套高效的实现，该高效实现基于CPU指令。

具体的实现参考源码[`synchronizer.cpp`][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;
    }

可以看出，根据`hashcode`这个全局变量的取值，决定用何种策略生成哈希值，查看[`globals.hpp`][globals.hpp]来看是哪一种变量：

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

发现是一个`experimental`的 JVM 变量，这样的话，想要修改，必须添加额外的参数，如下所示：

-XX:+UnlockExperimentalVMOptions -XX:hashCode=2

并且，这个`hashCode`默认为5。

# 哈希值是每次hashcode()方法调用重计算么？ #

**对于没有覆盖`hashcode()`方法的类**，实例每次调用`hashcode()`方法，只有**第一次**计算哈希值，之后哈希值会存储在对象头的 **标记字（MarkWord）** 中。

![image][]  
（上图来自于：https://www.cnblogs.com/helloworldcode/p/11914053.html）

如果进入**各种锁**状态，那么会缓存在其他地方，一般是**获取锁的线程里面存储**，恢复无锁（即释放锁）会**改回原有的哈希值**。

关于对象头结构，以及对象存储结构，感兴趣的话，可以参考：[Java GC详解 - 1. 理解Java对象结构][Java GC_ - 1. _Java]

# \-XX:hashCode=0 利用 Park-Miller 伪随机数生成器生成哈希值 #

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

调用 os 的 random 方法生成随机数。这个方法的实现方式是:  
[os.cpp][]：

//初始seed，默认是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 就是随机数的生成公式的实现，公式是：  
![image][image 1]  
这里，a=16807, c=0, m=2^31-1

由于这些随机数都是采用的同一个生成器，会 CAS 更新同一个 seed，如果有大量的生成的新对象并且都调用`hashcode()`方法的话，可能会有性能问题。重复调用同一个对象的`hashcode()`方法不会有问题，因为之前提到了是有缓存的。

# \-XX:hashCode=1或者4 基于对象指针 OOPs #

OOPs（Ordinary Object Pointers）对象指针是对象头的一部分。关于对象头结构，以及对象存储结构，感兴趣的话，可以参考：[Java GC详解 - 1. 理解Java对象结构][Java GC_ - 1. _Java]。可以简单理解为对象在内存中的地址的描述。

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`很简单，就是获取`oop`的实现基类`oopDesc`的指向地址(`oopDesc`描述了OOP的基本组成，感兴趣可以参考：[Java GC详解 - 1. 理解Java对象结构][Java GC_ - 1. _Java])：

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

当`-XX:hashCode=4`，直接用`oop`的地址作为哈希值。`-XX:hashCode=1`则是经过变换的，每次发生 Stop The World （STW）stw\_random会发生改变，通过这个`addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random`变换减少哈希碰撞，让哈希值更散列化。

想更深入了解 Stop the world，可以参考：[JVM相关 - SafePoint 与 Stop The World 全解(基于OpenJDK 11版本)][JVM_ - SafePoint _ Stop The World _OpenJDK 11]

# \-XX:hashCode=2 敏感测试，恒定为1 #

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

主要用于测试某些集合是否对于哈希值敏感。

# \-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;

每创建一个新对象，调用哈希值，这个自增数+1，可以看出，散列性极差，很容易哈希碰撞。

# \-XX:hashCode=5 默认实现 #

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 随机数生成法。主要是[这篇论文][Link 1]提出的一种快速并且散列性好的哈希算法。

# 特殊的哈希值导致某些场景的问题 #

我们经常使用某个对象或者某个字段的哈希值，通过对于某个数组长度取模，获取到下标，取出数组对应下标的对象，进行进一步处理。这在负载均衡，任务调度，线程分配很常见。那下面这段代码是否有问题呢？

//获取userId这个字符串的哈希值的绝对值
    int index = Math.abs(userId.hashCode());
    //返回哈希值取模之后的下标的对象
    return userAvatarList.get(index % userAvatarList.size()).getUrl();

通常大多数情况下，是没有问题的，但是假设`userId`是这几个哈希值为`Integer.MIN_VALUE`的字符串：

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

输出：

-2147483648
    -2147483648
    -2147483648

对于这些值，如果你用`Math.abs()`取绝对值的话，我们知道`Math.abs(Integer.MIN_VALUE)`还是等于`Integer.MIN_VALUE`，这是因为底层实现：

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

`-Integer.MIN_VALUE`和`Integer.MIN_VALUE`是相等的。`Integer.MIN_VALUE`取模还是负数，这样取下标对应的对象的时候，**就会报异常**。

所以，需要修改为：

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

[synchronizer.cpp]: https://github.com/openjdk/jdk/blob/master/src/hotspot/share/runtime/synchronizer.cpp
[globals.hpp]: https://github.com/openjdk/jdk/blob/master/src/hotspot/share/runtime/globals.hpp
[image]: /images/20221123/26ddb395073d418887b9031021136594.png
[Java GC_ - 1. _Java]: https://zhanghaoxin.blog.csdn.net/article/details/108627011
[os.cpp]: https://github.com/openjdk/jdk/blob/master/src/hotspot/share/runtime/os.cpp
[image 1]: /images/20221123/7b7ed77fd72b490fb714805e46c1d9e5.png
[JVM_ - SafePoint _ Stop The World _OpenJDK 11]: https://zhanghaoxin.blog.csdn.net/article/details/107450858
[Link 1]: https://www.jstatsoft.org/article/view/v008i14