Введение
Java коллекции, наверное, наиболее распространенные сущности с которыми работает программист. Причем в завасимости от области разработки варьируется также и глубина осознания реализации той коллекции с которой работает разработчик. К примеру, в web разработке очень часто та или иная коллекция используется как промежуточная структура данных, целью которой является передать данные из DAO уровня в сервис или UI. Для многих опытных инженеров даже отсутствует разница между ArrayList и LinkedList, поскольку и та и другая структура полностью удовлетворяют его нуждам и нет причин использовать преимущества одной из них.
И в общем то хорошо все как-бы. Есть коллекции – бери любую работай и проблем не знай. Кабы вот на собеседованиях не пытали бесполезными вопросами. Да и в приграммировании низкоуровневых алгоритмов без них никуда, иногда за счет просаживания по перфомансу алгоритм может просто не взлететь и тогда уж очень важны становятся те “мелочи” на которые не обращаешь внимания изначально. Сюда же как следствие можно добавить модное сейчас направление “биг дата”, где очень пригодятся знания о всякоразных ньюансах и особенностях Java Collections Framework.
Давайте постараемся бегло рассмотреть общую структуру Java коллекций дабы получить общее представление об оных.
Для начала упомянем что Java Collections Framework не единственный фреймворк предоставляющий возможность работы с коллекциями вот еще некоторые:
1. Guava (Google Collections Library) – Библиотека добавляет несколько полезных реализаций структур данных, таких как мультимножество, мультиотображение и двунаправленное отображение. Улучшена эффективность.
2. Trove library – Реализация коллекций, позволяющая хранить примитивы (в Java Collections Framework примитивы хранить нельзя, только сущности унаследованные от класса Object), что позволяет повысить эффективность работы.
3. PCJ (Primitive Collections for Java) – так же как и Trove предназначены для примитивных типов, что позволит повысить эффективность.
4. Наконец Вы сами можете написать собственную коллекцию (тот же связной список). Иногда бизнес логика может затребовать существования некоего объекта, который должен частично реализовывать функционал коллекции. Так что опыт работы может здесь пригодится.
Как видим, выбрать есть из чего. Но для начала необходимо освоить базовые коллекции Java которыми пользуются чаще всего. К тому же некоторые сторонние библиотеки реализуют интерфейсы Java Collections Framework (пример Guava). То есть знание иерархии классов базовых коллекций позволит более быстро освоить сторонние библиотеки.
Базовые интерфейсы
В библиотеке коллекций Java существует два базовых интерфейса, реализации которых и представляют совокупность всех классов коллекций:
1. Collection – коллекция содержит набор объектов (элементов). Здесь определены основные методы для манипуляции с данными, такие как вставка (add, addAll), удаление (remove, removeAll, clear), поиск (contains)
2. Map – описывает коллекцию, состоящую из пар “ключ — значение”. У каждого ключа только одно значение, что соответствует математическому понятию однозначной функции или отображения. Такую коллекцию часто называют еще словарем (dictionary) или ассоциативным массивом (associative array). Никак НЕ относится к интерфейсу Collection и является самостоятельным.
Хотя фреймворк называется Java Collections Framework, интерфейс Map и его реализации входят во фреймворк также!
Интерфейсы Collection и Map являются базовыми, но они не есть единственными. Их расширяют другие интерфейсы, добавляющие дополнительный функционал. О них мы ещё поговорим.
Интерфейс Collection
Итак, что же порождает Collection? Как видно с диаграммы, интерфейс Collection не является базовым. Он расширяет интерфейс Iterable, у которого есть только один метод iterator(). Это значит что любая коллекция будет возвращать итератор а также ее можно без всяких трудностей использовать в конструкции foreach.
Итератор – объект, который абстрагирует за единым интерфейсом доступ к элементам коллекции. Итератор это паттерн позволяющий получить доступ к элементам любой коллекции без вникания в суть ее реализации.
Идем дальше. Как видим на рисунке, интерфейс Collection расширяют интерфейсы List, Set и Queue. Давайте рассмотрим зачем нужен каждый.
1. List – Представляет собой упорядоченную коллекцию, в которой допустимы дублирующие значения. Иногда их называют последовательностями (sequence). Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу.
2. Set – описывает коллекцию, не содержащую повторяющихся элементов. Это соответствует математическому понятию множества (set).
3. Queue – очередь. Это коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки. В дополнение к базовым операциям интерфейса Collection, очередь предоставляет дополнительные операции вставки, получения и контроля.
Реализации интерфейса List
Красным на рисунке выделены интерфейсы, зеленым – абстрактные классы, а синим готовые реализации. Сразу заметим что здесь не вся иерархия, а только основная её часть.
Как видим на рисунке, между интерфейсом и конкретной реализацией коллекции существует несколько абстрактных классов. Это сделано для того, что бы вынести общий функционал в абстрактный класс, таким образом реализовать повторное использование кода.
ArrayList – пожалуй самая часто используемая коллекция. Он инкапсулирует в себе обычный массив, длина которого может увеличиваться при добавлении новых элементов. Так как ArrayList использует массив, то время доступа к элементу по индексу минимально (В отличии от LinkedList). При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево, при этом реальный размер массива (его емкость, capacity) не изменяется. Если при добавлении элемента, оказывается, что массив полностью заполнен, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент.
LinkedList – Двусвязный список. Это структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и две ссылки («связки») на следующий и предыдущий узел списка. Доступ к произвольному элементу осуществляется за линейное время (но доступ к первому и последнему элементу списка всегда осуществляется за константное время — ссылки постоянно хранятся на первый и последний, так что добавление элемента в конец списка вовсе не значит, что прийдется перебирать весь список в поисках последнего элемента).
Реализации интерфейса Set
Как большинство читателей, вероятно, знают, хеш-таблица хранит информацию, используя, так называемый, механизм хеширования, в котором содержимое ключа используется для определения уникального значения, называемого хеш-кодом. Этот хеш-код затем применяется в качестве индекса, с которым ассоциируются данные, доступные по этому ключу.
Если Вы хотите использовать HashSet для хранения объектов СВОИХ классов, то вы ДОЛЖНЫ переопределить методы hashCode() и equals(), иначе два логически-одинаковых объекта будут считаться разными по хеш-коду, так как при добавлении элемента в коллекцию будет вызываться метод hashCode() класса Object (который скорее-всего вернет разный хэш-код для ваших объектов).
Важно отметить, что класс HashSet не гарантирует упорядоченности элементов, поскольку процесс хеширования сам по себе обычно не порождает сортированных наборов. Если вам нужны сортированные наборы, то лучшим выбором может быть другой тип коллекций, такой как класс TreeSet.
LinkedHashSet – поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать упорядоченную итерацию вставки в набор. То есть, когда идет перебор объекта класса LinkedHashSet с применением итератора, элементы извлекаются в том порядке, в каком они были добавлены.
TreeSet – коллекция, которая хранит свои элементы в виде упорядоченного по значениям дерева. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n).
Реализации интерфейса Queue
PriorityQueue – единственная прямая реализация интерфейса Queue (не считая LinkedList, который больше является списком, чем очередью).
Реализации интерфейса Map
Интерфейс Map соотносит уникальные ключи со значениями. Ключ — это объект, который вы используете для последующего извлечения данных. Задавая ключ и значение, вы можете помещать значения в объект карты. После того как это значение сохранено, вы можете получить его по ключу.
HashMap — основан на хэш-таблицах, реализует интерфейс Map. Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов. Больше можно почитать здесь.
LinkedHashMap – расширяет класс HashMap. Он создает связный список элементов в карте, расположенных в том порядке, в котором они вставлялись. Это позволяет организовать перебор карты в порядке вставки. То есть, когда происходит итерация по коллекционному представлению объекта класса LinkedHashMap, элементы будут возвращаться в том порядке, в котором они вставлялись. Вы также можете создать объект класса LinkedHashMap, возвращающий свои элементы в том порядке, в котором к ним в последний раз осуществлялся доступ. Рекомендуется почитать.
Небольшое замечание. Очень часто, как было уже означено, есть необходимость использовать список пар (ключ значение). И, по правде говоря, в Java не существует из коробки коллекции, которая бы позволила наполнить этот список и затем по нему пройтись. Выход казалось бы очевидный – создать кастомный класс пары (ключ, значение) и помещать такие объекты в любимый список. Но очень часто программисты для этого используют именно HashMap. Но тут есть два ньюанса. Во первых механизм хеширования. Для описанной задачи он явно излишний – ведь обходить нам надо весь список по порядку а не брать произвольный элемент изнутри. И во вторых порядок. Как было уже сказанно HashMap не гарантирует порядок хранения элементов. В отличие от LinkedHashMap. Посим как вывод, если вам нужен упорядоченный список пар – используйте LinkedHashMap.
TreeMap – красно-черное дерево реализующее интерфейс NavigableMap. Коллекция сортируется по естественному упорядочиванию (natural ordering) ее ключей или с помощью интерфейса Comparator который задается при создании коллекции. Эта имплементация гарантирует время доступа log(n) для следующих методов: containsKey, get, put и remove.
WeakHashMap – основан на хэш-таблицах, реализует интерфейс Map с так называемыми слабыми ключами (weak keys). Пара в данной коллекции автоматически будет удалена когда ссылка на ключ больше нигде не используется. Другими словами, нахождение объекта представленного ключем в данной коллекции не блокирует сборщик мусора от зачистки. После того как ключ будет зачищен вся пара будет удалена из коллекции.
Другие коллекции
Их еще называют “устаревшими”. Но я не нашел аннотации @Deprecated или каких-либо иных, которые бы запрещали их использование в коде.
- Enumeration — Интерфейс. В современной версии Java рекомендуется применять Iterator.
- Dictionary — Абстрактный класс, аналог интерфейса Map. Реализации не имеет, посим рекомендую его рассматривать как интерфейс. Наиболее известная реализация – Hashtable.
- Hashtable — Класс. Имплементит классическую структуру данных – хэш таблицу. В современных версиях Java рекомендуется использовать HashMap.
- Vector — Класс. Аналог класса ArrayList. Поддерживает упорядоченный список элементов, хранимых во “внутреннем” массиве.
- Stack — Класс. Производный от Vector, в который добавлены методы “вталкивания” (push) и “выталкивания” (pop) элементов, так что список может трактоваться в терминах, принятых для описания структуры данных стека (stack).
Все методы Hashtable, Stack, Vector являются синхронизированными, что делает их менее эффективными в однопоточных приложениях.
Синхронизированные коллекции
Получить синхронизированные объекты коллекций можно с помощью статических методов synchronizedMap и synchronizedList класса Collections.
Map m = Collections.synchronizedMap(new HashMap());
List l = Collections.synchronizedList(new ArrayList());
Синхронизированные обрамления коллекций synchronizedMap и synchronizedList иногда называют условно потоко безопасными – все операции в отдельности потокобезопасны, но последовательности операций, где управляющий поток зависит от результатов предыдущих операций, могут быть причиной конкуренции за данные. Здесь более. Условная безопасность потоков, обеспечиваемая synchronizedList и synchronizedMap представляет скрытую угрозу – разработчики полагают, что, раз эти коллекции синхронизированы, значит, они полностью потокобезопасны, и пренебрегают должной синхронизацией составных операций. В результате, хотя эти программы и работают при лёгкой нагрузке, но при серьёзной нагрузке они могут начать выкидывать NullPointerException или ConcurrentModificationException.
Кроме того всегда существует возможность “классической” синхронизации с помощью блока synchronized.
Заключение
В заключение приведем общую диаграмму рассмотренной иерархии:
