Почему генерация hashCode по умолчанию в jvm была переключена на xor-shift в JDK 8?

Question

Я изучаю код JVM, чтобы глубже понять Java. В synchronizer.cpp (в метод get_next_hash ) есть комментарий, который гласит:

// Схема xor-shift Марсагии с резьбой- Speci c State
// Это, вероятно, лучшая общая реализация - мы
//, вероятно, сделаем это по умолчанию в будущих выпусках.

Это найдено в в ветви else, когда переменная hashcode не является ни одним из (0,1,2,3,4). эту переменную можно установить с помощью опции JVM "-XX: hashcode = n".

Я написал некоторый код для проверки этих алгоритмов ha sh:

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

Свойства хорошей функции ha sh включают 1) случайность, 2) однородность, 3) производительность, 4) масштабируемость. Небольшое количество коллизий не означает, что функция ha sh является достаточно случайной, например, в вашем тесте последовательные хеш-коды также не дают коллизий, но, очевидно, это не очень хорошая функция ha sh.

Также, Вы проверили только один случай потока. С одним потоком -XX:hashCode=0 (алгоритм Park-Miller RNG, который был по умолчанию до JDK 8) ведет себя довольно хорошо. Однако в приложениях с высокой степенью одновременности это становится ужасным: производительность снижается из-за высокой конкуренции за глобальную переменную, а вероятность генерирования одного и того же хэш-кода в разных потоках возрастает из-за состояния гонки, см. комментарий в исходном коде:

  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 также далеко не идеален с точки зрения случайности. Он просто XOR адрес объекта с глобальной переменной, обновляемой только в паузах 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 в this поток электронной почты .

Короче говоря, только -XX:hashCode=0 и -XX:hashCode=5 обеспечивают хорошую случайность, в то время как последняя гораздо более масштабируема и производительна, так как использует только простые побитовые операции и не обновляет глобальные переменные.