Коллекционер хорошего кода: что нужно знать о Java Collections Framework

Работа с массивами данных, их структурирование, поиск соответствий между ними, фильтрация — все это основа любой программы, написанной на Java. Поэтому программистам важно иметь в своем арсенале инструменты, которые максимально упростили бы и структурировали работу с этими данными. Именно здесь и берут свое начало коллекции фреймворков на Java.

Что такое Collections Framework

Это набор различных интерфейсов для работы с группами объектов при программировании на Java. Коллекции позволяют производить манипуляции с массивами (Array), очередями (Queue, Stack), списками (List), ключами и значениями (Map) и другими типами объектов.

Любая коллекция на Java строго структурирована: одни интерфейсы подчиняют другие, последние же — расширяют функционал своих «‎‎старших братьев» по иерархии.

В основе иерархической структуры Java Collections Framework лежит интерфейс Collection. Это главенствующий интерфейс. Общая коллекция вмещает в себя все остальные виды коллекций и позволяет работать с группами объектов благодаря основным методам, среди которых:

• add(…) — добавить;
• remove(…) — убрать;
• clear(…) — очистить.

Интерфейс Collection наследуется от Iterable, а значит все подчиненные ему коллекции являются итерируемыми вне зависимости от типа их реализации. Благодаря этому в Collection вы можете получить итератор, который позволит вам пройтись по другим интерфейсам коллекций.

Интерфейсу Collection подчинены три главных интерфейса:

• Set — позволяет работать с множествами данных;
• List — взаимодействует со списками данных;
• Queue — работает с очередью.

Интерфейс Map работает с данными типа «‎‎ключ/значение». Он стоит в этом списке отдельно, и чуть позже я объясню, почему это так. А пока давайте пройдемся по основным типам коллекций и выясним, за что отвечает каждая из них. 

Интерфейс List и его реализации — ArrayList и LinkedList

List — это упорядоченная коллекция, наиболее часто используемая в Java Collections Framework. Этот интерфейс контролирует, где вставлен каждый элемент списка. При работе с List пользователю доступны элементы списка по их целочисленному индексу (позиции в списке).

Интерфейс List имеет две стандартные реализации — ArrayList и LinkedList.

Смысл в том, что можно написать и другие реализации, но в JDK уже есть две, которые доступны «‎‎из коробки».

ArrayList содержит внутри себя массив, длина которого будет увеличиваться автоматически при добавлении в него новых элементов.

Вторая имплементация интерфейса List — класс LinkedList. Это список с двумя связями, где каждый элемент содержит ссылку на предшествующий и следующий элементы списка.

ArrayList и LinkedList — идентичны, то есть их методы полностью совпадают. Они оба могут добавлять и извлекать элементы из любой части списка. Так в чем же отличие? Главная разница между ними в цикломатической сложности операций — количестве линейно независимых маршрутов, проходящих через код программы. Чем меньшее количество маршрутных точек будет проходить каждая отдельно взятая команда, тем быстрее будет работать программа.

Для наглядности различий в цикломатической сложности между двумя классами рассмотрим таблицу:

Как видите, основные преимущества класса LinkedList связаны с операциями (iterator.remove() и ListIterator.add(E element). Их цикломатическая сложность всегда будет равна О(1). В случае добавления add(E element) лучше использовать LinkedList, а вот для get(int index) — ArrayList.

Так же дела обстоят с оператором add(int index, E element). Цикломатическая сложность этой операции для LinkedList будет ниже только в том случае, если сам индекс будет равен нулю. Для всех остальных случаев разумнее использовать именно ArrayList.

Это же касается и операции remove: для класса LinkedList ее цикломатическая сложность будет вдвое меньше, чем для ArrayList. Забегая наперед скажу, что именно ArrayList используют в подавляющем случае работ в интерфейсе List.

Интерфейс Set

Set — это коллекция, которая не содержит повторяющихся элементов. Этот интерфейс создан для моделирования абстракций математического множества.

Иерархия Set включает в себя два интерфейса — SortedSet и NavigableSet — и три основных класса. О последних расскажу подробнее:

• HashSet — коллекция, которая не позволяет хранение одинаковых элементов благодаря содержанию в себе объекта HashMap. Он использует для хранения данных хэш-таблицы.
• LinkedHashSet — подобная HashSet, в которой элементы объединены между собой в порядковый список. В этом случае элементы хранятся в том же порядке, в котором и добавляются (благодаря содержанию в себе объекта LinkedHashMap).
• TreeSet — коллекция, которая использует для хранения элементов упорядоченное по значениям дерево. TreeSet содержит в себе TreeMap — коллекцию, которая использует для хранения своих элементов сбалансированное красно-черное бинарное дерево. Благодаря этому операции add, remove и contains в этой коллекции займут гарантированное время, равное log(n). А это — весомое преимущество по сравнению с другими имплементациями интерфейса Set.

Интерфейс Queue

Все мы не любим очереди: кому нравится напрасно тратить свое время в ожидании чего-то? Но вы точно полюбите очереди, если научитесь с ним работать 🙂 В Java Collections Framework за работу с очередью отвечает интерфейс Queue, который имеет довольно простую иерархию:

Queue способен упорядочить элементы в очереди по двум основным типам:

• при помощи полученного в конструкторе интерфейса Comparator, который сравнивает новые объекты в очереди с предыдущими;
• с помощью интерфейса Comparable, который необходим для упорядочения элементов в соответствии с их натуральным порядком.

Интерфейс Map

Это коллекция предназначена для работы с данными типа «‎‎ключ/значение». Под ключом мы имеем ввиду объект, который используем для извлечения данных, которые он в себе содержит. В структурном плане Map не наследует коллекцию Iterable и имеет ряд уникальных методов, характерных только для него.

У этого интерфейса схожая с Set структурная иерархия классов. Map реализуется с помощью четырех имплементаций: HashMap, TreeMap (о них я писал выше), LinkedHashMap и WeakHashMap:

• LinkedHashMap расширяет функционал HashMap и способен организовать перебор элементов в первоначальном порядке. То есть при осуществлении итерации по методу LinkedHashMap все объекты будут возвращены в строгом порядке их добавления.
• WeakHashMap — класс, который организовывает слабые ссылки объектов со своими ключами. Используется для динамических объектов. Например, при построении систем с функцией сбора мусора. Она не вносится в перечень объектов, подлежащих удалению из-за того, что игнорируется сборщиком мусора при выявлении объектов, которые в ней содержаться.

Коллекции в Java достаточно объемны. Они содержат в себе массу интерфейсов и реализаций, о которых точно можно написать не одну статью.

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

Правильное понимание принципов работы с коллекциями останется одним из главных навыков для качественного программирования на Java.