Производительность основных коллекций java. Сравнение с аналогами .Net

Тема Java Collections API одна из основополагающих при изучении. На моей памяти ни одно собеседование на должность java-программиста не обходилось без выяснения тонкостей использования того или иного класса коллекций. В сети и книгах очень много информации по этой теме, однако как правило слабо охватываются вопросы связанные с производительностью и потреблением ресурсов. Соответственно, создаются некоторые сложности при выборе класса для применения в том или ином случае, что особенно критично при разработке высоконагруженных систем.

Чтобы выбор был немного более прозрачным, я решил провести небольшое исследование по определению производительности коллекций при выполнении основных операций над их элементами. Также приведу небольшое сравнение показателей некоторых коллекций Java с классами-аналогами из .Net.

Коллекции в java

В качестве вступления пара слов об интерфейсах, реализуемых коллекциями. Есть 3 базовых интерфейса:

• Set — множество уникальных элементов;
• List — упорядоченный массив элементов;
• Map — ассоциативный массив вида ключ=>значение, где ключ и значение могут быть объектами любого класса. Ключи в списке должны быть уникальными.

Эти интерфейсы реализованы множеством классов. Из названия класса коллекции можно судить об ее особенностях. Возьмем для примера класс LinkedHashSet:

• слово Set говорит о реализации соответствующего интерфейса;
• Linked — означает, что элементы связаны между собой «по цепочке», т.е. каждый имеет ссылки на своих соседей. В данной реализации это позволяет сохранить последовательность элементов, в которой они были добавлены в коллекцию;
• Hash — говорит о том, что коллекция базируется на значениях, зависящих от значений Hash-кода для каждого элемента. Это позволяет производить быструю проверку наличия элемента в коллекции.

Функционал Java коллекций

Рассмотрим несколько основных реализаций и функции доступные для каждой:

• HashSet — множество базирующееся на хэш-кодах элементов. Порядок элементов при обходе(итерации) не определен. Не допускает дубликатов.
• TreeSet — множество отсортированное в натуральном порядке. Не допускает дубликатов.
• LinkedHashSet — множество базирующееся на хэш-кодах элементов. Порядок элементов соответствует последовательности добавления в коллекцию.
• LinkedList — связанный список. Каждый элемент ссылается на 2 соседних. Порядок элементов соответствует последовательности добавления.
• ArrayList — индексированный список. Каждому элементу соответствует индекс типа int.
• HashMap — ассоциативный массив. В качестве уникальных ключей используется множество базирующееся на хэш-кодах. Порядок элементов не определен.
• LinkedHashMap — ассоциативный массив. В качестве уникальных ключей используется множество базирующееся на хэш-кодах. Порядок элементов соответствует последовательности добавления.
• TreeMap — ассоциативный массив. В качестве уникальных ключей используется отсортированное в натуральном порядке множество.

* — в Map-классах для добавления элементов используется метод put, который можно трактовать и как вставку (insert). В тестах я использовал этот метод в категориях «добавление элемента» и «вставка элемента».

В большей части таблицы все понятно. Хочется заострить внимание на ячейках с “±”. Это означает, что функция для коллекции доступна, но ее использование требует большей бдительности, т.к. может повлечь большую трату ресурсов процессора. Рассмотрим сначала процедуру вставки элемента применительно к классам ArrayList и LinkedList. Для ArrayList алгоритм вставки в i-ю позицию будет выглядеть примерно так:
— скопировать элементы с индексами i..size-1 («хвост массива») во временный массив;
— увеличить длину массива на 1;
— присвоить i-му элементу новое значение;
— скопировать все элементы из временного массива обратно, начиная с индекса i+1.

Как можно догадаться — при увеличении размера массива операция вставки элемента в произвольную позицию будет занимать большее время. То же самое будет происходить и при удалении произвольного элемента. Это время возрастает пропорционально размеру массива и индексу вставляемого элемента. Соответственно самой ресурсоемкой будет вставка(удаление) элемента в начало массива (индекс 0). Далее в тестах приводится количественная оценка этого времени. Забегая вперед, следует сказать, что не стоит совсем отказываться от использования операций вставки. Если необходима не очень частая вставка элементов и размер массива не превышает 5-10 тыс. элементов, то производительность будет на приемлемом уровне.

Для LinkedList ситуация несколько иная: массив построен не по индексу, а цепочкой, т.е. каждый элемент имеет ссылки на соседние. Операция произвольной вставки будет потреблять времени немногим меньше, чем в ArrayList и также время будет расти пропорционально размеру массива. Основная потеря времени в этом случае происходит при поиске позиции, в которую необходимо вставить элемент. Т.к. индекс отсутствует, то позиция определяется перебором i элементов от головы или size-i от хвоста массива. Сама же процедура вставки сводится к изменению ссылок в двух соседних и вставляемом элементе. Основной плюс такой организации — это возможность «дешево» вставлять/удалять элементы в начало массива, независимо от его длины.

Исходя из вышеописанного, процедура выборки произвольного элемента по индексу будет быстро отрабатываться для ArrayList и намного медленней для LinkedList. Причем время выборки для ArrayList незначительно зависит от количества элементов в массиве, а для LinkedList оно растет пропорционально.Исходя из вышеописанного, процедура выборки произвольного элемента по индексу будет быстро отрабатываться для ArrayList и намного медленней для LinkedList. Причем время выборки для ArrayList незначительно зависит от количества элементов в массиве, а для LinkedList оно растет пропорционально.

Условия тестирования

Железо: AMD Athlon 64 X2 3800+, 4GB ОЗУ.
Софт: Windows Vista Bussines 32, Java 1.6.0_20, .NET v4.
Исследуемые параметры: основные функции чтения/записи для коллекций (см. таблицу выше).
Методика:

• для каждого исследуемого класса программа с набором процедур компилировалась отдельно;
• запуск производился 5 раз для каждого размера коллекции и в зачет шли средние арифметические от измеренных времен;
• в java время измерялось с помощью функции System.nanoTime(), в c#(.Net) — DateTime.Now();
• операции «проверка наличия элемента (contains)» и «чтение произвольного элемента (get)» выполнялись по 100 000 раз для каждого размера массива, элемент(индекс) для поиска генерировался случайно;
• в качестве элементов коллекций использовалась строка вида: «testString» + i. Эта же строка использовалась в качестве индекса для Map-коллекций.
• для java-коллекций с помощью профайлера был определен размер на основании данных об используемой памяти до создания коллекции и после.

Результаты тестирования

Размеры java-коллекций в зависимости от количества элементов

Сравнительные тесты java-коллекций

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

Сравнительные тесты java vs .net

Как можно увидеть — результаты в среднем примерно равны. Небольшой перевес в сторону java наблюдается лишь в коллекциях с размером более 500 000 элементов.
The Collections Framework API Reference