Коллекцию можно создать двумя способами через конструктор collection или через метод collection from

Коллекции

Типы коллекций. Интерфейс Collection

Для хранения наборов данных в 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 является базовым для всех коллекций, определяя основной функционал:

Интерфейс 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 возвращать количество элементов в коллекции.

Источник

Коллекции (Collections) в Java. Введение

Эта статья является первой из серии статей о коллекциях в Java. В будущих статьях будет рассмотрены основные классы-коллекции, появившиеся в Java 1.5. Будут рассмотрены классы, унаследованные от Set, List, Queue и Map: ArrayList, HashSet, EnumSet, LinkedHashSet, LinkedList, PriorityQueue, TreeSet, HashMap, LinkedHashMap, TreeMap и другие.

Немного истории

До появления версии 1.5 в Java были только 3 типа коллекций: массивы, Vector (и унаследованный от него Stack) и Hashtable.

До Java 1.4 включительно Vector представлял собой очередь, в которую можно было добавлять объект любого класса. Он представлял простой способ работы с цепочкой элементов. Так как типизированные коллекции появились только в 5-й версии Java, то программисты нередко использовали Vector для хранения объектов разных классов из-за простоты использования. Конечно, и в 5-й версии Java, можно создать любую коллекцию, которая будет хранить объекты класса java.lang.Object, но это делать строго не рекоммендуется. В Java 1.5 Vector стал типизированным как и остальные классы коллекций.

Hashtable — коллекция, позволяющая хранить данные в виде ключ-значение. Иногда Hashtable сравнивают (и приравнивают) с ассоциативными массивами из других языков программирования. Ключ и значение могут быть любым объектом, но не примитивом. Также, ключ в Hashtable не может быть null.

До Java 1.4 в Vector и Hashtable нельзя было добавлять примитивные типы, такие как: int, float, long, double. Для создания списка примитивных объектов необходимо было использовать оболочки для примитивных типов: Integer, Float, Long, Double. С выходом Java версии 1.5, в Vector и Hashtable можно добавлять примитивные типы. Они будут автоматически преобразованы в свои обертки.

Vector и Hashtable были и остаются синхронизированными из-за чего операции с ними занимают больше времени, чем с аналогичными классами List и Map. Vector и Hashtable — устаревшие классы, которые не рекоммендуется использовать.

Коллекции в Java 1.5

Перейдем непосредственно к коллекциям, которые появились в Java 1.5. Все коллекции унаследованы от одного интерфейса Collection из пакета java.util. Интерфейс Collection, в свою очередь, реализует интерфейс Iterable. Это означает, что все классы, унаследованные от Collection могут использоваться в цикле foreach. Например так:

Учтите, что удаление элементов из коллекции в цикле foreach небезопасно. Для этих целей используйте итератор, например так:

Иерархия интерфейсов, унаследованных от Collection представлена на Рис.1. Как можно заметить, отсутствует интерфейс Map — он не унаследован от Collection и о нём разговор будет отдельный.

Рис 1. Коллекции (Collections) в Java

Стоит заметить, что в Java нет ни одного класса, который напрямую реализует интерфейс Collection. Это происходит через промежуточные интерфейсы List, Set и Queue.

Общепринятые правила использования Collection

1. Всегда корректно описывайте методы equals() и hashCode() в объектах, которые будут добавлены в коллекцию. Например, для того, чтобы метод contains(Object o) вернул корректное значение, необходимо чтобы выполнялось следующее условие: (o==null ? e==null : o.equals(e)). Метод hashCode() гарантирует, что два объекта с разными значениями hashCode() не могут быть равны. Также метод hashCode() может использоваться коллекцией для наиболее эффективного размещения объектов в памяти. Это правило не касается стандартных типов вроде String, Integer, Float и т.д. так как в этих классах уже реализованы оба метода.

2. Каждый класс, реализующий интерфейс Collection, имеет как минимум два конструктора: конструктор по умолчанию и конструктор, принимающий коллекцию (объект Collection ). Это правило ложиться на плечи разработчика так как у интерфейсов не может быть конструкторов. Пример:

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

Источник

Работа с коллекциями на Java

Интерфейс Java Collection(java.util.Collection) является одним из корневых интерфейсов API Java Collection. Хотя не создаете экземпляр Collection напрямую, а скорее подтип Collection, вы часто можете рассматривать эти подтипы единообразно, как Collection. В этом тексте вы увидите как.

Создание

Вы не создаете экземпляр Collection напрямую, но экземпляр одного из подтипов Collection. Вот пример создания List, который является подтипом Collection:

Приведенный выше пример работает для каждого подтипа коллекции.

Подтипы

Следующие интерфейсы (типы коллекций) расширяют интерфейс Java Collection:

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

Пример стандартного наследования, так что в этом нет ничего волшебного, но время от времени может быть хорошей особенностью.

Вот метод, который работает с коллекцией:

И вот несколько способов вызвать этот метод с разными подтипами Collection:

Как добавить элемент

Независимо от того, какой подтип вы используете, существует несколько стандартных методов для добавления элементов в коллекцию. Осуществляется это с помощью метода add():

Метод add() добавляет данный элемент в коллекцию и возвращает true, если коллекция изменилась в результате вызова метода. Может и не измениться. Если набор уже содержал этот элемент, он больше не добавляется. С другой стороны, если бы вы вызвали add() для List, и список уже содержал этот элемент, в итоге элемент дважды существовал бы в List.

Как удалить элемент

Метод remove() удаляет элемент из коллекции и возвращает значение true, если удаленный элемент присутствовал в коллекции и был удален. Если отсутствует, метод возвращает false. Вот пример удаления:

Как добавить коллекцию объектов

Для этого используйте addAll():

Java Collection addAll() добавляет все элементы, найденные в Collection, переданные в качестве параметра в метод. Сам объект не добавляется, только его элементы. Если бы вы вызвали add() с Collection в качестве параметра, был бы добавлен сам объект, а не его элементы.

Как именно ведет себя метод addAll(), зависит от подтипа Collection. Некоторые подтипы позволяют добавлять один и тот же элемент более одного раза, а другие – нет.

Как удалить коллекцию элементов

Java Collection removeAll() удаляет все найденные элементы, переданные Collection в качестве параметра методу. Если параметр содержит какие-либо элементы, не найденные в целевой коллекции, они просто игнорируются. Вот пример удаления:

Как сохранить все элементы из коллекции в другой

Коллекция Java retainAll() является противоположностью removeAll(). Вместо удаления всех элементов, найденных в параметре Collection, он сохраняет их и удаляет все остальные.

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

Проверка, содержится ли определенный элемент

Интерфейс Collection имеет два метода, чтобы проверить, содержит ли Collection один или несколько определенных элементов. Это методы contains() и containsAll(). Они проиллюстрированы здесь:

• contains() возвращает true, если содержится элемент, и false, если нет;
• containsAll() возвращает true, если содержатся все элементы в коллекции параметров, и false, если нет.

Размер

Вы можете проверить размер коллекции, используя метод size(). Под «размером» подразумевается количество элементов. Вот пример:

Итерация

Вы можете перебрать все элементы коллекции. Это делается путем получения Java Iterator из коллекции и повторения этого. Вот как это выглядит:

Вы также можете выполнить итерацию Java Collection с помощью цикла for-each:

Источник

Богдан Стефанюк

В C# для хранения набора однотипных данных можно использовать массивы. Но с ними не всегда удобно работать потому, что они имеют фиксированный размер и часто бывает сложно угадать, какого размера нужен массив.

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

Все коллекции лежат в нескольких пространствах имен:

• System.Collections — простые необобщенные коллекции.
• System.Collections.Generic — обобщенные коллекции.
• System.Collections.Specialized — специальные коллекции.
• System.Collections.Concurrent — коллекции для работы в многопоточной среде.

Устройство коллекций

Все коллекции, так или иначе, реализую интерфейс ICollection, некоторые реализуют интерфейсы IList и IDictionary (которые внутри наследуют ICollection). Этот интерфейс предоставляет минимальный набор методов, которые позволяют реализовать коллекцию.

В свою очередь, ICollection расширяет интерфейс IEnumerable. Он предоставляет нумератор, который позволяет обходить коллекции элемент за элементом. Именно этот интерфейс позволяет использовать коллекции в цикле foreach.

Вместительность коллекций

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

После активного наполнения коллекции наступает момент, когда внутренний массив заполнен и мы не можем добавить новый элемент. В таком случае коллекция создаёт новый массив с большей вместительностью (обычно в два раза больше) и копирует туда данные со старого массива.

Поэтому коллекции, которые основаны на массивах имеют сложность вставки:

• O(1) — когда вместительности достаточно.
• O(n) — когда вместительности недостаточно и нужно копировать данные в массив побольше.

Чтобы избежать уменьшения производительности нужно при создании коллекции указать необходимую нам вместительности. Это позволит уменьшить количество копирований.

Сравнивание и сортировка элементов коллекций

Сравнение
Такие методы как Contains, IndexOf, LastIndexOf, and Remove используют сравнение элементов для свое работы. Если коллекция является обобщенной, то используются два механизма сравнения:

• Если тип реализует интерфейс IEquatable тогда механизм сравнения использует метод Equals этого интерфейса.
• Если тип не реализует интерфейс IEquatable тогда для сравнения используется Object.Equals

Некоторые коллекции имеют конструктор, который принимает имплементацию IEqualityComparer который используется для сравнения.

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

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

Явная сортировка подразумевает, что наши элементы не реализуют интерфейс IComparable, поэтому в качестве параметра метода сортировки нужно передать объект, который реализует интерфейс IComparer.

Если тип не реализует интерфейс IComparable и мы не передали явно тип, который реализует IComparer, то при вызове метода сортировки вылетит исключение.

Алгоритмическая сложность коллекций

Список List

Класс List представляет из себя простейший список однотипных элементов, которые можно получить по индексу. Предоставляет методы для поиска, сортировки и изменения списка.

Для своей работы списки используют обычные массивы. Это значит что могут быть проблемы с производительностью из-за частого создания нового массива. Также у списков есть еще два нюанса:

• Вставка элемента в середину списка приведет к созданию нового массива и копирование данных, что негативно влияет на производительность.
• Списки не могут хранить экстремально огромное количество элементов из-за фрагментации адресного пространства.

Если эти проблемы существенны для вас, то стоит присмотреться к LinkedList или ImmutableList

Связанный список LinkedList

Класс LinkedList реализует простой двухсвязный список, каждый элемент которого имеет ссылка на предыдущий и следующий элемент.

Каждый элемент списка оборачивается в специальный класс LinkedListNode , который имеет ссылку на следующий элемент (Next), на предыдущий элемент (Previous) и само значение (Value).

Связанный список позволяет вставлять и удалять элементы со сложностью O (1). Также мы можем удалить элемент и заново вставить в тот же или другой список без дополнительного выделения памяти.

Словарь Dictionary

Словари хранят данные в виде ключ-значение. Каждый элемент словаря представляет из себя объект структуры KeyValuePair .

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

Внутри словари построены на базе хеш-таблицы, что позволяет очень быстро вставлять элементы и получать по ключу (сложность O (1)). Сами же хеш-таблицы, в свою очередь, реализованы с помощью массивов.

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

Стек Stack и Очередь Queue

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

Стеки Stack — реализуют подход LIFO (last in — first out).

Очереди Queue — реализуют подход (first in — first out).

Внутри они реализованы с помощью обычных массивов.

Множества HashSet и SortedSet

Эти классы реализуют математические множества. По своей природе множество — набор уникальных элементов с общими характеристиками, в нашем случае одного типа.

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

Внутренняя реализация этих классов отличается:

• HashSet — множество, построенное на базе хеш-таблицы.
• SortedSet — отсортированное множество, построенное на базе красно-черного дерева.

Можно заметить что LINQ предоставляет несколько похожих операций (Distinct, Union, Intersect, Except), которые можно выполнить с любой коллекцией. Но HastSet предоставляет намного больший набор операций с множествами.

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

KeyedCollection

KeyedCollection это абстрактный класс, который позволяет построить собственную коллекцию.

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

В отличие от словарей, элемент KeyedCollection коллекции не является парой ключ-значение, вместо этого весь элемент является значением, а в качестве ключа используется его поле, свойство или любое другое значение. Для получения ключа используется абстрактный метод, который является обязательным для реализации. GetKeyForItem

Внутри KeyedCollection построен на базе двух структур данных. Для быстрого получения данных по ключу используется словарь, а для получение элемента по индексу используется массив.

NameValueCollection

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

Особенной эту коллекцию делает то что однин ключ может содержать несколько эллементов.

Иммутабельные коллекции

Иммутабельные коллекции не входят в стандартную библиотеку классов (BCL). Для их использования нужно установить System.Collections.Immutable NuGet пакет.

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

Сами же коллекции можно поделить на несколько видов:

• Mutable — обычные коллекции которые поддерживают изменения.
• Immutable — коллекции, которые полностью запрещают изменения. Хотя на самом деле любое изменение иммутабельной коллекции приводит к созданию новой.
• ReadOnly — обертки над стандартными коллекциями, которые не дают поменять данные. Из-за того что это всего лишь обертка мы можем поменять данные в оригинальной коллекции и ead only коллекция подтянет изменения.

Иммутабельные стеки ImmutableStack и очереди ImmutableQueue

Ничем не отличаются от обычных стеков и очередей, кроме того, что являются не изменяемыми.

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

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

Иммутабельные списки ImmutableList

Под капотом используют сбалансированное бинарное дерево вместо массива или связанного списка.

Массивы не подходят из-за накладных расходов на их использование. Связанный список тоже не подойдет, потому что ImmutableList поддерживает обращение по индексу из-за чего нужно долго перебирать связанные элементы. Поэтому для нормальной работы иммутабельных списков используют сбалансированное бинарное дерево.

Иммутабельные массивы ImmutableArray

По сути, это небольшая прослойка над обычными массивами и все. Любые мутабельные операции приводят к копированию массива. Из-за этого скорость добавления элементов равна O (n), но в то же время получение элемента по индексу занимает O (1).

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

Иммутабельные словари ImmutableDictionary

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

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

Особенности использования

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

По идее чтобы было проще, мы можем объединить все изменения в цепочку:

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

Чтобы минимизировать проблему стоит использовать методы, которые могут выполнить нужные изменения за один вызов. Например:

Но такие методы позволяют сделать только один вид изменения. Например у нас нет единого метода, который позволяет добавить и удалить одну запись:

Для решения этой проблемы иммутабельные коллекции предоставляют билдеры (builders).

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

Источник