виды коллекций java перечисляете все что знаете
Коллекции в Java
Алгоритмы + Структуры данных = Программы.
Никлаус Вирт.
Введение
При написании программы очень часто возникает потребность хранить набор каких-либо объектов. Это могут быть числа, строки, объекты пользовательских классов и т.п. В данной статье я постараюсь классифицировать и описать основные классы коллекций простым языком.
Как видим, выбрать есть из чего. Но для начала необходимо освоить базовые коллекции Java которыми пользуются чаще всего. А так же некоторые сторонние библиотеки реализуют интерфейсы Java Collections Framework (пример Guava http://guava-libraries.googlecode.com/svn/tags/release05/javadoc/overview-tree.html). То есть знание иерархии классов базовых коллекций позволит более быстро освоить сторонние библиотеки.
Базовые интерфейсы
В библиотеке коллекций Java существует два базовых интерфейса, реализации которых и представляют совокупность всех классов коллекций:
Интерфейс Collection
Давайте рассмотрим основные интерфейсы, относящиеся к Collection:
Как видно с диаграммы, интерфейс Collection не является базовым (какая интрига :D). Интерфейс Collection расширяет интерфейс Iterable, у которого есть только один метод iterator(). Это значит что любая коллекция, которая есть наследником Iterable должна возвращать итератор.
Реализации интерфейса List
Сразу смотрим на иерархию классов.
Как видим на рисунке, между интерфейсом и конкретной реализацией коллекции существует несколько абстрактных классов. Это сделано для того, что бы вынести общий функционал в абстрактный класс, таким образом реализовать повторное использование кода.
Часто на собеседованиях спрашивают про отличия ArrayList и LinkedList. И какой когда нужно использовать. См. вопрос собеседования: http://www.quizful.net/interview/java/54AubfnDy6Ti
Реализации интерфейса Set
Смотрим следующую диаграмму. Пытаемся вникнуть 🙂
Если Вы хотите использовать HashSet для хранения объектов СВОИХ классов, то вы ДОЛЖНЫ переопределить методы hashCode() и equals(), иначе два логически-одинаковых объекта будут считаться разными, так как при добавлении элемента в коллекцию будет вызываться метод hashCode() класса Object (который скорее-всего вернет разный хэш-код для ваших объектов).
Важно отметить, что класс HashSet не гарантирует упорядоченности элементов, поскольку процесс хеширования сам по себе обычно не порождает сортированных наборов. Если вам нужны сортированные наборы, то лучшим выбором может быть другой тип коллекций, такой как класс TreeSet.
Реализации интерфейса Queue
Здесь я привел очень упрощенную иерархию.
Реализации интерфейса Map
Интерфейс Map соотносит уникальные ключи со значениями. Ключ — это объект, который вы используете для последующего извлечения данных. Задавая ключ и значение, вы можете помещать значения в объект карты. После того как это значение сохранено, вы можете получить его по ключу. Интерфейс Map — это обобщенный интерфейс, объявленный так, как показано ниже.
Здесь К указывает тип ключей, а V — тип хранимых значений.
Иерархия классов очень похожа на иерархию Set’а:
HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Хорошая статья http://habrahabr.ru/post/128017/
Устаревшие коллекции
Следующие коллекции являются устаревшими, и их использование не рекомендуется, но не запрещается.
1. Enumeration — аналог интерфейса Iterator.
2. Vector — аналог класса ArrayList; поддерживает упорядоченный список элементов, хранимых во «внутреннем» массиве.
3. Stack — класс, производный от Vector, в который добавлены методы вталкивания (push) и выталкивания (pop) элементов, так что список может трактоваться в терминах, принятых для описания структуры данных стека (stack).
4. Dictionary — аналог интерфейса Map, хотя представляет собой абстрактный класс, а не интерфейс.
5. Hashtable — аналог HashMap.
Все методы Hashtable, Stack, Vector являются синхронизированными, что делает их менее эффективными в одно поточных приложениях.
Синхронизированные коллекции
Получить синхронизированные объекты коллекций можно с помощью статических методов synchronizedMap и synchronizedList класса Collections.
Map m = Collections.synchronizedMap(new HashMap());
List l = Collections.synchronizedList(new ArrayList());
Кроме того всегда существует возможность «классической» синхронизации с помощью блока synchronized.
Собираем все воедино
Итак, смотрим на получившейся диаграмму классов:
Как видим диаграмма достаточно массивная. Но такая архитектура считается эталонной в OOП.
Заключение
Если Вам понравилась статья, проголосуйте за нее
Голосов: 187 Голосовать 
Коллекции в Java
2020.06.08 (Последнее изменение: 2021.11.18)
Общее описание
Интерфейсы коллекций
Иерархия интерфейсов коллекций 
| Интерфейс | Описание |
|---|---|
| Itarable | Реализация данного интерфейса позволяет объекту использоваться в цикле “for-each” |
| Collection | Корневой интерфейс в иерархии коллекций. |
| List | Упорядоченная коллекция (также известная как последовательность). |
| Set | Коллекция (набор/множество), которая не содержит повторяющихся элементов. |
| SortedSet | Интерфейс Set, который дополнительно обеспечивает упорядочение по его элементам. |
| NavigableSet | Интерфейс SortedSet расширенный с помощью методов навигации, обеспечивающих поиск ближайших совпадений искомых элементов. |
| Queue | Очередь, предназначенна для хранения элементов перед обработкой. |
| Deque | Линейная коллекция, которая поддерживает вставку и удаление элементов на обоих концах. |
| Map | Отображение. Объект, который сопоставляет ключи со значениями. |
| SortedMap | Отображение, которое дополнительно обеспечивает упорядочивание по ключам. |
| NavigableMap | Интерфейс SortedMap расширенный с помощью методов навигации, обеспечивающих поиск ближайших совпадений искомых элементов. |
| Iterator | Итератор по коллекции. |
| ListIterator | Итератор для списков, который позволяет программисту перемещаться по списку в любом направлении, изменять список во время итерации и получать текущее положение итератора в списке. |
| RandomAccess | Маркерный интерфейс, используемый реализациями списков для указания на то, что они поддерживают быстрый (обычно постоянный по времени) произвольный доступ. |
| Интерфейс | Описание |
|---|---|
| Cloneable | Позволяет классам, реализующим интерфейс, сделать копию экземпляра класса. |
| Serializable | Интерфейс позволяет классу быть сериализованным, это означает что объект класса может быть преобразован в последовательность бит или байт для передачи по сети. |
Интерфейс Map
Отображение. Структура данных для хранения связанных вместе пар “ключ-значение”.
public interface Map
Вложенные классы
| Класс | Описание |
|---|---|
| static interface Map.Entry | Запись отображения (пара ключ-значение отображения). Получается с помощью метода Map.entrySet() |
| Метод | Описание |
|---|---|
| K getKey() | Возвращает ключ соответствующий данной записи. |
| V getValue() | Возвращает значение соответствующее данной записи. |
| V setValue(V value) | Заменяет значение соответствующее этой записи на указанное значение (опциональная операция). |
Методы
Наиболее общие реализации сведены в следующей таблице:
| Interface | Hash Table | Resizable Array | Balanced Tree | Linked List | Hash Table + Linked List |
|---|---|---|---|---|---|
| Set | HashSet | TreeSet | LinkedHashSet | ||
| List | ArrayList | LinkedList | |||
| Deque | ArrayDeque | LinkedList | |||
| Map | HashMap | TreeMap | LinkedHashMap |
Свойства коллекций
Временная сложность
| Среднее | Индекс | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| ArrayList | O(1) | O(n) | O(n) | O(n) |
| Vector | O(1) | O(n) | O(n) | O(n) |
| LinkedList | O(n) | O(n) | O(1) | O(1) |
| Hashtable | n/a | O(1) | O(1) | O(1) |
| HashMap | n/a | O(1) | O(1) | O(1) |
| LinkedHashMap | n/a | O(1) | O(1) | O(1) |
| TreeMap | n/a | O(log(n)) | O(log(n)) | O(log(n)) |
| HashSet | n/a | O(1) | O(1) | O(1) |
| LinkedHashSet | n/a | O(1) | O(1) | O(1) |
| TreeSet | n/a | O(log(n)) | O(log(n)) | O(log(n)) |
| Худшее | Индекс | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| ArrayList | O(1) | O(n) | O(n) | O(n) |
| Vector | O(1) | O(n) | O(n) | O(n) |
| LinkedList | O(n) | O(n) | O(1) | O(1) |
| Hashtable | n/a | O(n) | O(n) | O(n) |
| HashMap | n/a | O(n) | O(n) | O(n) |
| LinkedHashMap | n/a | O(n) | O(n) | O(n) |
| TreeMap | n/a | O(log(n)) | O(log(n)) | O(log(n)) |
| HashSet | n/a | O(n) | O(n) | O(n) |
| LinkedHashSet | n/a | O(n) | O(n) | O(n) |
| TreeSet | n/a | O(log(n)) | O(log(n)) | O(log(n)) |
ArrayList
Является реализацией динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Реализация основана на обычном массиве.
Следует применять, если в процессе работы с коллекцией предполагается частое обращение к элементам по индексу.
Не рекомендуется применять, если требуется частое удаление/добавление элементов в середину коллекции.
Пример использования ArrayList
Ссылки
LinkedList
Пример использования LinkedList
Ссылки:
HashSet
Пример использования хэш-множества HashSet
Ссылки:
TreeSet
Древовидное множество. Хранит отсортированную коллекцию в виде структуры красно-черного дерева.
Пример использования TreeSet
Ссылки:
EnumSet
Специализированное множество используется с типами enum (перечислениями).
Для реализации использует битовую последовательность. В каждом бите устанавливается 1, если соответствующее значение перечисления присутствует в множестве. Все методы в EnumSet реализованы с использованием арифметических побитовых операций. Эти вычисления очень быстрые, и поэтому все основные операции выполняются за постоянное время. Если сравнивать EnumSet с другими реализациями Set то он обычно быстрее, потому что значения хранятся в предсказуемом порядке, и для каждого вычисления необходимо проверять только один бит. В отличие от HashSet, нет необходимости вычислять hashcode, чтобы найти правильный сегмент. EnumSet очень компактен и эффективен. Следовательно, использует меньше памяти.
EnumSet следует использовать, когда мы храним значения enum в множестве.
Пример использования EnumSet
Ссылки:
LinkedHashSet
Множество сохраняющее значения в хэш таблицу в виде связанного списка с сохранением порядка ввода.
Сравнение LinkedHashSet и HashSet
Сравнение LinkedHashSet и TreeSet
Ссылки:
ArrayDeque
Двусторонняя очередь. Массив с изменяющимся размером, реализующий интерфейс Deque.
Сравнение ArrayDeque и LinkedList
Использование в качестве стэка
Ссылки:
PriorityQueue
Очередь по приоритету возвращает элементы в отсортированном порядке, после того как они были введены в произвольном порядке.
Например, мы хотим получить элементы в порядке возрастания. В этом случае голова очереди будет указывать на наименьший элемент. Когда элемент будет получен, следующий наименьший элемент станет головой очереди.
Элементы приоритетной очереди могут быть не отсортированы, однако элементы возвращаются в отсортированном порядке.
Ссылки:
HashMap
Отображение. Структура данных для хранения связанных вместе пар “ключ-значение”. Хэширует только ключи, значения не хэшируются. Хэширование выполняется немного быстрее, чем вставка в дерево, поэтому данные отображение используется, когда не требуется отсортированный порядок ключей.
Ссылки:
TreeMap
Отображение. Структура данных для хранения связанных вместе пар “ключ-значение”. Использует хранение ключей в виде дерева для поиска. Функция сравнения для вставки в дерево используется только для ключей, значения не сравниваются.
Ссылки:
WeakHashMap
Отображение основанное на хэш таблицах со слабыми ключами. Записи в нем автоматически будут удалены системой сборки “мусора”, если ключ не используется (на него нет ссылок, кроме WeakHashMap), при удалении ключа также будет удалено связанное значение.
Сравнение WeakHashMap и HashMap
Ссылки:
LinkedHashMap
Отображение основанное на хэш-таблицах с сохранением порядка ввода элементов или порядка доступа к элементам в двунаправленном связанном списке. Порядок доступа может быть использован при реализации кэширования с “наиболее давним использованием”. Сохраняются часто используемые элементы, а при заполнении удаляется наиболее старый элемент.
Сравнение LinkedHashMap и HashMap
Оба LinkedHashMap и HashMap реализуют интерфейс Map. Однако, существуют некоторые отличия между ними.
Ссылки:
EnumMap
Класс EnumMap специализированная реализация Map для использования типа enum в качестве ключей. Все ключи должны иметь один тип enum который явно или неявно указан при создании отображения. Внутри данный класс реализован как массивы. Такая реализация очень компактна и эффективна.
Ссылки:
IdentityHashMap
Этот класс не является реализацией общего назначения интерфейса Map! Хотя этот класс реализует интерфейс Map, он намеренно нарушает общее соглашение, которое предписывает использование метода equals() при сравнении объектов. Этот класс используется только когда требуется семантика равенства ссылок.
Класс IdentityHashMap используется, когда хэш-значения ключей должны вычисляться не методом hashCode(), а методом System.identityHashCode(). В данном методе вычисление хэш-кода происходит исходя из адреса объекта в памяти. Для сравнения объектов типа IdentityHashMap используется операция ==, а не метод equals().
Ссылки:
Представления и оболочки
Представлением называется объект реализующий интерфейс коллекции методы которого управляют исходной коллекцией.
Поддиапазоны
headSet()
tailSet()
headMap()
tailMap()
Немодифицируемые представления
В классе Collections есть методы, которые создают немодифицируемые представления коллекций. Данные представления производят динамическую проверку попытки изменить коллекцию и генерируют исключение.
Синхронизированные представления
Если обращение к коллекции происходит из нескольких потоков, то нужно исключить ее повреждение. Вместо реализации потокобезопасных классов был использован механизм представлений, чтобы сделать потокобезопасными обычные коллекции.
Проверяемые представления
Предназначены для отладки ошибок, возникающих при применении обобщенных типов. При несоответствии типа генерируется исключение типа ClassCastException.
Прочее
Сортировка и перестановка
Двоичный поиск
Алгоритмы
Взаимное преобразование коллекций и массивов
Преобразование массива в коллекцию
Преобразование коллекции в массив
В интерфейсе Interface Collection есть следующие методы:
Унаследованные коллекции
В первом выпуске java появились коллекции, применявшиеся до появления фреймворка коллекций. Они были добавлены в фреймворк коллекций.
Иерархия унаследованных классов коллекций Hashtable, Properties 
Иерархия унаследованных классов коллекций Vector, Stack 
Обзор коллекций в Java (Java Collections Framework)
Коллекции в Java
Java Коллекции являются одним из столпов Java Core. Они используются почти в каждом приложении, поэтому мы просто обязаны уметь использовать Java Collections Framework эффективно.
Что такое Коллекции?
Коллекции — это контейнеры, группы элементов, которые представляют собой единое целое.
Например: банка конфет, список имен и т.д. Коллекции используются почти в каждом языке программирования и Java не является исключением. Как только коллекции появились в Java, то насчитывали всего несколько классов: Vector, Stack, Hashtable, Array. Но уже в Java 1.2 появился полноценный Java Collections Framework, с которым мы и будем сегодня знакомиться.
Коллекции в Java состоят нескольких частей
Преимущества Java Collections Framework
В Java Collections Framework есть следующие преимущества:
Интерфейсы коллекций
Следует отметить, что платформа Java не предоставляет отдельные интерфейсы для каждого типа коллекций. Если какая-то операция не поддерживается, то реализация коллекции бросает UnsupportedOperationException.
Кратко по каждой коллекции
Интерфейс итератора (Iterator)
Интерфейс множества (Set)
Набор представляет собой коллекцию, которая не может содержать повторяющиеся элементы. Этот интерфейс представляет математическую абстракцию для представления множеств в виде колоды карт.
Платформа Java содержит три реализации Set : HashSet, TreeSet и LinkedHashSet.И нтерфейс Set не позволяет осуществлять произвольный доступ к элементу в коллекции. Мы можем использовать итератор или цикл по каждому элементу для перебора элементов.
Интерфейс Список (List)
Коллекции в java
Сегодня поговорим о коллекциях — структурах данных для хранения объектов. Самое короткое и простое определение коллекции: коллекция — это объект, который хранит другие объекты.
Для начала выясним: для чего нам нужны коллекции если у нас уже есть массивы, которые могут хранить другие объекты? Все дело в простоте и удобстве использования. Зачем изобретать велосипед, если его уже изобрели до нас. Мы просто берем и используем готовые решения, которые зачастую будут работать быстрее наших. Когда мы познакомимся с разными коллекциями, Вы поймете, что некоторые из них и строятся на массивах.
В чем еще преимущество использования коллекций:
И это еще не полный список. По мере того, как Вы будете программировать, Вы сможете по настоящему оценить коллекции в java.
В Java есть два главных интерфейса от которых и наследуются все остальные классы коллекций: Collection, Map.
Collection — хранит набор объектов в виде к которому мы уже привыкли изучая массивы: есть объект он помещается в ячейку. С ним возможны все манипуляции: удаление, вставка нового, поиск и т.д.
Map — хранит данные в виде пары «ключ-значение». Сегодня мы поговорим только о первом интерфейсе в связи с тем, что тема достаточно обширная и важная.
Интерфейс Collection наследуется другими интерфейсами, которые в свою очередь имплементируются классами, в которых реализована та или иная структура данных.
На картинке выше Вы можете посмотреть иерархию интерфейсов коллекции и увидеть методы, которые у них есть. Как видим методов достаточно много и они очень полезные в работе с массивами данных.
От этих интерфейсов, как я уже говорил выше идет реализация классов.
Есть еще абстрактные классы, от которых унаследуются классы выше, но я сознательно упускаю от Вас эту информацию поскольку считаю, что это только усложнит и так запутанную структуру классов коллекций. Она сложна только на первый взгляд. Разобравшись в тонкостях, Вы уже сможете найти более развернутую информацию и нюансы об этих структурах данных.
ArrayList — коллекция на основе массива. Имеет свойство изменять свой размер в зависимости от того удаляются или добавляются элементы.
LinkedList — коллекция на основе связанного списка. Элементы помещенные в данную коллекцию сохраняют свой порядок вставки. То есть, в каком порядке был вставлен элемент, в таком порядке он будет при выводе. Каждый элемент, который хранится в LinkedList, содержит ссылки на «соседей». Это упрощает добавление и удаление элементов в списке. Классы ArrayList и Vector предпочтительнее использовать для поиска элементов, потому что эти классы используют индексы для доступа к элементам. Однако вставка и удаление элементов для них будет медленнее, чем LinkedList.
Vector — тот же самый ArrayList с той разницей, что методы данной коллекции синхронизованы. То есть, потокобезобасны.
Stack — список, который реализует данные стека. Элементы размещаются по принципу LIFO (last-in, first-out) — последний пришел, первым ушел.
Теперь немного практики. Здесь, я не буду приводить много методов и все структуры данных, так как они интуитивно понятны и очень простые в использовании.
import java.util.ArrayList ;
import java.util.List ;
public class ListExample <
Результат работы программы:
Хотелось бы обратить внимание на метод stream, который является нововведением в Java 8. Если интересно, можно почитать отдельную статью о стрим апи.
Заменив ArrayList на LinkedList мы получаем тот же набор методов для этой структуры данных. Выбор в использовании структур зависит от требований программы. Преимущества каждой структуры мы описали выше. Что еще отличает LinkedList от ArrayList так это то, что на выходе Вы получите элементы в том же порядке, в котором Вы их добавляли в LinkedList. В то время, как ArrayList не гарантирует это. Те же самые методы будут работать для Vector и Stack.
Теперь перейдем к Set.
Set — коллекция, которая не содержит повторяющихся элементов.
HashSet — набор, в котором элементы хранятся в хеш-таблице. У элементов нет строгого порядка. HashSet использует метод hashCode своих элементов для определения их размещения в наборе.
LinkedHashSet — элементы хранятся в виде связанного списка. Только элементы хранятся в сортированном виде.
TreeSet — хранит элементы в структуре данных дерева, которая также сортируется и доступна для навигации. Методы добавление, удаление и получить элемент, гарантируют работу в log (n) времени, где n — количество элементов в дереве.
import java.util.Set ;
import java.util.TreeSet ;
public class SetExample <
Результат работы программы:
Как видим, добавление еще одной 30 не удалось, что подтверждает теорию о том, что в сет можно добавить только уникальные объекты. Методы данной структуры такие же как и List. Поэтому останавливаться здесь подробно не будем.
Еще предлагаю рассмотреть очередь (Queue).
Queue — коллекция, которая хранит элементы в определенном порядке, нужном для их обработки. Помимо основных методов Collection в этом интерфейсе добавлены дополнительные методы вставки, проверки, извлечения. В данной коллекции элементы обычно размещаются в порядке FIFO (first-in, first-out) — первым пришел, первым ушел.
Теперь к реализациям.
PriorityQueue — очередь, в которой элементы упорядочиваются на основании заданного вами параметра(в отличие от параметра на основе FIFO). Эта очередь упорядочивает элементы либо по их натуральному порядку (используя интерфейс Comparable), либо с помощью интерфейса Comparator, полученному в конструкторе.
import java.util.Comparator ;
import java.util.PriorityQueue ;
import java.util.Queue ;
public class QueueExample <
public static void main ( String [ ] args ) <
Comparator Integer > comparator = new Comparator Integer > ( ) <
Результат работы программы: [80, 9, 1, 7]
Как я уже говорил выше, Qeue имеет свои собственные методы получения, вставки и удаления элемента. Отличия от стандартных методов Collection заключаются в том, что если стандартные методы генерируют исключения, то методы Queue возвращают специальное значение.
import java.util.PriorityQueue ;
import java.util.Queue ;
public class QueueExample <
[1, 4, 9, 7, 80]
1
4
[4, 7, 9, 80]
Пожалуй, на этом и закончим данную статью. О Map мы поговорим в другой раз. А сейчас, у Вас и так хватит работы, чтобы потренироваться в использовании прочитанного материала. Используйте коллекции, не бойтесь выхода за пределы как это было с массивами. Не следите за размерностью — об этом уже позаботились разработчики коллекций.