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

Question

我正在学习 JVM 代码以更深入地了解 Java。在synchronizer.cpp（在该get_next_hash方法）有，说评论：

// Marsaglia 的具有线程特定状态的异或移位方案
// 这可能是最好的整体实现 -- 我们
可能会// 在未来的版本中将其设为默认值。

当变量hashcode不是 (0,1,2,3,4) 中的任何一个时，这会在 in else 分支中找到。这个变量可以通过 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。我的问题是：它比异或移位更好吗？为什么 jdk-8 将“-XX:hashcode=5”设为默认值？

Answer 1

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

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

  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在随机性方面也远非完美。它只是将对象的地址与仅在停止世界 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 ;

您可以在此电子邮件线程中找到对不同 hashCode 算法的讨论和分析。

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