Коллекции в Java

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

Что же такое коллекции? Коллекции (иногда их называют контейнерами) - это классы, которые позволяют хранить и что-то делать с некоторой группой объектов. Вы наверняка знаете самый попсовый пример коллекции - это массив. Во многих языках работа с массивами встроена на языковом уровне (каламбурно). Массивы - низкоуровневое понятие. Для того, чтобы успешно работать с ними нужно помнить о длине массива. Операции удаления и добавления элементов основаны на индексных операциях, что тоже является достаточно лоулвл. Именно по этой причине программисты полюбили всякие рекурсивные (в понятийном смысле) структуры данных (списки, массивы) - у них проще интерфейс. 

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

В Java набор классов, реализующих работу с коллекциями называется Java Collection Framework. Все эти классы реализуют некоторые интерфейсы, то есть внутри фреймворка существует разделение между тем, "что делает класс" от "как он реализован". Разумеется, при разработке прикладных уже программ сохраняется стандартное требование - используйте интерфейсы везде, где можно, не внедряя (injection, наверное слышали это) зависимость в программу. Пройдемся по списку интерфейсов, рассмотрев основные use cases:

1. java.util.List<E>. Как видно из названия, этот интерфейс для списков, то есть для такой коллекции, где упорядоченно хранится набор объектов. Этот порядок задается очередностью добавления элементов. Внутри такого списка возможно хранение одинаковых объектов. Также, существует операция для получения различных элементов, как одиночных, так и прямо части списка. 
2. java.util.Queue<E>. Ну а это интерфейс для очереди, FIFO (First in - first out). 
3. java.util.Deque<E>. Интерфейс для двунаправленной очереди. То есть, добавлять и удалять элементы можно с обоих концов.
4. java.util.Set<E>. Множества, как много в этом слове... Коллекции, которые реализуют этот интерфейс гарантируют невозможность добавления одинаковых элементов, то есть все элементы в такой коллекции уникальны. 
5. java.util.SortedSet<E>. То же, что предыдущий интерфейс, но еще и элементы в порядке возрастания внутри коллекции. 
6. java.util.Map<K, V>. Ну а это любимые наши словари. То есть списки "ключ-значение". Одному элементу V ставится в соответствие элемент один или более элемент K. Еще одно название для подобных коллекций - ассоциативные массивы.
7. java.util.SortedMap<K, V>. То же, что и предыдущее, но ключи расположены в порядке возрастания.

Мы рассмотрели ключевые интерфейсы коллекций. Теперь посмотрим на реализации. На самом деле, при всем многообразии интерфейсов коллекции и их реализаций, "в потрохах", то бишь внутри, данные в Java Collection Framework хранятся 3-мя основными способами: массивы, связанные списки (Linked List), бинарные  Рассмотрим каждый из способов хранения коллекций в памяти:

Массивы

Наверняка вы знаете, что это такое. У нас есть кусочек памяти, и у нас есть разные объекты. При этом мы знаем размер объекта, что позволяет перемещаться внутри массива, чтобы получать его элементы. Разумеется, это означает, что данные у нас одного типа. Чтобы размер элемента был одинаковый. Время обращения к элементу массива - O(1). Операции вставки и удаления - O(n). Самой проблемной будет являться вставка в начало массива. Вставку можно представить следующим алгоритмом (i - индекс, куда вставляем):

1. скопировать элементы с индексами i..n-1 в промежуточный массив;
2. увеличить длину всего массива на 1;
3. присвоить i-му элементу новое значение;
4. скопировать все элементы из промежуточного массива обратно.

Коллекции на основе этого интерфейса сами следят за размером массива, удваивая размер при достижении предела. Реализации, имеющие в основе массивы: java.util.ArrayList<E>, java.util.ArrayDeque<E> и так далее. Расход памяти - O(n). Но операции вставки и удаления приводят к созданию промежуточных массивов. 

Связанные списки

Связанные списки - это цепочки объектов, ссылающиеся друг на друга. Примером реализации такого подхода к организации коллекции является java.util.LinkedList<E>. Этот класс, внутри, имеет ссылки на предыдущий и на следующий элемент. Эта реализация представляет собой замкнутый двусвязный список. Скорость доступа к элементу зависит от положения этого элемента относительно начала (головы) списка, в среднем - O(n). Таким образом, коллекции реализующие такой подход к хранению данных, лучше не использовать там, где нужен доступ к произвольному элементу массива. Операция вставки будет чуть быстрее, чем в случае с массивом. Разумеется, основная проблема в данном случае - это поиск места, куда вставить элемент. Вставка и удаление элемента в начало занимает O(1), но в среднем O(n). 

Бинарные деревья

Бинарные деревья - это структура данных, особенно хорошо пригодная для хранения и поиска упорядоченных некоторым образом объектов. Скорость доступа в контейнерах типа java.util.TreeSet<E>, TreeMap<K,V> - O(log(n)). Скорость добавления и удаления элементов - O(log(n)). Расход памяти - O(n).

Хэш-таблицы

Хэш-таблицы - это специальные контейнеры, на основе массивов, в которых поиск определенного элемента осуществляется а с помощью хэш-функции. В хэш-таблицах индекс определяется на основе хэш-функции, а в нужной позиции массива хранится указатель на связанный список элементов у которых хэш-функции совпадают. Среднее время поиска элемента - O(1). Наихудший случай поиска - O(n). Операции вставки всегда O(1). Операция удаления - может быть как O(n), так и O(1). Время поиска и удаления зависит от хэш-функции. Если хэш функция равномерно распределяет элементы и нет никаких коллизий (коллизия - это когда разные объекты имеют одинаковое вычисленное значение хэш-функции). Ввиду того, что хэш-таблицы - обширная штука, выставлю ссылку, где более подробно расписано о этой структуре данных http://bitsofmind.wordpress.com/2008/07/28/introduction_in_hash_tables/. Контейнеры, реализующие данный способ организации данных - java.util.HashSet<E>, java.util.HashMap<K,V>, java.util.WeakHashMap<K,V>.

Небольшая итоговая табличка по интерфейсам и реализациям, спертая у Джошуа Блоха (крутой Java парень):

Интерфейс	На базе хэш-таблиц	На базе массивов	На базе деревьев	На базе связанных списков	На базе хэш-таблиц + связанных списков
Set	HashSet		TreeSet		LinkedHashSet
List		ArrayList		LinkedList
Queue
Deque		ArrayDeque
Map	HashMap		TreeMap		LinkedHashMap

Тестирование

Для тестирования было решено использовать JUnit тест, ну и несколько обобщить задачку, чтобы было легко тестировать коллекции. Был найден абсолютно подходящий для этого код - Тестирование произведено исключительно на Integer, но не проблема подставить и другие значения, кому нужно. Производится несколько прогонов. Исходный код доступен на github - https://github.com/JEuler/CollectionTest.

Итак, результаты для некоторых коллекций (время в микросекундах):

Коллекция	Размерность	Время добавления	Время итерации	Время поиска элемента	Время удаления
TreeSet	1 000 000	195 844	99 436	8.7	98 308
TreeSet	100 000	10 277	6 549	3.6	4 878
TreeSet	10 000	540	523	2.1	357
TreeSet	1 000	41.9	42.8	0.2	29.1
TreeSet	100	2.8	3.6	0.0	2.2
TreeSet	10	0.1	0.4	0.0	0.1
ArrayList	1 000 000	9 314	32 885	3 915	85 057 989
ArrayList	100 000	513	3 255	93.4	608 277
ArrayList	10 000	51.9	323	8.5	4 462
ArrayList	1 000	4.5	32.6	0.8	57.5
ArrayList	100	0.4	3.4	0.0	1.5
ArrayList	10	0.0	0.4	0.0	0.1
LinkedList	1 000 000	20 874	59 720	3 465	27 076
LinkedList	100 000	985	5 590	229	692
LinkedList	10 000	77.3	549	22.4	68.8
LinkedList	1 000	7.4	55.0	2.1	6.8
LinkedList	100	0.7	5.6	0.2	0.6
LinkedList	10	0.0	0.6	0.0	0.0
HashSet	1 000 000	32 217	113 363	8.4	19 671
HashSet	100 000	1 575	18 924	7.0	1 540
HashSet	10 000	164	9 345	6.6	139
HashSet	1 000	15.5	8 555	7.7	14.5
HashSet	100	2.3	8 447	7.2	1.9
HashSet	10	0.9	8 440	7.1	0.8
LinkedHashSet	1 000 000	55 723	74 168	7.4	24 765
LinkedHashSet	100 000	6 076	7 039	5.8	1 589
LinkedHashSet	10 000	259	696	4.3	220
LinkedHashSet	1 000	21.1	69.7	1.1	15.1
LinkedHashSet	100	2.6	7.0	0.1	1.4
LinkedHashSet	10	0.8	0.8	0.0	0.1

P.S. Есть какая то библиотека коллекций High Perfomance Primitive Collection - http://labs.carrotsearch.com/hppc.html. Может быть, имеющиеся там коллекции быстрее, чем те, которые есть в Java Collection Framework.

P.P.S. Есть http://sourceforge.net/projects/javacollections/ - jar файл, где можно погонять разные тесты производительности коллекций. Но с виду, там только один прогон идет.
P.P.P.S. http://java.dzone.com/articles/java-collection-performance - здесь тоже можно посмотреть различные графики по производительности коллекций.

Ссылки и благодарности

1. http://vanillajava.blogspot.ru/2011/08/comparing-collections-speeds.html - код тестирования был подсмотрен здесь. http://vanillajava.blogspot.ru/2011/08/collections-library-for-millions-of.html - здесь некая коллекция для большого количества элементов, любопытно, можно посмотреть. 
2. http://appliedjava.wordpress.com/2010/09/23/java-collections-framework/ - хорошая информация о Java Collection Framework. 
3. http://korzh.net/2010-11-proizvoditelnost-osnovnyx-kollekcij-java-sravnenie-s-analogami-net.html - результат тестирования коллекций Java. Много графиков, рекомендуется к прочтению. В отличие от текущей статьи, представлено сравнение расходуемой памяти. 

Выводы

Выводы каждый может сделать сам, в каком случае какую структуру использовать. Но в целом - если у вас много элементов и надо быстро их добавлять и по ним скакать - то ArrayList. Если нужно, чтобы более менее быстро всё работало - TreeSet, LinkedHashSet. Последнему нужна хэш-функция. HashSet позволит вам быстрее всего находить конкретный элемент (проверить его наличие), но итерация по всем элементам - самая дорогая среди всех структур. Все эти аспекты и означают, что каждый должен сам решить, что ему использовать.