Java Collections Framework

Что такое Java Collections

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

Collections— это контейнеры, группы элементов, которые представляют собой единое целое.

Например: банка конфет, список имен и т.д. Коллекции используются почти в каждом языке программирования и Java не является исключением. Как только коллекции появились в Java, то насчитывали всего несколько классов: Vector, Stack, Hashtable, Array. Но уже в Java 1.2 появился полноценный Java Collections Framework, с которым мы и будем сегодня знакомиться.

Коллекции в Java состоят нескольких частей

Интерфейсы: В коллекциях интерфейсы обеспечивают абстрактный тип данных для представления коллекции java.util.Collection — корневого интерфейса фреймворка. Он находится на вершине иерархии Коллекций. Он содержит наиболее важные методы: size(), iterator(), add(), remove(), clear(). Каждая коллекция должна реализовывать эти методы. Также есть другие важные интерфейсы java.util.List, java.util.Set,java.util.Queue и java.util.Map. Map является единственным интерфейсом, который не наследует интерфейс Collection, но является неотъемлемой частью коллекций. Все интерфейсы фреймворка находятся в пакете java.util.

Список интерфейсов и классов в Java Collections

Реализация: Java предоставляет готовые классы с реализацией вышеупомянутых коллекций. Мы можем использовать их для создания новых типов коллекций в нашей программе. С помощью классов ArrayList, LinkedList, HashMap, TreeMap, HashSet, TreeSet можно решить огромное количество задач, но если нам нужна специальная реализация той или иной коллекции, мы можем наследовать её и работать со своей реализацией. В Java 1.5 придумали потокобезопасные коллекции, которые позволили изменять содержимое коллекции время итерации по элементам. Наиболее популярными являются: CopyOnWriteArrayList, ConcurrentHashMap, CopyOnWriteArraySet. Эти классы находятся в пакете java.util.concurrent. Все классы коллекций находятся в пакетах java.util и java.util.concurrent.
Алгоритмы: алгоритмы — это полезны методы, которые решают тривиальные задачи, например: поиск, сортировка и перетасовка элементов коллекции.

Преимущества Java Collections Framework

В Java Collections Framework есть следующие преимущества:

Требует меньше усилий. Фреймворк располагает множеством распространенных типов коллекций и полезных методов для манипуляции данными. Таким образом, мы можем сосредоточиться на бизнес-логике, а не разработке наших API.
Отличное качество — использование хорошо проверенных коллекций увеличивает качество нашей программы.
Повторное использование и совместимость

List

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

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). Так же, ввиду реализации, данную коллекцию можно использовать как стек или очередь. Для этого в ней реализованы соответствующие методы.

Разница между ArrayList и Vector в Java

ArrayList и Vector оба являются классами в иерархии Collection Framework. ArrayList и Vector, оба используются для создания динамического массива объектов, размер которого может увеличиваться по мере необходимости. Существует два основных отличия ArrayList и Vector в том, что Vector принадлежит классам Legacy, которые впоследствии были реинжинирированы для поддержки классов коллекции, тогда как ArrayList является стандартным классом коллекции. Другое важное отличие состоит в том, что ArrayList не синхронизирован с другой стороны; Вектор синхронизирован.

Ключевые различия между ArrayList и векторами

Несколько потоков могут работать с ArrayList одновременно, поэтому он считается несинхронизированным . В отличие от ArrayList, только один поток может работать с вектором одновременно; следовательно это называется Синхронизировано .
В ранней версии Java некоторые классы и интерфейсы обеспечивали методы для хранения объектов, которые они называли классами Legacy. Вектор является одним из классов Legacy в Java. Позднее эти устаревшие классы были реинжинирированы для поддержки класса Collection, тогда как класс ArrayList является стандартным классом Collection.
Когда предел массива полностью используется и новый объект добавляется рядом с исчерпанным массивом, его размер увеличивается в обоих случаях, т.е. как в ArrayList, так и в Vector, но разница в том, что в ArrayList, если не указан размер увеличивается на 50% от текущего массива, тогда как в массиве Vector размер удваивается, если значение приращения не указано.
Vector использует Enumeration, а также Iterator для обхода массива, тогда как ArrayList использует итератор только для обхода массива.
Поскольку ArrayList не синхронизирован и многие потоки могут работать с ним одновременно, его производительность лучше, чем у Vector, с которым одновременно может работать только один поток.

В чем разница между ArrayList и LinkedList?

Как выглядит ArrayList и LinkedList в Java

ArrayList и LinkedList являются классами Collection, и оба они реализуют интерфейс List. LinkedList реализует его с двусвязным списком, в то время как ArrayList реализует его с помощью динамического массива перераспределения.

Операция поиска

Операция поиска в ArrayList довольно быстро по сравнению с операцией поиска LinkedList. Метод ArrayList get (int index)дает производительность O(1), в то время как производительность LinkedList равна O(n). Это связано с тем, что ArrayList позволяет произвольный доступ к элементам в списке, поскольку он работает с основанной на индексе структурой данных, в то время как LinkedList не разрешает произвольный доступ, поскольку он не имеет индексов для непосредственного доступа к элементам, он должен пересекать список для извлечения или получить доступ к элементу из списка.

Манипуляции

Манипуляция с ArrayList медленная, поскольку она внутренне использует массив. Если нам нужно вставить или удалить элемент в ArrayList, он может принимать O(n), поскольку он внутренне использует массив, и нам может потребоваться сдвинуть элементы в случае вставки или удаления. С другой стороны, манипуляции с LinkedList быстрее, чем ArrayList, потому что он использует двусвязный список, поэтому в памяти не требуется сдвиг бит. Если нам нужно вставить или удалить элемент в LinkedList, он будет принимать O(1), поскольку он внутренне использует дважды.

ArrayList - это более простая структура данных, чем LinkedList. ArrayList имеет один массив указателей в смежных ячейках памяти. Его нужно только воссоздать, если массив расширен за пределы выделенного размера. Но LinkedList состоит из цепочки узлов; каждый узел разделяется выделенным и имеет передние и задние указатели на другие узлы. Итак, если вам не нужно вставлять середину, сращивать, удалять в середине и т. Д., ArrayList обычно будет быстрее. Он нуждается в меньшем распределении памяти, имеет гораздо лучшую локальность ссылки (что важно для кэширования процессора) и т. Д.

Поведение

Arraylist ведет себя как List, поскольку он реализует список. LinkedList ведет себя как List a, а также Queue, поскольку он реализует List и Queue.

Накладные расходы памяти

ArrayList поддерживает индексы и данные элементов, в то время как LinkedList поддерживает данные элемента и два указателя для соседних узлов, следовательно, потребление памяти в LinkedList сравнительно велико.

Set

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

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

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

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

Этот интерфейс описывает коллекции с предопределённым способом вставки и извлечения элементов, а именно — очереди 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.

Map

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 автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элеметна нет жёстких ссылок.

Заключение

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