Коллекции: list, set, map

Содержание

1. Список (list)
2. Набор (set)
3. Словарь (map)

Под коллекциями в программировании подразумевают объекты, которые хранят внутри себя какой-либо набор значений и предоставляют набор методов для обращения к этим значениям. В Java можно выделить 3 наиболее часто используемых типа коллекций: списки (list), наборы (set) и словари (map). При объявлении коллекции типизируются каким-либо типом, т.е. одна коллекция хранит данные одного типа.

Список (list)

Списки в Java реализуют интерфейс List, который, в свою очередь, расширяет интерфейс Collection. Список позволяет хранить любые значения, в том числе повторяющиеся. Итерация (обход) списка происходит в порядке добавления элементов. Т.е. элемент, добавленный первым, при итерации также будет первым.

Две наиболее частые реализации интерфейса List – это ArrayList и LinkedList.

Класс ArrayList построен на базе массива. Это означает, что доступ по индексу (порядковому номеру элемента) происходит очень быстро. А добавление элементов в середину списка в общем случае довольно затратно, т.к. нужно будет подвинуть вправо каждый элемент, который идёт после добавляемого. С удалением такая же штука. Кроме того, массив, лежащий в основе этой структуры данных, имеет конечное количество свободных ячеек и если их перестанет хватать, придётся создать новый массив большего размера, перенеся в него все элементы из исходного. Но всё это скрыто внутри реализации ArrayList.

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

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

Набор (set)

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

Сравнение любых двух объектов между собой в Java происходит при помощи методов equals() и hashCode() из базового класса Object. Метод equals выполняет полное сравнение элементов, тогда как hashCode только лишь вычисляет хеш-функцию, которая может принимать одинаковые значения для разных элементов. Соотношение между этими двумя методами всегда такое: если для двух объектов hashCode возвращает одинаковое значение, то equals при этом может быть false, однако если equals возвращает true, то hashCode обязан возвращать одинаковые значения. При создании собственных классов, если их предполагается использовать в наборах или словарях, вы должны переопределить эти два метода, чтобы коллекции работали с ними корректно.

Теперь рассмотрим три основные реализации интерфейса Set.

Первая из них – это HashSet. Когда мы будем выполнять проход по этому набору, то порядок элементов на первый взгляд нам покажется хаотичным. Однако на самом деле он будет зависеть от значения хэш-функции для каждого элемента. Также обратите внимание, что мы два раза добавляем «яблоко» в набор, однако в результате увидим его только один раз.

Следующая реализация – это LinkedHashSet, которая расширяет предыдущую. Основное различие заключается в том, что при обходе элементов мы будем видеть их в порядке добавления:

Ну а третья реализация под названием TreeSet имеет в своей основе структуру данных «красно-чёрное дерево», что позволяет сортировать элементы автоматически:

Поэтому если хотите сохранять порядок добавления элементов – используйте LinkedHashSet, а если хотите получить отсортированный набор – тогда используйте TreeSet.

Словарь (map)

Также смотрите статью Удобные методы работы с Map.

Интерфейс Map представляет собой набор из пар элементов типа «ключ-значение». На русский язык это переводят по-разному: карта, маппинг, хэш-таблица. Но мне больше всего нравится аналогия со словарём, ведь с этим набором мы примерно так и работаем: имеем какое-то слово (ключ) и пытаемся найти его перевод (значение).

Словарь гарантирует, что каждому ключу соответствует одно и только одно значение. Если по уже существующему ключу положить новое значение, то оно перезатрёт старое. При работе с ключами также используются методы equals и hashCode. И по аналогии с Set здесь мы также имеем три основных реализации интерфейса Map.

Первая реализация – это HashMap, которая не гарантирует никакого порядка элементов при обходе. Обратите внимание, что при повторном добавлении элемента с тем же ключом, мы теряем первое значение:

Ещё одна реализация – это LinkedHashMap, которая сохраняет порядок добавления:

Ну и третья популярная реализация интерфейса Map – это TreeMap, которая сортирует ключи по порядку:

Поэтому если хотите сохранять порядок добавления элементов – используйте LinkedHashMap, а если хотите получить отсортированный по ключам набор – тогда используйте TreeMap.