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

Question

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

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

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

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

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. Любые идеи?

Answer 1

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

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

1. Улучшить хэш-код. return k1 * 500 + k2; решает проблему.

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

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