为什么在 JDK 8 中 jvm 中的默认 hashCode 生成切换为 xor-shift？

Question

我正在学习 JVM 代码以更深入地理解 Java。在 synchronizer.cpp (in the get_next_hash method) 中有一条评论说：

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

当变量hashcode不是(0,1,2,3,4)中的任何一个时，在else b运行ch中找到。这个变量可以通过 JVM 选项“-XX:hashcode=n”设置。

我写了一些代码来测试那些哈希算法：

public static void main(String[] args) {
    long now = System.currentTimeMillis();
    RuntimeMXBean runtimeMxBean = ManagementFactory.getRuntimeMXBean();
    List<String> arguments = runtimeMxBean.getInputArguments();
    for(String s:arguments){
        System.out.println(s);
    }

    HashMap<Integer,Object> h = new HashMap<>();

    ArrayList<Object> arrayList = new ArrayList<>();

    for(int i=0;i<2000000;i++){
        Object o = new Object();
        if(h.containsKey(o.hashCode())){
            arrayList.add(o);
            continue;
        }
        h.put(o.hashCode(),o);
    }
    long currentTimeMillis = System.currentTimeMillis();
    System.err.println("hashcode collision："+arrayList.size());
    System.err.println(" used time "+(currentTimeMillis - now));

}

在我运行测试之前，我预计当我设置“-XX:hashcode=5”时我会得到最少的冲突，但事实并非如此:

| n | algorithm      |collisions|
|---|----------------|----------|
| 0 | rondom         |        0 |
| 1 | addr-XOR-SHIFT |        0 |
| 2 | invarible-one  |  1999999 |
| 3 | autoincrease   |        0 |
| 4 | addr           |    23511 |
| 5 | xor-shift      |      962 |

然后我将时间设置为 20000000，addr-XOR-SHIFT 仍然是 0。我的问题是：它比 xor-shift 好吗？为什么 jdk-8 使“-XX:hashcode=5”成为默认值？

Answer 1

好的散列函数的属性包括 1) 随机性，2) 均匀性，3) 性能，4) 可扩展性。少量的冲突并不意味着散列函数足够随机，例如在您的测试中，顺序哈希代码也不会产生冲突，但显然这不是一个好的哈希函数。

此外，您只测试了单线程情况。对于单个线程，-XX:hashCode=0（JDK 8 之前默认的 Park-Miller RNG 算法）表现得很好。然而，它在高并发应用程序中变得很糟糕：由于对全局变量的高度争用导致性能变差，并且由于竞争条件，在不同线程中生成相同 hashCode 的机会增加，请参见 the comment源代码：

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

-XX:hashCode=1在随机性方面也远非完美。它只是将 on 对象的地址与仅在 stop-the-world JVM 暂停时更新的全局变量进行异或运算：

  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 ;

您可以在this email thread.

中找到对不同hashCode算法的讨论和分析

简而言之，只有 -XX:hashCode=0 和 -XX:hashCode=5 提供了良好的随机性，而后者的可扩展性和性能要好得多，因为它仅使用简单的按位运算并且不更新全局变量。

为什么在 JDK 8 中 jvm 中的默认 hashCode 生成切换为 xor-shift？

Why was the default hashCode generation in jvm switched to xor-shift in JDK 8?

java

jvm