Подтвердить что ты не робот

Использование Java 7 HashMap в Java 8

Я обновил приложение Java на Java 8. Приложение сильно зависит от HashMaps. Когда я запускаю тесты, я вижу непредсказуемое поведение. Для некоторых входов приложение работает быстрее, чем раньше, но для больших входов оно работает медленнее.

Я проверил профилировщик, и самая трудоемкая операция - HashMap.get. Я подозреваю изменения вызваны модификацией HashMap в Java 8, но это может быть неверно, поскольку я изменил некоторые другие части.

Есть ли простой способ, с помощью которого я подключаюсь к исходному Java 7 HashMap в моем приложении Java 8, чтобы я только изменил реализацию hashmap, чтобы убедиться, что я все еще наблюдаю за изменением производительности.

Ниже приведена минимальная программа, которая пытается имитировать то, что делает мое приложение. Основная идея заключается в том, что мне нужно обмениваться узлами в приложении. В некоторой точке выполнения, node должен быть получен или создан, если он уже не существует на основе каких-либо целочисленных свойств. В следующем примере используется только одно целое число, но в реальном приложении у меня есть один, два и три целых ключа.

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Test1 {

static int max_k1 = 500;
static int max_k2 = 500;

static Map<Node, Node> map;
static Random random = new Random();

public static void main(String[] args) {
    for (int i = 0; i < 15; i++) {
        long start = System.nanoTime();
        run();
        long end = System.nanoTime();
        System.out.println((end - start) / 1000_000);
    }
}

private static void run() {
    map = new HashMap<>();
    for (int i = 0; i < 10_000_000; i++) {
        Node key = new Node(random.nextInt(max_k1), random.nextInt(max_k2));
        Node val = getOrElseUpdate(key);
    }
}

private static Node getOrElseUpdate(Node key) {
    Node val;
    if ((val = map.get(key)) == null) {
        val = key;
        map.put(key, val);
    }
    return val;
}

private static class Node {

    private int k1;
    private int k2;

    public Node(int k1, int k2) {
        this.k1 = k1;
        this.k2 = k2;
    }

    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + k1;
        result = 31 * result + k2;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;

        if (!(obj instanceof Node))
            return false;

        Node other = (Node) obj;

        return k1 == other.k1 && k2 == other.k2;
    }
  }
}

Сравнительный анализ является примитивным, но все же это результат 15 запусков на Java 8:

8143
7919
7984
7973
7948
7984
7931
7992
8038
7975
7924
7995
6903
7758
7627

и это для Java 7:

7247
6955
6510
6514
6577
6489
6510
6570
6497
6482
6540
6462
6514
4603
6270

Сравнительный анализ является примитивным, поэтому я ценю, что кто-то, кто знаком с JMH или другими инструментами бенчмаркинга, запускает его, но из того, что я вижу, результаты лучше для Java 7. Любые идеи?

4b9b3361

Ответ 1

Ваш hashCode() очень плохой. В приведенном примере у вас есть 250000 уникальных значений, но только 15969 уникальных хеш-кодов. Из-за большого количества конфликтов Java 8 свопирует списки с деревьями. В вашем случае это только добавляет накладные расходы, потому что многие элементы не только имеют одну и ту же позицию в хеш-таблице, но и один и тот же хеш-код. В любом случае дерево заканчивается как связанный список.

Есть несколько способов исправить это:

  • Улучшите свой хэш-код. return k1 * 500 + k2; устраняет проблему.

  • Используйте THashMap. Открытая адресация должна работать лучше в случае столкновений.

  • Сделайте Node реализацию Comparable. Это будет использоваться HashMap для построения сбалансированного дерева в случае конфликтов.