Performance Test: Map

Продолжаем рассматривать Java Collection Framework (предыдущая статья) и переключаемся на дерево классов Map, а именно на список наиболее распространенных реализаций интерфейса Map. Давайте для начала вспомним как выглядит упрощенная иерархия классов дерева Map.

Screen Shot 2014-07-17 at 9.27.16 PM


HashMap — обычная хеш-таблица. Используем ее всегда, если не нужен специфический функционал, который есть у остальных реализаций ниже. Порядок вставки (insertion order) не сохраняется, поэтому разные способы прохода по HashMap выдают элементы в разном порядке, независимо от порядка добавления.

Hashtable — все выше сказанное о HashMap применимо и к этому классу, но основные методы этой реализации синхронизированы, то есть помечены ключевым словом synchronized (вкратце скажем, что синхронизация применяется в многопоточное среде). Также, Hashtable не разрешает использовать null в качестве ключей и значений хеш-таблицы. Будет выброшен NullPointerException, если мы «подсунем» null.

LinkedHashMap — элементы связаны, как в связном списке. Порядок вставки сохраняется, это и есть её ключевая особенность. Класс LinkedHashMap является наследником класса HashMap. В качестве элемента, используется свой вложенный класс, который в свою очередь поддерживает связи на предыдущий и следующий элемент.

TreeMap — для быстрого доступа к элементам используется отсортированное дерево (красно-черное). 
Элементы хранятся в отсортированном порядке 
(но не в порядке добавления).

Далее мы сравним производительность этих реализаций при работе с методами put, get, containsValue, а также перебором с помощью итератора. Код для тестирования, был переиспользован из предыдущей статьи, но слегка модифицирован, давайте рассмотрим основные моменты (текст кода сокращен, мы опускаем стандартные места, чтобы показать только суть):

PutMapTest: вставка 1 000 000 элементов в пустую таблицу

public PutMapTest(Map mapToTest, int size){
        this(mapToTest);
        this.size = size;
    }

    private void prepareKeys() {
        keys = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            keys.add(i + 1);
        }

        Collections.shuffle(keys);
    }

    @Override
    public void run() {
        Random random = new Random();

        for (Integer key : keys) {
            mapToTest.put(key, random.nextInt(size));
        }
    }

GetMapTest: поиск элементов в таблице с 1 000 000 элементов

public void run() {
    for (Object key : mapToTest.keySet()) {
        mapToTest.get(key);
    }
}

IterateMapTest: перебор элементов с помощью итератора в таблице с 1 000 000 элементов

    public void run() {
        Iterator i = mapToTest.keySet().iterator();

        while(i.hasNext()) {
            i.next();
        }
    }

ContainsMapTest: проверка вхождения по значению в таблице с 1000 элементов

public class ContainsMapTest extends  MapTest implements Runnable {
    public static final int SIZE = 1000;

    public ContainsMapTest(Map map) {
        super(map);
        new PutMapTest(map, SIZE).run();
    }

    @Override
    public void run() {
        for (Object value: mapToTest.values()) {
            mapToTest.containsValue(value);
        }
    }
}

Результат из консоли:

Put 1000000 elements in map ====
HashMap : 0.252 sec
Hashtable : 0.927 sec
LinkedHashMap : 1.736 sec
TreeMap : 1.571 sec
————————————-
Get 1000000 elements from map ====
HashMap : 0.057 sec
Hashtable : 0.075 sec
LinkedHashMap : 0.081 sec
TreeMap : 0.117 sec
————————————-
Iterate 1000000 elements in map ====
HashMap : 0.026 sec
Hashtable : 0.014 sec
LinkedHashMap : 0.015 sec
TreeMap : 0.022 sec
————————————-
Contains value for 1000 elements in map ====
HashMap : 2.103 sec
Hashtable : 195.621 sec
LinkedHashMap : 3.927 sec
TreeMap : 7.145 sec

Наша оценка, с использованием баллов в виде количества звезд приведена ниже. Конкретную разницу в секундах лучше смотреть выше в консольном выводе. На схеме ниже, мы хотим лишь отобразить порядок — насколько лучше или хуже та или иная реализации в определенной ситуации:

Screen Shot 2014-07-17 at 6.17.20 PM

Общая рекомендация использовать — HashMap, но если нам нужно отсортированное дерево, синхронизация или сохранение порядка вставки, то выбираем остальные, имеющиеся в арсенале реализации. Касательно Hashtable — она не отменяет написания собственной синхронизации, если нам нужно вызывать несколько методов последовательно в рамках одного потока, чтобы другие потоки при этом ожидали доступ к монитору объекта.

Для тех кому интересна реализации тестирования, приводим листинги основных методов.

    private void runMapTest() throws ExecutionException, InterruptedException {
        int reportSize = 15;
        performanceReport.reset(reportSize);
        ExecutorService executor = Executors.newFixedThreadPool(reportSize);

        Map hashMap = new HashMap();
        Map hashtable = new Hashtable();
        Map linkedMap = new LinkedHashMap();
        Map treeMap = new TreeMap();

        performanceReport.addMessage(String.format("Put %d elements in map ====", MAP_PUT_SIZE)).
        track(executor.submit(buildTest(HASHMAP_CLASS, new PutMapTest(hashMap))).get()).
        track(executor.submit(buildTest(HASHTABLE_CLASS, new PutMapTest(hashtable))).get()).
        track(executor.submit(buildTest(LINKED_HASHMAP_CLASS, new PutMapTest(linkedMap))).get()).
        track(executor.submit(buildTest(TREEMAP_CLASS, new PutMapTest(treeMap))).get()).
        addEmptyLine();

        performanceReport.addMessage(String.format("Get %d elements from map ====", MAP_PUT_SIZE)).
        track(executor.submit(buildTest(HASHMAP_CLASS, new GetMapTest(hashMap))).get()).
        track(executor.submit(buildTest(HASHTABLE_CLASS, new GetMapTest(hashtable))).get()).
        track(executor.submit(buildTest(LINKED_HASHMAP_CLASS, new GetMapTest(linkedMap))).get()).
        track(executor.submit(buildTest(TREEMAP_CLASS, new GetMapTest(treeMap))).get()).
        addEmptyLine();

        performanceReport.addMessage(String.format("Iterate %d elements in map ====", MAP_PUT_SIZE)).
        track(executor.submit(buildTest(HASHMAP_CLASS, new IterateMapTest(hashMap))).get()).
        track(executor.submit(buildTest(HASHTABLE_CLASS, new IterateMapTest(hashtable))).get()).
        track(executor.submit(buildTest(LINKED_HASHMAP_CLASS, new IterateMapTest(linkedMap))).get()).
        track(executor.submit(buildTest(TREEMAP_CLASS, new IterateMapTest(treeMap))).get()).
        addEmptyLine();

        performanceReport.addMessage(String.format("Contains value for %d elements in map ====", 1000)).
        track(executor.submit(buildTest(HASHMAP_CLASS, new ContainsMapTest(new HashMap()))).get()).
        track(executor.submit(buildTest(HASHTABLE_CLASS, new ContainsMapTest(new Hashtable()))).get()).
        track(executor.submit(buildTest(LINKED_HASHMAP_CLASS, new ContainsMapTest(new LinkedHashMap()))).get()).
        track(executor.submit(buildTest(TREEMAP_CLASS, new ContainsMapTest(new TreeMap()))).get());

        executor.shutdown();
    }
    
private Callable<PerformanceTracker> buildTest(final String collectionName,
                                                   final Runnable listTest) {
        return new Callable<PerformanceTracker>() {
            @Override
            public PerformanceTracker call() {
                final long startTime = System.currentTimeMillis();
                listTest.run();
                final long endTime = System.currentTimeMillis();
                return new PerformanceTracker(collectionName, startTime, endTime);
            }
        };
    }

...

public abstract class MapTest implements Runnable {
    public static final int MAP_PUT_SIZE = 1_000_000;

    public static final String HASHMAP_CLASS = "HashMap";
    public static final String HASHTABLE_CLASS = "Hashtable";
    public static final String LINKED_HASHMAP_CLASS = "LinkedHashMap";
    public static final String TREEMAP_CLASS = "TreeMap";

    protected Map mapToTest;

    public MapTest(Map mapToTest) {
        this.mapToTest = mapToTest;
    }

}

public class PerformanceReport {
    private List trackerList = new ArrayList<>();

    public void reset(int size) {
        trackerList = new ArrayList<>(size);
    }

    public PerformanceReport track(PerformanceTracker performanceTracker) {
        trackerList.add(performanceTracker);
        return this;
    }

    public void printReport(PrintStream outputStream) {
        for (PerformanceTracker tracker : trackerList) {
            if (!tracker.isPlainString()) {
                outputStream.printf("%s : %.3f sec%n", tracker.getCollectionName(), 
                    tracker.getDuration() / 1000f);
            } else {
                outputStream.println(tracker.getMessage());
            }
        }
    }

    public void addEmptyLine() {
        PerformanceTracker performanceTracker = 
            new PerformanceTracker("-------------------------------------", true);
        performanceTracker.setPlainString(true);
        trackerList.add(performanceTracker);
    }

    public PerformanceReport addMessage(String message) {
        PerformanceTracker performanceTracker = new PerformanceTracker(message, true);
        trackerList.add(performanceTracker);
        return this;
    }
}

 


Комментарии:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>