что такое коллекция java

Коллекции в Java

2020.06.08 (Последнее изменение: 2021.07.15)

Общее описание

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

Иерархия интерфейсов коллекций

Интерфейс Map

Отображение. Структура данных для хранения связанных вместе пар “ключ-значение”.

public interface Map

Вложенные классы

Методы

Наиболее общие реализации сведены в следующей таблице:

Свойства коллекций

Временная сложность

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

Источник

Коллекции

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

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

Хотя в 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, предназначен для создания наборов по типу словаря с объектами в виде пары «ключ-значение»

ArrayList : простой список объектов

LinkedList : представляет связанный список

ArrayDeque : класс двунаправленной очереди, в которой мы можем произвести вставку и удаление как в начале коллекции, так и в ее конце

TreeSet : набор отсортированных объектов в виде дерева

LinkedHashSet : связанное хеш-множество

PriorityQueue : очередь приоритетов

HashMap : структура данных в виде словаря, в котором каждый объект имеет уникальный ключ и некоторое значение

TreeMap : структура данных в виде дерева, где каждый элемент имеет уникальный ключ и некоторое значение

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

Интерфейс Collection

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

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

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 () : возвращает массив, содержащий все элементы коллекции

Источник

Коллекции в Java: о чём многие забывают

Из опыта code-review и ответов на StackOverflow набралось немало моментов, касающихся Java Collections API, которые мне казались очевидными, но другие разработчики о них почему-то не знали или знали, но не чувствовали уверенности их применять. В этой статье я собираю в общую кучу всё, что накопилось.

Содержание:

List.subList

Про это уже писали, но стоит повторить. Наверно, самый недооценённый метод из Collections API. Бывает, что надо каким-то образом обработать часть списка (например, в алгоритмах семейства «разделяй и властвуй» или при распараллеливании задачи). Многие создают метод или класс, который завязывается на три параметра: List, from и to:

Так незачем делать. Реализации алгоритма должно быть плевать, что она обрабатывает часть списка. Пишите:

Даже если у вас всё в одном методе, удобнее воспользоваться расширенным циклом for, чем возиться с индексами:

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

У популярных реализаций вроде ArrayList это выполняется очень быстро.

Надо выяснить, начинается ли список с определённых элементов? И тут subList в руки!

Надо добавить в один список все элементы другого списка за исключением первого? И тут subList придёт на помощь:

PriorityQueue

Если subList — самый недооценённый метод, то PriorityQueue — это, на мой взгляд, самый недооценённый класс. Многие сталкиваются с задачей отыскать, скажем, 10 минимальных значений большого несортированного списка. Чаще всего список сортируют и потом берут первые 10 значений. Если исходный список менять нельзя, придётся его ещё скопировать для сортировки. А ведь очередь с приоритетом легко справится с этой задачей:

Такой код в зависимости от данных может работать гораздо быстрее, чем сортировка. Например, для n = 10 и случайно заполненного списка из миллиона элементов очередь с приоритетом почти в сто раз обгоняет подход с сортировкой. При этом дополнительной памяти требуется O(n) и входные элементы можно обрабатывать в потоковом режиме (например, выбрать 10 наименьших чисел из входного файла).

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

EnumSet и EnumMap

До сих пор встречается код, где значения типа enum используют в качестве ключей в HashSet и HashMap. Хотя это работает, но оно неоправданно расточительно. Существующие специальные классы EnumSet и EnumMap значительно производительнее. Так если в enum не больше 64 разных значений, EnumSet хранит всё в одном поле типа long в битовой маске. EnumMap содержит все значения в обычном массиве той же длины, сколько элементов в enum, а ключи не хранит вовсе. Так как у каждого значения в enum есть порядковый номер ordinal(), можно легко перейти от enum-ключа к элементу массива. Также никогда не нужно менять размер массива.

Set.add(E) и Set.remove(E) возвращают булево значение

Часто вижу подобный код:

Не надо забывать, что операция добавления в Set возвращает true, если добавление успешно (то есть элемента не было) и false, если такой элемент уже был. Незачем усложнять код и два раза пробивать элемент по хэш-таблице или двоичному дереву, ведь можно написать:

Map.put(K, V), Map.remove(K), List.set(idx, E), List.remove(idx) возвращают предыдущий элемент

Из той же оперы ситуация. Методы, изменяющие или удаляющие элемент в коллекции возвращают предыдущее значение, и этим надо пользоваться. Не надо писать, например, так:

Map.keySet() и Map.values()

Многие почему-то забывают, что Map.keySet() и Map.values() возвращают отображения исходного Map, которые позволяют удалять элементы (если Map модифицируемый). Надо оставить в Map только записи с определёнными значениями (и любыми ключами)? Пожалуйста:

Arrays.asList может быть ключом

Arrays.asList() создаёт список из нужного числа элементов и у него как раз подходящие реализации equals и hashCode : никакой boilerplate не нужен. Так можно создать ключ любой длины, причём корректно обработаются null-значения и примитивы (брагодаря боксингу). Не сработает только, если вы хотите в составе ключа иметь массив.

Collections.min/max

К примеру, вам нужно найти ключ в Map, соответствующий максимальному значению. Пишите так:

Можно и через Stream API, но Collections.max() несколько быстрее. Если вы не можете использовать Java-8 и компараторы вроде Entry.comparingByValue() вам недоступны, их нетрудно написать.

Stack, Vector, Hashtable, LinkedList

Просто не используйте эти классы. Пользы от них никакой нет. Вместо Stack пользуйтесь ArrayDeque, вместо Vector — ArrayList, вместо Hashtable — HashMap. Если вам нужна потокобезопасность, они вам всё равно не помогут. Возможно, в девятке их всё-таки пометят @Deprecated (смотрите JEP 277).

На сегодня всё. Программируйте с удовольствием!

Источник