Что такое коллекция в java

Коллекции в Java

В этом уроке мы рассмотрим коллекции, которые являются одной из важных частей Java Core.

Коллекции (Collection Framework) – это хранилища, поддерживающие различные способы накопления и упорядочения объектов с целью обеспечения возможностей эффективного доступа к ним. Они очень похожи на массивы, но имеют намного больше возможностей. Очень тяжело написать приложение на Java, которое может обойтись без коллекций.

Коллекции были добавлены в версии J2SЕ 1.2.

Collection framework в языке Java состоит из 3-х частей:

• интерфейсы,
• классы,
• алгоритмы.

Практически все коллекции и интерфейсы являются обобщенными. На этапе создания коллекции, вы скорее всего будете знать элементы какого типа вам нужны — String, Integer и т.д. Конечно же можно создать необобщенную коллекцию, но так делается крайне редко.

В этом уроке рассмотрим основные элементы коллекций, иерархия которых представлена на следующем рисунке:

Презентацию с видео можно скачать на Patreon .

1. Интерфейс Collection
2. Структуры данных
3. Интерфейс List и класс ArrayList
4. Интерфейс Set и классы HashSet, LinkedHashSet
5. Интерфейс SortedSet и класс TreeSet
6. Интерфейсы Comparable и Comparator
7. Интерфейс NavigableSet
8. Интерфейсы Queue и Deque
9. Класс ArrayDeque
10. Класс LinkedList
11. Класс PriorityQueue
12. Принцип PECS
13. Интерфейс Iterator
14. Интерфейс ListIterator
15. Отображения Map
16. Класс Collections
17. Backed Collections
18. Legacy Classes
19. Задания

Коллекции

Для хранения наборов данных в 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 возвращать количество элементов в коллекции.

Справочник по Java Collections Framework

Данная публикация не является полным разбором или анализом (не покрывает пакет java.util.concurrent ). Это, скорее, справочник, который поможет начинающим разработчикам понять ключевые отличия одних коллекций от других, а более опытным разработчикам просто освежить материал в памяти.

Что такое Java Collections Framework?

Java Collection Framework — иерархия интерфейсов и их реализаций, которая является частью JDK и позволяет разработчику пользоваться большим количесвом структур данных из «коробки».

Базовые понятия

На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: Collection и Map . Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» (словари).

Collection — этот интерфейс находится в составе JDK c версии 1.2 и определяет основные методы работы с простыми наборами элементов, которые будут общими для всех его реализаций (например size() , isEmpty() , add(E e) и др.). Интерфейс был слегка доработан с приходом дженериков в Java 1.5. Также, в версии Java 8, было добавлено несколько новых методов для работы с лямбдами (такие как stream() , parallelStream() , removeIf(Predicate filter) и др.).

Важно также отметить, что эти методы были реализованы непосредственно в интерфейсе как default -методы.

Map. Данный интерфейс также находится в составе JDK c версии 1.2 и предоставляет разработчику базовые методы для работы с данными вида «ключ — значение».Также как и Collection , он был дополнен дженериками в версии Java 1.5 и в версии Java 8 появились дополнительные методы для работы с лямбдами, а также методы, которые зачастую реализовались в логике приложения ( getOrDefault(Object key, V defaultValue) , putIfAbsent(K key, V value) ).

Интерфейс Map [doc]

Hashtable — реализация такой структуры данных, как хэш-таблица. Она не позволяет использовать null в качестве значения или ключа. Эта коллекция была реализована раньше, чем Java Collection Framework, но в последствии была включена в его состав. Как и другие коллекции из Java 1.0, Hashtable является синхронизированной (почти все методы помечены как synchronized ). Из-за этой особенности у неё имеются существенные проблемы с производительностью и, начиная с Java 1.2, в большинстве случаев рекомендуется использовать другие реализации интерфейса Map ввиду отсутствия у них синхронизации.

HashMap — коллекция является альтернативой Hashtable . Двумя основными отличиями от Hashtable являются то, что HashMap не синхронизирована и HashMap позволяет использовать null как в качестве ключа, так и значения. Так же как и Hashtable , данная коллекция не является упорядоченной: порядок хранения элементов зависит от хэш-функции. Добавление элемента выполняется за константное время O(1), но время удаления, получения зависит от распределения хэш-функции. В идеале является константным, но может быть и линейным O(n). Более подробную информацию о HashMap можно почитать здесь (актуально для Java < 8).

LinkedHashMap — это упорядоченная реализация хэш-таблицы. Здесь, в отличии от HashMap , порядок итерирования равен порядку добавления элементов. Данная особенность достигается благодаря двунаправленным связям между элементами (аналогично LinkedList ). Но это преимущество имеет также и недостаток — увеличение памяти, которое занимет коллекция. Более подробная информация изложена в этой статье.

TreeMap — реализация Map основанная на красно-чёрных деревьях. Как и LinkedHashMap является упорядоченной. По-умолчанию, коллекция сортируется по ключам с использованием принципа «natural ordering», но это поведение может быть настроено под конкретную задачу при помощи объекта Comparator , который указывается в качестве параметра при создании объекта TreeMap .

WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references. Другими словами, Garbage Collector автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элеметна нет жёстких ссылок.

Интерфейс List [doc]

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

Vector — реализация динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Vector появился в JDK версии Java 1.0, но как и Hashtable , эту коллекцию не рекомендуется использовать, если не требуется достижения потокобезопасности. Потому как в Vector , в отличии от других реализаций List , все операции с данными являются синхронизированными. В качестве альтернативы часто применяется аналог — ArrayList .

Stack — данная коллекция является расширением коллекции Vector . Была добавлена в Java 1.0 как реализация стека LIFO (last-in-first-out). Является частично синхронизированной коллекцией (кроме метода добавления push() ). После добавления в Java 1.6 интерфейса Deque , рекомендуется использовать именно реализации этого интерфейса, например ArrayDeque .

ArrayList — как и Vector является реализацией динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Как можно догадаться из названия, его реализация основана на обычном массиве. Данную реализацию следует применять, если в процессе работы с коллекцией предплагается частое обращение к элементам по индексу. Из-за особенностей реализации поиндексное обращение к элементам выполняется за константное время O(1). Но данную коллекцию рекомендуется избегать, если требуется частое удаление/добавление элементов в середину коллекции. Подробный анализ и описание можно почитать в этом хабратопике.

LinkedList — ещё одна реализация List . Позволяет хранить любые данные, включая null . Особенностью реализации данной коллекции является то, что в её основе лежит двунаправленный связный список (каждый элемент имеет ссылку на предыдущий и следующий). Благодаря этому, добавление и удаление из середины, доступ по индексу, значению происходит за линейное время O(n), а из начала и конца за константное O(1). Так же, ввиду реализации, данную коллекцию можно использовать как стек или очередь. Для этого в ней реализованы соответствующие методы. На Хабре также есть статья с подробным анализом и описанием этой коллекции.

Интерфейс Set [doc]

Представляет собой неупорядоченную коллекцию, которая не может содержать дублирующиеся данные. Является программной моделью математического понятия «множество».

HashSet — реализация интерфейса Set , базирующаяся на HashMap . Внутри использует объект HashMap для хранения данных. В качестве ключа используется добавляемый элемент, а в качестве значения — объект-пустышка (new Object()). Из-за особенностей реализации порядок элементов не гарантируется при добавлении.

LinkedHashSet — отличается от HashSet только тем, что в основе лежит LinkedHashMap вместо HashMap . Благодаря этому отличию порядок элементов при обходе коллекции является идентичным порядку добавления элементов.

TreeSet — аналогично другим классам-реализациям интерфейса Set содержит в себе объект NavigableMap , что и обуславливает его поведение. Предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator , либо сохраняет элементы с использованием «natural ordering».

Интерфейс Queue [doc]

Этот интерфейс описывает коллекции с предопределённым способом вставки и извлечения элементов, а именно — очереди FIFO (first-in-first-out). Помимо методов, определённых в интерфейсе Collection, определяет дополнительные методы для извлечения и добавления элементов в очередь. Большинство реализаций данного интерфейса находится в пакете java.util.concurrent и подробно рассматриваются в данном обзоре.

PriorityQueue — является единственной прямой реализацией интерфейса Queue (была добавлена, как и интерфейс Queue, в Java 1.5), не считая класса LinkedList , который так же реализует этот интерфейс, но был реализован намного раньше. Особенностью данной очереди является возможность управления порядком элементов. По-умолчанию, элементы сортируются с использованием «natural ordering», но это поведение может быть переопределено при помощи объекта Comparator , который задаётся при создании очереди. Данная коллекция не поддерживает null в качестве элементов.

ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out). Интерфейс Deque и реализация ArrayDeque были добавлены в Java 1.6. Эта коллекция представляет собой реализацию с использованием массивов, подобно ArrayList , но не позволяет обращаться к элементам по индексу и хранение null . Как заявлено в документации, коллекция работает быстрее чем Stack , если используется как LIFO коллекция, а также быстрее чем LinkedList, если используется как FIFO.

Заключение

Java Collections Framework содержит большое количество различных структур данных, доступных в JDK «из коробки», которые в большинстве случаев покрывают все потребности при реализации логики приложения. Сравнение временных характеристик основных коллекций, которые зачастую используются в разработке приложений приведено в таблице:

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

В дополнение, хотелось бы указать в качестве дополнительного материала, ссылку на обзор пакета java.util.concurrent . Который является отличным дополнением к изложенному материалу.

Интерфейсы и коллекции в Java

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

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

Коллекция – это…

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

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

Суть гибких по размеру наборов элементов заключается в том, что классы в коллекции отвечают за реализацию различных алгоритмов и структур информации:

• множество;
• дерево;
• очередь и так далее.

The collections образовывают логичную структуру. В основе каждого такого компонента языка заложено использование того или иного интерфейса. Соответствующий элемент отвечает за определение базового функционала in the collection.

Инструменты для работы с the collection собраны в Java Collection Framework (JCF). Далее предстоит изучить этот фреймворк более подробно. Особое внимание необходимо уделить set, который позволяет использовать «неупорядоченное множество».

Выше представлена структура имеющихся the collections в Java. Каждый элемент здесь имеет собственную область применения и особенности.

Кратко о каждом

Изучая interface set, необходимо рассмотреть и другие компоненты JCF. Соответствующий фреймворк включает в себя:

1. The List – неупорядоченный список. В ней у каждого компонента имеется индекс. Дубликаты значений поддерживаются системой.
2. The Queue. Такое название получила очередь. Соответствующий список поддерживает добавление компонентов только in the end (в конец). Удаление составляющих происходит исключительно спереди. Здесь реализуется правило «Первым пришел – первым ушел».
3. The Deque. Это очередь и стек. Компоненты здесь можно добавлять как в начало, так и в конец. Аналогично ситуация обстоит с удалением.
4. The Map. Пары «ключ–значение». Ключи of code уникальны. Параметры могут повторяться. В map порядок компонентов не гарантируется. Используется такая коллекция для поиска объектов по ключу.
5. Set in Java. Коллекция, которая включает в себя (contains) неупорядоченное множество компонентов. Здесь один и тот же объект не может встречаться более одного раза. Это стандартный интерфейс, а также подтип Collection.

Далее Set будет изучен более подробно. Связано это с тем, что set interface используются в разработке очень часто.

Понятие множества

Множество – способ хранения данных. Он напоминает массив и списки. Ключевое особенностью множества является то, что оно включает в себя только уникальные значения. Именно так работает sets.

Выше – множество set, которое состоит из int. Оно включает в себя 5 компонентов. Добавить туда единицу не получится. Это связано с тем, что int = 1 уже имеется в заданном «перечне».

Set interfaces обеспечивают уникальность of the elements. Дублирующие записи в соответствующих множествах исключены.

Виды

Java new set – это интерфейс. Он поддерживает несколько реализации in the programming language:

Основных видов set три:

• HashSet;
• LinkedHashSet;
• TreeSet.

Остальные множества специалистам требуются на практике редко, поэтому они изучены далее не будут.

HashSet

Interface in set часто использует класс HashSet. Он применяется для хранения информации в хеш-таблице. Так называется структура информации (structure of information), в которой все элементы (the elements) помещаются в бакеты (buckets). Они соответствуют результатам вычисления of хеш-функции.

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

В предложенном примере заданный алгоритм расчетов – это и есть хеш-функция. Результат вычисления – это хеш-код.

В описанном примере ключ от номера 356 попадет в коробку с номером 5. В случае с комнатой 123 – в ящик с подписью 6.

Выше – наглядный пример java set of the code. Данный алгоритм применим к расчетам в случае с использованием HashSet. Аналогичным образом можно получить и другие значения.

В new HashSet string добавление (add), поиск (search), а также удаление (remove) элементов происходит за постоянное время. Количество of the element в коллекции не имеет никакого значения.

Такой метод организации позволяет хранить компоненты в произвольном порядке. Он быстро справляется с поиском. Использовать такой set interface необходимо тогда, когда порядок не имеет никакого значения, а на первое место выходит скорость. Для оптимизации поиска метод (method) HashSet хранит компоненты так, как ему удобно.

LikesHashSet и TreeSet

Второй вариант set interface – это LikesHashSet. Данный метод позволяет организовать хранение так, как изначально был добавлен элемент в множество. Он работает чуть медленнее, чем HashSet, зато является более систематизированным.

TreeSet встречается реже. Он позволяет хранить компоненты в отсортированном виде. Способ «классификации» (то, в какой форме получать и сохранять данные) разработчик определяет самостоятельно. По умолчанию при использовании The TreeSet применяется организация в естественном порядке – в форме красно-черного дерева.

Сравнение Set со списками

Set Interface и List похожи друг на друга. Соответствующие коллекции выступают в качестве некоторого набора компонентов. Они отличаются друг от друга. Ключевая разница – методы (the methods), которые содержат the Set и the List in the programming languages:

1. В Set e новые (new) элементы не могут быть добавлены, если они уже имеются в пределах заданного множества. В списках соответствующий принцип не работает. В таких коллекциях int (integer), str (strings) и void могут встречаться более одного раза.
2. Второй момент, на который необходимо обратить внимание – это гарантированность внутреннего порядка. Получить 100% упорядоченный «перечень» позволяет только список. Компоненты в List могут повторяться согласно установленному внутреннему порядку.

В остальном the List и the Set похожи друг на друга.

Реализации

The Set – это интерфейс. Для использования соответствующего компонента потребуется выбрать реализацию:

• java.util.enumset;
• java util set (hashset);
• jawakutilklaidakes ashset;
• util.treeset.

Каждая предложенная реализация Set ведет себя по-разному относительно порядка расположения элементов при итерации набора и времени, необходимого для вставки и доступа к компонентам в наборах.

HashSet поддерживается HashMap. Он не поддерживает никаких гарантий относительно последовательностей элементов в процессе итерации (iterator string).

LinkedHashSet в отличие от HashSet one отличается тем, что он гарантирует сохранение порядка элементов во время итерации. Он будет совпадать с их вставкой в коллекции. При повторной вставке элемента, который уже имеется в LinkedHashSet порядок не поменяется.

Tree Set int Java тоже гарантирует получение массива в определенном порядке при повторении. Таковым является порядок сортировки. Речь идет о порядке, в котором компоненты должны быть отсортированы при использовании Collections.sort для List или массива, содержащего соответствующие элементы. Порядок будет определяться либо естественным расположением (при реализации Comparable), либо конкретной реализацией Comparator.

Методы и примеры

Далее будут рассмотрены ключевые методы в set string java. К ним относят:

• add – добавление компонента;
• remove – удаление;
• size – возврат размера множества;
• contains – определение факта нахождения составляющего в множестве;
• clear – удаление всех компонентов из коллекции;
• isEmpty – возвращает значение true, если множество пустое.

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

Добавление в набор

The set поддерживает метод add. С его помощью удается добавлять новые составляющие во множество. Он унаследован непосредственно от интерфейса Collection:

Выше – три вызова упомянутого метода. Они добавляют экземпляр к String-набору.

Перебор

Перебор составляющих в the set может осуществляться несколькими способами:

• через цикл for–each;
• при помощи итератора, который будет получен непосредственно из the set.

При обработки итерации компонентов в the Set порядок составляющих зависит от того, какая именно реализация была использована.

Через итератор

Для выполнения итерации компонентов через итератор, потребуется сначала получить его из имеющегося набора. Для этого применяется метод iterator:

Выше – наглядный пример кода, который поможет добиться желаемого результата.

Использование цикла

Перебор может быть реализован через цикл for–each:

Set Interface будет реализовывать Iterable. Из-за этого можно перебирать компоненты набора через for–each.

Установка размера через Size

Метод size используется для того, чтобы разработчик смог установить размер набора. В качестве соответствующего параметра выступает количество компонентов, включенных во множество:

После обработки соответствующего запроса переменная, отвечающая за размер, будет иметь значение, равное 3. Результатом обработки фрагмента кода является массив с тремя добавленными компонентами.

Проверка на пустоту

Чтобы проверить множество на пустоту, достаточно использовать метод isEmpty:

После его реализации переменная isEmpty получит значение, равное «Истина». Связано это с тем, что новый the Set является пустым: в нем отсутствуют составляющие.

Еще один вариант проверки на пустоту:

Для реализации команды используется сравнение значения, возвращаемого методом size() с нулем. Как только код обработается, переменная isEmpty получит значение true. Это связано с тем, что метод set size возвращает 0.

Содержание компонента

А вот фрагмент кода, который помогает выяснить, содержится ли заданное значение (объект) во множестве:

Для определения набора на факт содержания того или иного объекта требуется внутреннее выполнение итерации компонентов множества с каждым элементов, передаваемым в качестве параметра. Сравнение реализовывается при помощи метода равенства.