Коллекции виды коллекций java

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

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

Список (list)

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

List list = new ArrayList<>();
list.add( «яблоко» );
list.add( «ананас» );
list.add( «яблоко» );
System.out.println(list); // На экране увидим: [яблоко, ананас, яблоко]

Две наиболее частые реализации интерфейса 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. Когда мы будет выполнять проход по этому набору, то порядок элементов на первый взгляд нам покажется хаотичным. Однако на самом деле он будет зависеть от значения хэш-функции для каждого элемента. Также обратите внимание, что мы два раза добавляем «яблоко» в набор, однако в результате увидим его только один раз.

Set hashSet = new HashSet<>();
hashSet.add( «яблоко» );
hashSet.add( «яблоко» ); // дубль
hashSet.add( «ананас» );
hashSet.add( «банан» );
System.out.println(hashSet); // На экране увидим: [банан, яблоко, ананас]

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

Set linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add( «яблоко» );
linkedHashSet.add( «яблоко» );
linkedHashSet.add( «ананас» );
linkedHashSet.add( «банан» );
System.out.println(linkedHashSet); // [яблоко, ананас, банан]

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

Set treeSet = new TreeSet<>();
treeSet.add( «яблоко» );
treeSet.add( «яблоко» );
treeSet.add( «ананас» );
treeSet.add( «банан» );
System.out.println(treeSet); // [ананас, банан, яблоко]

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

Словарь (map)

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

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

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

Map hashMap = new HashMap<>();
hashMap.put( «яблоко» , 1 );
hashMap.put( «яблоко» , 2 ); // повторное добавление
hashMap.put( «ананас» , 3 );
hashMap.put( «банан» , 4 );
System.out.println(hashMap); // На экране увидим:

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

Map linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put( «яблоко» , 1 );
linkedHashMap.put( «яблоко» , 2 );
linkedHashMap.put( «ананас» , 3 );
linkedHashMap.put( «банан» , 4 );
System.out.println(linkedHashMap); //

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

Map treeMap = new TreeMap<>();
treeMap.put( «яблоко» , 1 );
treeMap.put( «яблоко» , 2 );
treeMap.put( «ананас» , 3 );
treeMap.put( «банан» , 4 );
System.out.println(treeMap); //

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

Источник

Коллекции

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

Классы коллекций располагаются в пакете java.util , поэтому перед применением коллекций следует подключить данный пакет.

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

• Collection : базовый интерфейс для всех коллекций и других интерфейсов коллекций
• Queue : наследует интерфейс Collection и представляет функционал для структур данных в виде очереди
• Deque : наследует интерфейс Queue и представляет функционал для двунаправленных очередей
• List : наследует интерфейс Collection и представляет функциональность простых списков
• Set : также расширяет интерфейс Collection и используется для хранения множеств уникальных объектов
• SortedSet : расширяет интерфейс Set для создания сортированных коллекций
• NavigableSet : расширяет интерфейс SortedSet для создания коллекций, в которых можно осуществлять поиск по соответствию
• Map : предназначен для созданий структур данных в виде словаря, где каждый элемент имеет определенный ключ и значение. В отличие от других интерфейсов коллекций не наследуется от интерфейса Collection

Эти интерфейсы частично реализуются абстрактными классами:

• AbstractCollection : базовый абстрактный класс для других коллекций, который применяет интерфейс Collection
• AbstractList : расширяет класс AbstractCollection и применяет интерфейс List, предназначен для создания коллекций в виде списков
• AbstractSet : расширяет класс AbstractCollection и применяет интерфейс Set для создания коллекций в виде множеств
• AbstractQueue : расширяет класс AbstractCollection и применяет интерфейс Queue, предназначен для создания коллекций в виде очередей и стеков
• AbstractSequentialList : также расширяет класс AbstractList и реализует интерфейс List. Используется для создания связанных списков
• AbstractMap : применяет интерфейс Map, предназначен для создания наборов по типу словаря с объектами в виде пары «ключ-значение»

С помощью применения вышеописанных интерфейсов и абстрактных классов в Java реализуется широкая палитра классов коллекций — списки, множества, очереди, отображения и другие, среди которых можно выделить следующие:

• ArrayList : простой список объектов
• LinkedList : представляет связанный список
• ArrayDeque : класс двунаправленной очереди, в которой мы можем произвести вставку и удаление как в начале коллекции, так и в ее конце
• HashSet : набор объектов или хеш-множество, где каждый элемент имеет ключ — уникальный хеш-код
• TreeSet : набор отсортированных объектов в виде дерева
• LinkedHashSet : связанное хеш-множество
• PriorityQueue : очередь приоритетов
• HashMap : структура данных в виде словаря, в котором каждый объект имеет уникальный ключ и некоторое значение
• TreeMap : структура данных в виде дерева, где каждый элемент имеет уникальный ключ и некоторое значение

Схематично всю систему коллекций вкратце можно представить следующим образом:

Интерфейс Collection

Интерфейс Collection является базовым для всех коллекций, определяя основной функционал:

public interface Collection extends Iterable < // определения методов >

Интерфейс Collection является обобщенным и расширяет интерфейс Iterable, поэтому все объекты коллекций можно перебирать в цикле по типу for-each .

Среди методов интерфейса Collection можно выделить следующие:

• boolean add (E item) : добавляет в коллекцию объект item. При удачном добавлении возвращает true, при неудачном — false
• boolean addAll (Collection col) : добавляет в коллекцию все элементы из коллекции col. При удачном добавлении возвращает true, при неудачном — false
• void clear () : удаляет все элементы из коллекции
• boolean contains (Object item) : возвращает true, если объект item содержится в коллекции, иначе возвращает false
• boolean isEmpty () : возвращает true, если коллекция пуста, иначе возвращает false
• Iterator iterator () : возвращает объект Iterator для обхода элементов коллекции
• boolean remove (Object item) : возвращает true, если объект item удачно удален из коллекции, иначе возвращается false
• boolean removeAll (Collection col) : удаляет все объекты коллекции col из текущей коллекции. Если текущая коллекция изменилась, возвращает true, иначе возвращается false
• boolean retainAll (Collection col) : удаляет все объекты из текущей коллекции, кроме тех, которые содержатся в коллекции col. Если текущая коллекция после удаления изменилась, возвращает true, иначе возвращается false
• int size () : возвращает число элементов в коллекции
• Object[] toArray () : возвращает массив, содержащий все элементы коллекции

Все эти и остальные методы, которые имеются в интерфейсе Collection, реализуются всеми коллекциями, поэтому в целом общие принципы работы с коллекциями будут одни и те же. Единообразный интерфейс упрощает понимание и работу с различными типами коллекций. Так, добавление элемента будет производиться с помощью метода add , который принимает добавляемый элемент в качестве параметра. Для удаления вызывается метод remove() . Метод clear будет очищать коллекцию, а метод size возвращать количество элементов в коллекции.

Источник