Java – все, что нужно знать о коллекциях


Содержание

Наборы данных Collection

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

Интерфейс Collection является фундаментальным интерфейсом для классов Java, поддерживающих наборы данных (коллекции), в котором объявлены следующие 2 основных метода :

Помимо них, интерфейс Collection имеет еще несколько методов, которые рассмотрены ниже.

Метод add() добавляет элемент к набору и возвращает либо значение true, если набор данных изменился, либо false в противном случае. Например, если попытаться добавить в множество уже существующий объект, то запрос add() будет проигнорирован, поскольку по определению множество не может содержать дублирующие объекты.

Метод iterator() возвращает объект-итератор, реализующий интерфейс Iterator, который используется для последовательного обращения к элементам набора данных.

Интерфейс Iterator

В интерфейсе Iterator определены следующие три основных метода:

Реализация интерфейса Iterator предполагает, что с помощью вызова метода next() можно получить следующий элемент. С помощью метода hasNext() можно узнать, есть ли следующий элемент, и не достигнут ли конец коллекции. И если элементы еще имеются, то hasNext() вернет значение true. Метод hasNext() следует вызывать перед методом next(), так как при достижении конца коллекции метод next() выбрасывает исключение NoSuchElementException. И метод remove() удаляет текущий элемент, который был получен последним вызовом next().

Пример с Iterator для перебора коллекции, метод hasNext

Цикл for each

Начиная с JDK 5.0 можно сократить запись цикла, используя выражение «for each»

Компилятор преобразует цикл «for each» в обычный цикл с итератором. Цикл «for each» работает с любым объектом, реализующим интерфейс Iterable, в котором объявлен единственный метод

Интерфейс Collection расширяет интерфейс Iterable. Поэтому цикл «for each» можно использовать для любого набора данных из стандартной библиотеки.

Порядок следования элементов в итераторе

Порядок перебора элементов коллекции зависит от типа и набора элементов. Если используется объект ArrayList, то итератор начинает с индекса 0 и увеличивает индекс на 1 на каждом шаге. Если объект имеет тип HashSet, то порядок следования элементов коллекции может оказаться случайным.

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

Удаление элементов итератором

Метод remove() интерфейса Iterable удаляет элемент, возвращенный в результате последнего вызова метода next(). В большистве случаев это правильно, т.к. необходимо проверить элемент перед принятием решения об его удалении. Пример удаления первого элемента набора строк с использованием итератора :

Необходимо помнить, что перед вызовом next() и удалением remove() существует строгая взаимосвязь. Нельзя вызывать метод remove(), если ему не предшествовал вызов метода next(). При попытке сделать это будет сгенерировано исключение IllegalStateException.

При необходимости удаления двух соседних элементов нельзя дважды подряд вызвать метод remove().

Нужно сначала вызвать метод next(), чтобы итератор (указатель) встал на элемент, подлежащий удалению.

Универсальные вспомогательные методы, contains

Интерфейсы Collection и Iterable являются универсальными, поэтому для них можно создавать универсальные методы, работающие для любых наборов данных. Пример универсального метода contains, проверяющего наличие элемента obj в наборе данных :

Разработчики библиотеки Java добавили ряд полезных методов в интерфейс Collection, которые должны поддерживаться во всех реализующих его классах:

  • int size ()
  • boolean isEmpty ()
  • boolean contains (Object obj)
  • boolean containsAll (Collection c)
  • boolean equals (Object obj)
  • boolean addAll (Collection from)
  • boolean remove (Object obj)
  • boolean removeAll (Collection c)
  • void clear ()
  • boolean retainAll (Collection c)
  • Object[] toArray ()
  • T[] toArray (T[] arrayToFill)

Применение каждым классом, реализующим интерфейс Collection, такого количества стандартных методов было бы слишком обременительным. Чтобы упростить процесс их реализации, в классе AbstractCollection оставлены абстрактными только фундаментальные методы (такие, как size() и iterator()), а на их основе реализованы все остальные стандартные методы.

Теперь конкретный класс, представляющий набор данных, может расширить класс AbstractCollection за счет реализации метода iterator(), а метод contains() уже реализован в родительском классе AbstractCollection. Однако, если дочерний класс содержит более эффективный вариант реализации метода contains(), то его можно использовать вместо варианта родительского класса.

Методы интерфейса java.util.Collection

Метод Описание
Iterator iterator() Возвращает итератор для обращения к элементам набора данных.
int size() Возвращает количество элементов в наборе данных.
boolean isEmpty() Возвращает значение true, если набор пустой.
boolean contains (Object obj) Возвращает true, если набор содержит объект, эквивалентный obj.
boolean containsAll (Collection other) Возвращает true, если текущий набор содержит все объекты набора данных other.
boolean add (Object element) Добавляет элемент в набор. Возвращает true, если в результате вызова метода набор данных изменился.
boolean addAll (Collection other) Добавляет все элементы в набор. Возвращает true, если в результате вызова метода набор данных изменился.
boolean remove (Object obj) Удаляет объект obj. Возвращает true, если в результате вызова метода набор данных изменился.
boolean removeAll (Collection other) Удаляет из текущего набора данных все элементы, содержащиеся в наборе other. Возвращает true, если в результате вызова метода набор данных изменился.
void clear () Удаляет из текущего набора данных все элементы.
boolean retainAll (Collection other) Удаляет из набора данных элементы, не совпадающие с теми, которые содержатся в наборе other. Возвращает true, если в результате вызова метода набор данных изменился.
Object[] toArray () Возвращает массив с объектами из набора данных.

Методы итератора java.util.Iterator

Метод Описание
boolean hasNext() Возвращает значение true, если в коллекции имеется следующий элемент, иначе возвращает false
Object next() Возвращает следующий элемент. Если достигнут конец набора,то генерируется исключение NoSuchElementException
void remove() Удаляет последний прочитанный элемент. Этот метод должен быть вызван сразу же после обращения к элементу. Если после чтения элемента набор данных изменился, данный метод генерирует исключение IllegalStateException

Интерфейс ListIterator

Интерфейс Iterator предоставляет ограниченный функционал. Гораздо больший набор методов предоставляет другой итератор — интерфейс ListIterator. Данный итератор используется классами, реализующими интерфейс List, то есть классами LinkedList, ArrayList и др.

Интерфейс ListIterator расширяет интерфейс Iterator и определяет ряд дополнительных методов:

Метод Описание
void add(E obj) Вставляет объект obj перед элементом, который должен быть возвращен следующим вызовом next()
boolean hasNext() Возвращает true, если в коллекции имеется следующий элемент, иначе возвращает false
boolean hasPrevious() Возвращает true, если в коллекции имеется предыдущий элемент, иначе возвращает false
E next() Возвращает следующий элемент, если такого нет, то генерируется исключение NoSuchElementException
E previous() Возвращает предыдущий элемент, если такого нет, то генерируется исключение NoSuchElementException
int nextIndex() Возвращает индекс следующего элемента. Если такого нет, то возвращается размер списка
int previousIndex() Возвращает индекс предыдущего элемента. Если такого нет, то возвращается число -1
void remove() Удаляет текущий элемент из списка. Таким образом, этот метод должен быть вызван после методов next() или previous(), иначе будет сгенерировано исключение IllegalStateException
void set(E obj) Присваивает текущему элементу, выбранному вызовом методов next() или previous(), ссылку на объект obj

Пример использования итератора ListIterator

Иерархия наборов данных интерфейса Collection

На рисунке представлена иерархия наборов классов, реализующих интерфейс Collection:

Список наборов данных

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

Коллекции в Java

категория
Java
дата 27.06.2013
автор vovanok
голосов 185

Алгоритмы + Структуры данных = Программы.
Никлаус Вирт.

Введение

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

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

В данной статье речь пойдет именно о Java Collections Framework, так как существуют многочисленные альтернативы:
1. Guava(Google Collections Library) — Библиотека добавляет несколько полезных реализаций структур данных, таких как мультимножество, мультиотображение и двунаправленное отображение. Улучшена эффективность.
2. Trove library — Реализация коллекций, позволяющая хранить примитивы (в Java Collections Framework примитивы хранить нельзя, только оберточные типы), что позволяет повысить эффективность работы.
3. PCJ(Primitive Collections for Java) — так же как и Trove предназначены для примитивных типов, что позволит повысить эффективность.
4. Наконец Вы сами можете написать собственную коллекцию (тот же связной список). Но данный подход не рекомендуется :)

Как видим, выбрать есть из чего. Но для начала необходимо освоить базовые коллекции Java которыми пользуются чаще всего. А так же некоторые сторонние библиотеки реализуют интерфейсы Java Collections Framework (пример Guava http://guava-libraries.googlecode.com/svn/tags/release05/javadoc/overview-tree.html). То есть знание иерархии классов базовых коллекций позволит более быстро освоить сторонние библиотеки.

Базовые интерфейсы

В библиотеке коллекций Java существует два базовых интерфейса, реализации которых и представляют совокупность всех классов коллекций:

1. Collection — коллекция содержит набор объектов (элементов). Здесь определены основные методы для манипуляции с данными, такие как вставка (add, addAll), удаление (remove, removeAll, clear), поиск (contains)
2. Map — описывает коллекцию, состоящую из пар «ключ — значение». У каждого ключа только одно значение, что соответствует математическому понятию однозначной функции или отображения (тар). Такую коллекцию часто называют еще словарем (dictionary) или ассоциативным массивом (associative array). Никак НЕ относится к интерфейсу Collection и является самостоятельным.

Хотя фреймворк называется Java Collections Framework, интерфейс map и его реализации входят в фреймворк тоже !
Интерфейсы Collection и Map являются базовыми, но они не есть единственными. Их расширяют другие интерфейсы, добавляющие дополнительный функционал. О них мы ещё поговорим.

Интерфейс Collection

Давайте рассмотрим основные интерфейсы, относящиеся к Collection:

Как видно с диаграммы, интерфейс Collection не является базовым (какая интрига :D). Интерфейс Collection расширяет интерфейс Iterable, у которого есть только один метод iterator(). Это значит что любая коллекция, которая есть наследником Iterable должна возвращать итератор.

Итератор(http://ru.wikipedia.org/wiki/%D0%98%D1%82%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80) — объект, абстрагирующийся за единым интерфейсом доступ к элементам коллекции. Итератор это паттерн позволяющий получить доступ к элементам любой коллекции без вникания в суть ее реализации.

Идем дальше. Как видим с рисунка, интерфейс Collection расширяют интерфейсы List, Set и Queue. Давайте рассмотрим, зачем нужен каждый.
1. List — Представляет собой неупорядоченную коллекцию, в которой допустимы дублирующие значения. Иногда их называют последовательностями (sequence ). Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу.
2. Set — описывает неупорядоченную коллекцию, не содержащую повторяющихся элементов. Это соответствует математическому понятию множества (set).
3. Queue — очередь. Сразу запоминаем как правильно произносится: Queue — КЬЮ (http://www.youtube.com/watch?feature=player_embedded&v=ugauQ769kVc#at=22 ). Это коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки. В дополнение к базовым операциям интерфейса Collection, очередь предоставляет дополнительные операции вставки, получения и контроля.

Реализации интерфейса List

Сразу смотрим на иерархию классов.

Красным здесь выделены интерфейсы, зеленым — абстрактные классы, а синим готовые реализации. Сразу хочу заметить что здесь не вся иерархия, а только основная её часть.

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

ArrayList — пожалуй самая часто используемая коллекция. ArrayList инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов.
Так как ArrayList использует массив, то время доступа к элементу по индексу минимально (В отличии от LinkedList). При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево, при этом реальный размер массива (его емкость, capacity) не изменяется. Если при добавлении элемента, оказывается, что массив полностью заполнен, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент.

LinkedList — Двусвязный список. Это структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и две ссылки («связки») на следующий и предыдущий узел списка. Доступ к произвольному элементу осуществляется за линейное время (но доступ к первому и последнему элементу списка всегда осуществляется за константное время — ссылки постоянно хранятся на первый и последний, так что добавление элемента в конец списка вовсе не значит, что придется перебирать весь список в поисках последнего элемента). В целом же, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций.

Часто на собеседованиях спрашивают про отличия ArrayList и LinkedList. И какой когда нужно использовать. См. вопрос собеседования: http://www.quizful.net/interview/java/54AubfnDy6Ti

Реализации интерфейса Set

Смотрим следующую диаграмму. Пытаемся вникнуть :)

HashSet — коллекция, не позволяющая хранить одинаковые объекты(как и любой Set). HashSet инкапсулирует в себе объект HashMap (то-есть использует для хранения хэш-таблицу).
Как большинство читателей, вероятно, знают, хеш-таблица хранит информацию, используя так называемый механизм хеширования, в котором содержимое ключа используется для определения уникального значения, называемого хеш-кодом. Этот хеш-код затем применяется в качестве индекса, с которым ассоциируются данные, доступные по этому ключу. Преобразование ключа в хеш-код выполняется автоматически — вы никогда не увидите самого хеш-кода. Также ваш код не может напрямую индексировать хеш-таблицу. Выгода от хеширования состоит в том, что оно обеспечивает константное время выполнения методов add(), contains(), remove() и size() , даже для больших наборов.

Если Вы хотите использовать HashSet для хранения объектов СВОИХ классов, то вы ДОЛЖНЫ переопределить методы hashCode() и equals(), иначе два логически-одинаковых объекта будут считаться разными, так как при добавлении элемента в коллекцию будет вызываться метод hashCode() класса Object (который скорее-всего вернет разный хэш-код для ваших объектов).
Важно отметить, что класс HashSet не гарантирует упорядоченности элементов, поскольку процесс хеширования сам по себе обычно не порождает сортированных наборов. Если вам нужны сортированные наборы, то лучшим выбором может быть другой тип коллекций, такой как класс TreeSet.

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

TreeSet — коллекция, которая хранит свои элементы в виде упорядоченного по значениям дерева. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n).

Реализации интерфейса Queue

Здесь я привел очень упрощенную иерархию.

PriorityQueue — единственная прямая реализация интерфейса Queue (не считая LinkedList, который больше является списком, чем очередью).
Эта очередь упорядочивает элементы либо по их натуральному порядку (используя интерфейс Comparable), либо с помощью интерфейса Comparator, полученному в конструкторе.

Реализации интерфейса Map

Интерфейс Map соотносит уникальные ключи со значениями. Ключ — это объект, который вы используете для последующего извлечения данных. Задавая ключ и значение, вы можете помещать значения в объект карты. После того как это значение сохранено, вы можете получить его по ключу. Интерфейс Map — это обобщенный интерфейс, объявленный так, как показано ниже.

Здесь К указывает тип ключей, а V — тип хранимых значений.

Иерархия классов очень похожа на иерархию Set’а:

HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Хорошая статья http://habrahabr.ru/post/128017/

LinkedHashMap — расширяет класс HashMap. Он создает связный список элементов в карте, расположенных в том порядке, в котором они вставлялись. Это позволяет организовать перебор карты в порядке вставки. То есть, когда происходит итерация по коллекционному представлению объекта класса LinkedHashMap, элементы будут возвращаться в том порядке, в котором они вставлялись. Вы также можете создать объект класса LinkedHashMap, возвращающий свои элементы в том порядке, в котором к ним в последний раз осуществлялся доступ.
Рекомендую так же прочитать http://habrahabr.ru/post/129037/

Цукерберг рекомендует:  Games - Читы для игр

TreeMap — расширяет класс AbstractMap и реализует интерфейс NavigatebleMap. Он создает коллекцию, которая для хранения элементов применяет дерево. Объекты сохраняются в отсортированном порядке по возрастанию. Время доступа и извлечения элементов достаточно мало, что делает класс TreeMap блестящим выбором для хранения больших объемов отсортированной информации, которая должна быть быстро найдена.
Моя статья про TreeMap http://www.quizful.net/post/Java-TreeMap

WeakHashMap — коллекция, использующая слабые ссылки для ключей (а не значений). Слабая ссылка (англ. weak reference) — специфический вид ссылок на динамически создаваемые объекты в системах со сборкой мусора. Отличается от обычных ссылок тем, что не учитывается сборщиком мусора при выявлении объектов, подлежащих удалению. Ссылки, не являющиеся слабыми, также иногда именуют «сильными».
http://ru.wikipedia.org/wiki/%D0%A1%D0%BB%D0%B0%D0%B1%D0%B0%D1%8F_%D1%81%D1%81%D1%8B%D0%BB%D0%BA%D0%B0

Устаревшие коллекции

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

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());

Синхронизированные обрамления коллекций synchronizedMap и synchronizedList иногда называют условно потоко безопасными — все операции в отдельности потоко безопасны, но последовательности операций, где управляющий поток зависит от результатов предыдущих операций, могут быть причиной конкуренции за данные.
(источник http://www.ibm.com/developerworks/ru/library/j-jtp07233/)
Условная безопасность потоков, обеспечиваемая synchronizedList и synchronizedMap представляет скрытую угрозу — разработчики полагают, что, раз эти коллекции синхронизированы, значит, они полностью потоко безопасны, и пренебрегают должной синхронизацией составных операций. В результате, хотя эти программы и работают при лёгкой нагрузке, но при серьёзной нагрузке они могут начать выкидывать NullPointerException или ConcurrentModificationException.

Кроме того всегда существует возможность «классической» синхронизации с помощью блока synchronized.

Собираем все воедино

Итак, смотрим на получившейся диаграмму классов:

Как видим диаграмма достаточно массивная. Но такая архитектура считается эталонной в OOП.

Заключение

Надеюсь эта статья была вам полезной. Если в комментариях наберётся достаточно пожеланий, я напишу вторую часть статьи, где приведу примеры использования всех этих коллекций. (Представьте только: на собеседовании вас спрашивают про иерархию коллекций в java, а Вы им рисуете предыдущий рисунок. Как они будут удивлены :D)
Спасибо за внимание .

Если Вам понравилась статья, проголосуйте за нее

Коллекции

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

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

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

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

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

Интерфейсы являются основой Java Collections Framework. Обратите внимание, что все интерфейсы являются Generic, например public interface Collection . Использование — это указание типа объекта, который коллекция может содержать. Это помогает сократить ошибки времени выполнения с помощью проверки типов объектов во время компиляции.

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

Кратко по каждой коллекции

Интерфейс итератора (Iterator)

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

Интерфейс множества (Set)

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

Платформа Java содержит три реализации Set : HashSet, TreeSet и LinkedHashSet.И нтерфейс Set не позволяет осуществлять произвольный доступ к элементу в коллекции. Мы можем использовать итератор или цикл по каждому элементу для перебора элементов.

Интерфейс Список (List)

Список представляет собой упорядоченный набор элементов и может содержать повторяющиеся элементы. Вы можете получить доступ к любому элементу по индексу. Список представляет собой динамический массив. Список является одним из наиболее используемых типов коллекций. ArrayList и LinkedList классы являются реализацией интерфейса List .

Большая подборка полезных практических и обучающих материалов по Java

Java — язык программирования, который очень строго соответствует принципам объектно-ориентированного программирования. В этой статье вы найдете несколько полезных материалов, с которых стоит начать знакомство с языком.

Для начинающих

  • Отличная статья, в которой описано, как стоит подходить к изучению Java. После прочтения стоит заглянуть и в другие разделы сайта Skipy.ru, это уже будет полезно не только начинающим.
  • Study-Java — сайт, полностью состоящий из туториалов по Java, которые подскажут вам, в каком направлении стоит идти и какие навыки нужно вырабатывать в первую очередь.
  • Курс по основам языка Java.
  • Обширное руководство по многим темам с примерами кода.
  • Базовый курс по Java на ресурсе Stepik.
  • Более 350 вопросов с ответами для подготовки к интервью на позицию Junior Java Developer.
  • Наша подборка материалов для изучения языка Java.
  • Подборка полезных советов от Наньянского технологического университета — там есть аналогичные материалы и по другим темам.

Форумы, на которых вы можете задать возникшие вопросы:

Для продвинутых

  • Раздел Java на developer.com собрал в себе руководства как по целым пластам языка, вроде Enterprise Edition, так и разъяснения отдельных нюансов, вроде новомодных лямбда-выражений. Вот, например, статья, прочитав которую, вы разберётесь с тем, что такое аннотации, зачем они нужны и как правильно их использовать.
  • На сайте Tutorials Point есть раздел с исчерпывающим количеством туториалов по Java. Также там есть отдельный раздел для Java 8.
  • Java2S — коллекция примеров на все случаи жизни. Примечательно, что здесь есть не только чистая Java, но и работа с разными библиотеками, например JUnit. Хорошо описаны и нововведения Java 8 — Date-Time API, лямбды, потоки (streams).
  • Oskar Veerhoek — канал на YouTube, посвящённый OpenGL. Если вы собираетесь связать свою жизнь с программированием, маловероятно, что вам никогда не придётся работать с графикой. В течение курса из 41 видео автор расскажет вам, как работать с OpenGL в Java. Курс начинается с самых основ и написания 2D Minecraft’а, а заканчивается шейдерами, освещением и созданием 3D комнаты.

Для всех

  • Java-Tips — сборник готовых рецептов, шпаргалок, туториалов и полезных библиотек… Сайт будет незаменим для любого Java-программиста, особенно если вы только начинаете изучать язык. Отдельное спасибо стоит сказать тому, кто сортировал это всё — вам не составит труда найти здесь то, что вам нужно. Присутствуют материалы как по Java SE, так и по Enterprise и Micro версиям.
  • Регулярно обновляемый список вопросов и ответов.
  • Примеры решённых практических задач.
  • Структурированный справочник по языку.
  • Подробное руководство с примерами по каждой теме.
  • Обучающий материал от w3resource.
  • Подборка различных материалов для изучения языка.
  • Учебное пособие от Oracle, создателей языка.

  • Помните, что официальная документация — это источник самой достоверной и качественной информации.
  • Напоминаем, что на нашем сайте тоже есть порядочное количество статей по этому языку.

Практика

  • Бесплатные задачи, отсортированные по категориям на Codingbat;
  • Cписок задач от автора блога eax.me;
  • Олимпиадные задачи с ACMP;
  • Олимпиадные задачи с Codeforces;
  • Задачи с ответами на Codewars.

Полезные библиотеки

  • JUnit
    Любой код должен сопровождаться тестированием. Многие очень напрасно об этом забывают. Эта библиотека предназначена для автоматизации модульного тестирования. Еще несколько инструментов для тестирования в Java, вы найдете в нашей подборке.
  • HttpClient
    Библиотека для работы с HTTP ресурсами.
  • CommonsLang
    То, что «забыли» включить в JDK.
  • CommonsMath
    Отличное дополнение к java.math .
  • CommonsLogging
    Если вы используете для логирования System.out.println() , то вам стоит отрубить себе рук лучше воспользуйтесь этой библиотекой, так будет правильнее.
  • CommonsNet
    Логическое продолжение java.net , множество классов для работы с сетевыми протоколами.
  • CommonsVFS
    Библиотека, которая поможет вам абстрагироваться от способа хранения файлов — вы сможете достаточно обобщённо иметь к ним доступ по FTP, SFTP, WEBDAV, (G)ZIP и т.д.
  • CommonsIO
    С ней работать с вводом-выводом станет значительно проще.

Java 9

О том, какие изменения появились в Java 9, читайте в нашем обзоре с примерами.

Статьи

  • Подробный гайд по Java 9;
  • Знакомство с Project Jigsaw;
  • Java 9 Stream API: введение и материал по коллекторам;
  • Java 9 Process API;
  • Улучшения в Java Time (JSR-310);
  • Конкурентность;
  • Новое в Optional;
  • Разбираемся с Stack-Walking API;
  • Коллекции;
  • «Applying @Deprecated Enhancements»;
  • Используем sun.misc.Unsafe ;
  • Variable Handles;
  • Рефлексия vs Инкапсуляция;
  • Создание multi-release JAR-файлов при помощи Maven: о формате JAR, и о формате JAR с использованием Maven;
  • Ограничения памяти и Docker;
  • Введение в JShell.

Больше статей можно найти на этом сайте.

Блоги

  • Oracle (нет тега Java 9);
  • SitePoint;
  • Voxxed (выделим отличный цикл);
  • Baeldung;
  • Iteratr Learning (нет тега Java 9);
  • CodeFX;
  • Joda.

Книги и курсы

  • Курс «Java 9 Modularity: First Look»;
  • Книга «Java 9 Modularity»;
  • Книга «Mastering Java 9»;
  • Книга «Modular Programming in Java 9»;
  • Книга «Java 9 with JShell»;
  • Книга «Java 9 Module System».

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

Наборы данных Collection

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

Интерфейс Collection является фундаментальным интерфейсом для классов Java, поддерживающих наборы данных (коллекции), в котором объявлены следующие 2 основных метода :

Помимо них, интерфейс Collection имеет еще несколько методов, которые рассмотрены ниже.

Метод add() добавляет элемент к набору и возвращает либо значение true, если набор данных изменился, либо false в противном случае. Например, если попытаться добавить в множество уже существующий объект, то запрос add() будет проигнорирован, поскольку по определению множество не может содержать дублирующие объекты.

Метод iterator() возвращает объект-итератор, реализующий интерфейс Iterator, который используется для последовательного обращения к элементам набора данных.

Интерфейс Iterator

В интерфейсе Iterator определены следующие три основных метода:

Цукерберг рекомендует:  Нахождение дискриминанта и корней - Оцените консольное приложение

Реализация интерфейса Iterator предполагает, что с помощью вызова метода next() можно получить следующий элемент. С помощью метода hasNext() можно узнать, есть ли следующий элемент, и не достигнут ли конец коллекции. И если элементы еще имеются, то hasNext() вернет значение true. Метод hasNext() следует вызывать перед методом next(), так как при достижении конца коллекции метод next() выбрасывает исключение NoSuchElementException. И метод remove() удаляет текущий элемент, который был получен последним вызовом next().

Пример с Iterator для перебора коллекции, метод hasNext

Цикл for each

Начиная с JDK 5.0 можно сократить запись цикла, используя выражение «for each»

Компилятор преобразует цикл «for each» в обычный цикл с итератором. Цикл «for each» работает с любым объектом, реализующим интерфейс Iterable, в котором объявлен единственный метод

Интерфейс Collection расширяет интерфейс Iterable. Поэтому цикл «for each» можно использовать для любого набора данных из стандартной библиотеки.

Порядок следования элементов в итераторе

Порядок перебора элементов коллекции зависит от типа и набора элементов. Если используется объект ArrayList, то итератор начинает с индекса 0 и увеличивает индекс на 1 на каждом шаге. Если объект имеет тип HashSet, то порядок следования элементов коллекции может оказаться случайным.

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

Удаление элементов итератором

Метод remove() интерфейса Iterable удаляет элемент, возвращенный в результате последнего вызова метода next(). В большистве случаев это правильно, т.к. необходимо проверить элемент перед принятием решения об его удалении. Пример удаления первого элемента набора строк с использованием итератора :

Необходимо помнить, что перед вызовом next() и удалением remove() существует строгая взаимосвязь. Нельзя вызывать метод remove(), если ему не предшествовал вызов метода next(). При попытке сделать это будет сгенерировано исключение IllegalStateException.

При необходимости удаления двух соседних элементов нельзя дважды подряд вызвать метод remove().

Нужно сначала вызвать метод next(), чтобы итератор (указатель) встал на элемент, подлежащий удалению.

Универсальные вспомогательные методы, contains

Интерфейсы Collection и Iterable являются универсальными, поэтому для них можно создавать универсальные методы, работающие для любых наборов данных. Пример универсального метода contains, проверяющего наличие элемента obj в наборе данных :

Разработчики библиотеки Java добавили ряд полезных методов в интерфейс Collection, которые должны поддерживаться во всех реализующих его классах:

  • int size ()
  • boolean isEmpty ()
  • boolean contains (Object obj)
  • boolean containsAll (Collection c)
  • boolean equals (Object obj)
  • boolean addAll (Collection from)
  • boolean remove (Object obj)
  • boolean removeAll (Collection c)
  • void clear ()
  • boolean retainAll (Collection c)
  • Object[] toArray ()
  • T[] toArray (T[] arrayToFill)

Применение каждым классом, реализующим интерфейс Collection, такого количества стандартных методов было бы слишком обременительным. Чтобы упростить процесс их реализации, в классе AbstractCollection оставлены абстрактными только фундаментальные методы (такие, как size() и iterator()), а на их основе реализованы все остальные стандартные методы.

Теперь конкретный класс, представляющий набор данных, может расширить класс AbstractCollection за счет реализации метода iterator(), а метод contains() уже реализован в родительском классе AbstractCollection. Однако, если дочерний класс содержит более эффективный вариант реализации метода contains(), то его можно использовать вместо варианта родительского класса.

Методы интерфейса java.util.Collection

Метод Описание
Iterator iterator() Возвращает итератор для обращения к элементам набора данных.
int size() Возвращает количество элементов в наборе данных.
boolean isEmpty() Возвращает значение true, если набор пустой.
boolean contains (Object obj) Возвращает true, если набор содержит объект, эквивалентный obj.
boolean containsAll (Collection other) Возвращает true, если текущий набор содержит все объекты набора данных other.
boolean add (Object element) Добавляет элемент в набор. Возвращает true, если в результате вызова метода набор данных изменился.
boolean addAll (Collection other) Добавляет все элементы в набор. Возвращает true, если в результате вызова метода набор данных изменился.
boolean remove (Object obj) Удаляет объект obj. Возвращает true, если в результате вызова метода набор данных изменился.
boolean removeAll (Collection other) Удаляет из текущего набора данных все элементы, содержащиеся в наборе other. Возвращает true, если в результате вызова метода набор данных изменился.
void clear () Удаляет из текущего набора данных все элементы.
boolean retainAll (Collection other) Удаляет из набора данных элементы, не совпадающие с теми, которые содержатся в наборе other. Возвращает true, если в результате вызова метода набор данных изменился.
Object[] toArray () Возвращает массив с объектами из набора данных.

Методы итератора java.util.Iterator

Метод Описание
boolean hasNext() Возвращает значение true, если в коллекции имеется следующий элемент, иначе возвращает false
Object next() Возвращает следующий элемент. Если достигнут конец набора,то генерируется исключение NoSuchElementException
void remove() Удаляет последний прочитанный элемент. Этот метод должен быть вызван сразу же после обращения к элементу. Если после чтения элемента набор данных изменился, данный метод генерирует исключение IllegalStateException

Интерфейс ListIterator

Интерфейс Iterator предоставляет ограниченный функционал. Гораздо больший набор методов предоставляет другой итератор — интерфейс ListIterator. Данный итератор используется классами, реализующими интерфейс List, то есть классами LinkedList, ArrayList и др.

Интерфейс ListIterator расширяет интерфейс Iterator и определяет ряд дополнительных методов:

Метод Описание
void add(E obj) Вставляет объект obj перед элементом, который должен быть возвращен следующим вызовом next()
boolean hasNext() Возвращает true, если в коллекции имеется следующий элемент, иначе возвращает false
boolean hasPrevious() Возвращает true, если в коллекции имеется предыдущий элемент, иначе возвращает false
E next() Возвращает следующий элемент, если такого нет, то генерируется исключение NoSuchElementException
E previous() Возвращает предыдущий элемент, если такого нет, то генерируется исключение NoSuchElementException
int nextIndex() Возвращает индекс следующего элемента. Если такого нет, то возвращается размер списка
int previousIndex() Возвращает индекс предыдущего элемента. Если такого нет, то возвращается число -1
void remove() Удаляет текущий элемент из списка. Таким образом, этот метод должен быть вызван после методов next() или previous(), иначе будет сгенерировано исключение IllegalStateException
void set(E obj) Присваивает текущему элементу, выбранному вызовом методов next() или previous(), ссылку на объект obj

Пример использования итератора ListIterator

Иерархия наборов данных интерфейса Collection


На рисунке представлена иерархия наборов классов, реализующих интерфейс Collection:

Список наборов данных

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

Коллекции в Java

категория
Java
дата 27.06.2013
автор vovanok
голосов 185

Алгоритмы + Структуры данных = Программы.
Никлаус Вирт.

Введение

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

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

В данной статье речь пойдет именно о Java Collections Framework, так как существуют многочисленные альтернативы:
1. Guava(Google Collections Library) — Библиотека добавляет несколько полезных реализаций структур данных, таких как мультимножество, мультиотображение и двунаправленное отображение. Улучшена эффективность.
2. Trove library — Реализация коллекций, позволяющая хранить примитивы (в Java Collections Framework примитивы хранить нельзя, только оберточные типы), что позволяет повысить эффективность работы.
3. PCJ(Primitive Collections for Java) — так же как и Trove предназначены для примитивных типов, что позволит повысить эффективность.
4. Наконец Вы сами можете написать собственную коллекцию (тот же связной список). Но данный подход не рекомендуется :)

Как видим, выбрать есть из чего. Но для начала необходимо освоить базовые коллекции Java которыми пользуются чаще всего. А так же некоторые сторонние библиотеки реализуют интерфейсы Java Collections Framework (пример Guava http://guava-libraries.googlecode.com/svn/tags/release05/javadoc/overview-tree.html). То есть знание иерархии классов базовых коллекций позволит более быстро освоить сторонние библиотеки.

Базовые интерфейсы

В библиотеке коллекций Java существует два базовых интерфейса, реализации которых и представляют совокупность всех классов коллекций:

1. Collection — коллекция содержит набор объектов (элементов). Здесь определены основные методы для манипуляции с данными, такие как вставка (add, addAll), удаление (remove, removeAll, clear), поиск (contains)
2. Map — описывает коллекцию, состоящую из пар «ключ — значение». У каждого ключа только одно значение, что соответствует математическому понятию однозначной функции или отображения (тар). Такую коллекцию часто называют еще словарем (dictionary) или ассоциативным массивом (associative array). Никак НЕ относится к интерфейсу Collection и является самостоятельным.

Хотя фреймворк называется Java Collections Framework, интерфейс map и его реализации входят в фреймворк тоже !
Интерфейсы Collection и Map являются базовыми, но они не есть единственными. Их расширяют другие интерфейсы, добавляющие дополнительный функционал. О них мы ещё поговорим.

Интерфейс Collection

Давайте рассмотрим основные интерфейсы, относящиеся к Collection:

Как видно с диаграммы, интерфейс Collection не является базовым (какая интрига :D). Интерфейс Collection расширяет интерфейс Iterable, у которого есть только один метод iterator(). Это значит что любая коллекция, которая есть наследником Iterable должна возвращать итератор.

Итератор(http://ru.wikipedia.org/wiki/%D0%98%D1%82%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80) — объект, абстрагирующийся за единым интерфейсом доступ к элементам коллекции. Итератор это паттерн позволяющий получить доступ к элементам любой коллекции без вникания в суть ее реализации.

Идем дальше. Как видим с рисунка, интерфейс Collection расширяют интерфейсы List, Set и Queue. Давайте рассмотрим, зачем нужен каждый.
1. List — Представляет собой неупорядоченную коллекцию, в которой допустимы дублирующие значения. Иногда их называют последовательностями (sequence ). Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу.
2. Set — описывает неупорядоченную коллекцию, не содержащую повторяющихся элементов. Это соответствует математическому понятию множества (set).
3. Queue — очередь. Сразу запоминаем как правильно произносится: Queue — КЬЮ (http://www.youtube.com/watch?feature=player_embedded&v=ugauQ769kVc#at=22 ). Это коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки. В дополнение к базовым операциям интерфейса Collection, очередь предоставляет дополнительные операции вставки, получения и контроля.

Реализации интерфейса List

Сразу смотрим на иерархию классов.

Красным здесь выделены интерфейсы, зеленым — абстрактные классы, а синим готовые реализации. Сразу хочу заметить что здесь не вся иерархия, а только основная её часть.

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

ArrayList — пожалуй самая часто используемая коллекция. ArrayList инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов.
Так как ArrayList использует массив, то время доступа к элементу по индексу минимально (В отличии от LinkedList). При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево, при этом реальный размер массива (его емкость, capacity) не изменяется. Если при добавлении элемента, оказывается, что массив полностью заполнен, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент.

LinkedList — Двусвязный список. Это структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и две ссылки («связки») на следующий и предыдущий узел списка. Доступ к произвольному элементу осуществляется за линейное время (но доступ к первому и последнему элементу списка всегда осуществляется за константное время — ссылки постоянно хранятся на первый и последний, так что добавление элемента в конец списка вовсе не значит, что придется перебирать весь список в поисках последнего элемента). В целом же, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций.

Часто на собеседованиях спрашивают про отличия ArrayList и LinkedList. И какой когда нужно использовать. См. вопрос собеседования: http://www.quizful.net/interview/java/54AubfnDy6Ti

Реализации интерфейса Set

Смотрим следующую диаграмму. Пытаемся вникнуть :)

HashSet — коллекция, не позволяющая хранить одинаковые объекты(как и любой Set). HashSet инкапсулирует в себе объект HashMap (то-есть использует для хранения хэш-таблицу).
Как большинство читателей, вероятно, знают, хеш-таблица хранит информацию, используя так называемый механизм хеширования, в котором содержимое ключа используется для определения уникального значения, называемого хеш-кодом. Этот хеш-код затем применяется в качестве индекса, с которым ассоциируются данные, доступные по этому ключу. Преобразование ключа в хеш-код выполняется автоматически — вы никогда не увидите самого хеш-кода. Также ваш код не может напрямую индексировать хеш-таблицу. Выгода от хеширования состоит в том, что оно обеспечивает константное время выполнения методов add(), contains(), remove() и size() , даже для больших наборов.

Если Вы хотите использовать HashSet для хранения объектов СВОИХ классов, то вы ДОЛЖНЫ переопределить методы hashCode() и equals(), иначе два логически-одинаковых объекта будут считаться разными, так как при добавлении элемента в коллекцию будет вызываться метод hashCode() класса Object (который скорее-всего вернет разный хэш-код для ваших объектов).
Важно отметить, что класс HashSet не гарантирует упорядоченности элементов, поскольку процесс хеширования сам по себе обычно не порождает сортированных наборов. Если вам нужны сортированные наборы, то лучшим выбором может быть другой тип коллекций, такой как класс TreeSet.

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

TreeSet — коллекция, которая хранит свои элементы в виде упорядоченного по значениям дерева. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n).

Реализации интерфейса Queue

Здесь я привел очень упрощенную иерархию.

PriorityQueue — единственная прямая реализация интерфейса Queue (не считая LinkedList, который больше является списком, чем очередью).
Эта очередь упорядочивает элементы либо по их натуральному порядку (используя интерфейс Comparable), либо с помощью интерфейса Comparator, полученному в конструкторе.

Реализации интерфейса Map

Интерфейс Map соотносит уникальные ключи со значениями. Ключ — это объект, который вы используете для последующего извлечения данных. Задавая ключ и значение, вы можете помещать значения в объект карты. После того как это значение сохранено, вы можете получить его по ключу. Интерфейс Map — это обобщенный интерфейс, объявленный так, как показано ниже.

Здесь К указывает тип ключей, а V — тип хранимых значений.

Иерархия классов очень похожа на иерархию Set’а:

HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Хорошая статья http://habrahabr.ru/post/128017/

LinkedHashMap — расширяет класс HashMap. Он создает связный список элементов в карте, расположенных в том порядке, в котором они вставлялись. Это позволяет организовать перебор карты в порядке вставки. То есть, когда происходит итерация по коллекционному представлению объекта класса LinkedHashMap, элементы будут возвращаться в том порядке, в котором они вставлялись. Вы также можете создать объект класса LinkedHashMap, возвращающий свои элементы в том порядке, в котором к ним в последний раз осуществлялся доступ.
Рекомендую так же прочитать http://habrahabr.ru/post/129037/

TreeMap — расширяет класс AbstractMap и реализует интерфейс NavigatebleMap. Он создает коллекцию, которая для хранения элементов применяет дерево. Объекты сохраняются в отсортированном порядке по возрастанию. Время доступа и извлечения элементов достаточно мало, что делает класс TreeMap блестящим выбором для хранения больших объемов отсортированной информации, которая должна быть быстро найдена.
Моя статья про TreeMap http://www.quizful.net/post/Java-TreeMap

WeakHashMap — коллекция, использующая слабые ссылки для ключей (а не значений). Слабая ссылка (англ. weak reference) — специфический вид ссылок на динамически создаваемые объекты в системах со сборкой мусора. Отличается от обычных ссылок тем, что не учитывается сборщиком мусора при выявлении объектов, подлежащих удалению. Ссылки, не являющиеся слабыми, также иногда именуют «сильными».
http://ru.wikipedia.org/wiki/%D0%A1%D0%BB%D0%B0%D0%B1%D0%B0%D1%8F_%D1%81%D1%81%D1%8B%D0%BB%D0%BA%D0%B0

Устаревшие коллекции

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

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());

Синхронизированные обрамления коллекций synchronizedMap и synchronizedList иногда называют условно потоко безопасными — все операции в отдельности потоко безопасны, но последовательности операций, где управляющий поток зависит от результатов предыдущих операций, могут быть причиной конкуренции за данные.
(источник http://www.ibm.com/developerworks/ru/library/j-jtp07233/)
Условная безопасность потоков, обеспечиваемая synchronizedList и synchronizedMap представляет скрытую угрозу — разработчики полагают, что, раз эти коллекции синхронизированы, значит, они полностью потоко безопасны, и пренебрегают должной синхронизацией составных операций. В результате, хотя эти программы и работают при лёгкой нагрузке, но при серьёзной нагрузке они могут начать выкидывать NullPointerException или ConcurrentModificationException.

Кроме того всегда существует возможность «классической» синхронизации с помощью блока synchronized.

Цукерберг рекомендует:  Objective c - iOS - Работа приложения в фоновом режиме

Собираем все воедино

Итак, смотрим на получившейся диаграмму классов:

Как видим диаграмма достаточно массивная. Но такая архитектура считается эталонной в OOП.

Заключение

Надеюсь эта статья была вам полезной. Если в комментариях наберётся достаточно пожеланий, я напишу вторую часть статьи, где приведу примеры использования всех этих коллекций. (Представьте только: на собеседовании вас спрашивают про иерархию коллекций в java, а Вы им рисуете предыдущий рисунок. Как они будут удивлены :D)
Спасибо за внимание .

Если Вам понравилась статья, проголосуйте за нее

Какую коллекцию Java я должен использовать?

В этом вопросе Как я могу эффективно выбрать контейнер стандартной библиотеки в С++ 11? — удобная блок-схема, используемая при выборе коллекций С++.

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

Какие ресурсы и «чит-листы» доступны, чтобы помочь людям выбрать нужную коллекцию для использования при программировании на Java? Как люди знают, какие реализации List, Set и Map они должны использовать?

Поскольку я не мог найти подобную блок-схему, я решил сделать ее сам.

В этой блок-схеме не рассматриваются и такие функции, как синхронизированный доступ, безопасность потоков и т.д. или устаревшие коллекции, но он охватывает 3 стандартных Установить, 3 стандартных Карта s и 2 стандартных Список.

Это изображение было создано для этого ответа и лицензировано по лицензии Creative Commons Attribution 4.0. Простейшая атрибуция заключается в ссылке на этот вопрос или на этот ответ.

Другие ресурсы

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

HashSet vs TreeSet

Существует подробное обсуждение того, когда следует использовать HashSet или TreeSet здесь: Hashset vs Treeset

ArrayList vs LinkedList

Сводка основных не параллельных, несинхронизированных коллекций

Collection : интерфейс, представляющий неупорядоченную «сумку» предметов, называемых «элементами». Следующий элемент не определен (случайно).

  • Set: интерфейс, представляющий Collection без дубликатов.
    • HashSet: Set поддерживаемый Hashtable . Самое быстрое и наименьшее использование памяти при заказе неважно.
    • LinkedHashSet: HashSet с добавлением связанного списка для связывания элементов в порядке вставки. Элемент «следующий» — это следующий за последним вставленный элемент.
    • TreeSet: Set котором элементы упорядочены Comparator (обычно естественное упорядочение). Медленное и самое большое использование памяти, но необходимое для упорядочения на основе компаратора.
    • EnumSet: чрезвычайно быстрый и эффективный Set настроенный для одного типа перечисления.
  • List: Интерфейс, представляющий Collection , элементы которой упорядочены, и каждый имеет числовой индекс, представляющий его позицию, где ноль — первый элемент, а (length — 1) — последний.
    • ArrayList: List поддерживаемый массивом, где массив имеет длину (называемую «емкость»), которая по крайней мере равна числу элементов (список «размер»). Когда размер превышает емкость (когда (capacity + 1)-th элемент (capacity + 1)-th ), массив воссоздается с новой емкостью (new length * 1.5) — -th — это быстрое восстановление, поскольку он использует System.arrayCopy() . Удаление и вставка/добавление элементов требует, чтобы все соседние элементы (справа) были сдвинуты в или из этого пространства. Доступ к любому элементу быстрый, так как требуется только вычисление (element-zero-address + desired-index * element-size) чтобы найти его местоположение. В большинстве ситуаций ArrayList предпочтительнее, чем LinkedList .
    • LinkedList: List поддерживаемый набором объектов, каждый из которых связан со своими «предыдущими» и «следующими» соседями. LinkedList — это также Queue и Deque . Доступ к элементам осуществляется начиная с первого или последнего элемента и проходя до достижения желаемого индекса. Вставка и удаление, как только требуемый индекс достигнут с помощью обхода, является тривиальным вопросом переотображения только непосредственных соседних ссылок для указания на новый элемент или обхода теперь удаленного элемента.
  • Map: интерфейс, представляющий Collection где каждый элемент имеет идентифицирующий элемент «ключ» —each является парой ключ-значение.
    • HashMap: Map где ключи неупорядочены и поддерживаются Hashtable .
    • LinkedhashMap: ключи упорядочены по порядку вставки.
    • TreeMap: Map где ключи упорядочены Comparator (обычно естественное упорядочение).
  • Queue: интерфейс, представляющий Collection которой элементы обычно добавляются к одному концу и удаляются из другого (FIFO: первым пришел, первым вышел).
  • Stack: интерфейс, представляющий Collection которой элементы, как правило, одновременно добавляются (помещаются) и удаляются (извлекаются) с одного и того же конца (LIFO: последний пришел, первый вышел).
  • Deque: Сокращение от «двусторонней очереди», обычно произносится как «колода». Связанный список, который обычно добавляется и читается только с любого конца (но не с середины).

Основные диаграммы коллекции:

Сравнение вставки элемента с ArrayList и LinkedList :

Для чего нужны коллекции в программировании?

Для чего нужны коллекции? Списки, очереди, наборы?

Что в них можно хранить?

Можете пожалуйста дать ссылки примеров работы с коллекциями?

1 ответ 1

Что-то какой-то ответ предыдущего оратора слишком краткий, на мой вкус. И статья на мой вкус не самая «вкусная».

Для чего нужны коллекции? > списки,очереди,и наборы?

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

Очередь с приоритетом часто используется для сортировки массива и для нахождения максимума\минимума.

Набор set — упорядоченное множество. Коллекции Set предназначены для хранения множества не повторяющихся объектов. Таким образом при добавление двух элементов с одинаковым значением в коллекцию, с интерфейсом Set , коллекции это воспримут за один элемент. Каждый объект который вы добавите в коллекцию set получит свой уникальный хэш-код, то есть строку по которой можно будет осуществить доступ к нему. Пример использования Set — пусть вы пишите базу данных по автомобильным номерам. Там не допустима ситуация, когда у двух машин один номер. Именно set по скорости работы (поиска и добавления) в этом плане окажется эффективнее других структур данных.

Что в них можно хранить(и как?примеры)?

Про то как примерно хранить. Я давал нечто, похожее на ответ в другом вопросе.

Если вам вздумается экономить время в изучении вопроса с коллекциями, я шибко рекомендую посмотреть примеры в формате скринкастов на ютьюбе. ИМХО это отличные практические занятия для каждого. Мне больше всего по коллекциям понравилось это:

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

PS. Если материал кажется вам не полным вы можете задать дополнительные вопросы, типа примеров работы c каждой конкретной коллекцией. Ибо в одном ответе довольно трудно всё кратко прояснить.

Java – все, что нужно знать о коллекциях

Java Collections Framework это коллекция интерфейсов и классов, которые используются для сохранения и обработки данных.

Java Collections Framework состоит из следующих компонентов:

  • List это упорядоченный список объектов (иногда еще называют последовательностью объектов). Элементы списка могут вставляться или извлекаться по их индексу в списке (индексация начинается с 0). В эту группу входят: ArrayList , LinkedList , Vector , Stack .
  • Set это не упорядоченная коллекция. Главная особенность множеств — уникальность элементов, то есть один и тот же элемент не может содержаться в множестве дважды. Есть такие имплементации Set интерфейса: HashSet , TreeSet , LinkedHashSet , EnumSet . HashSet хранит элементы в хэш-таблице, что предполагает эффективную реализацию, но не гарантирует порядок итерации элементов. TreeSet хранит элементы в красно-чёрном дереве и упорядочивает элементы по их значениям, эта коллекция существено медленее чем HashSet . LinkedHashSet реализована как хэш-таблица и хранит элементы в связаном списке, в порядке котором они были вставленны.
  • Map (иногда можно встретить названия: отображения, словарь, ассоциативный массив, карты) отображает ключи в значения и не может иметь дубликаты ключей. Есть три основных имплементации Map интерфейса HashMap , TreeMap и LinkedHashMap . HashMap не гарантирует воспроизводимость порядка вставки элементов. TreeMap хранит элементы в красно-чёрном дереве и упорядычивает элементы по их ключам и медленее чем HashMap . LinkedHashMap упорядычивает элементы в порядке их вставки.
  • Iterator / ListIterator используются для итерации элементов коллекции. Основное отличие между Iterator и ListIterator в том, что первый позволяет итерировать только в одном направлении, а второй в обоих направлениях.

Выше сказаное можно резюмировать в такой таблице

Производительность методов каждого класса можно записать через O-нотацию

Метод Тип Время
get, set ArrayList O(1)
add, remove ArrayList O(n)
contains, indexOf ArrayList O(n)
get, put, remove, containsKey HashMap O(1)
add, remove, contains HashSet O(1)
add, remove, contains LinkedHashSet O(1)
get, set, add, remove (с любого конца) LinkedList O(1)
get, set, add, remove (по индексу) LinkedList O(n)
contains, indexOf LinkedList O(n)
peek PriorityQueue O(1)
add, remove PriorityQueue O(log n)
remove, get, put, containsKey TreeMap O(log n)
add, remove, contains TreeSet O(log n)

ArrayList

ArrayList это массив с изменяемым количесвтом элементов (стандартный array имеет фиксированый размер), его элементы могут быть доступны непосредственно по индексу. Он реализует все операции списка и позволят вставлять все объекты, включая null . Контейнер ArrayList , оптимизированный для произвольного доступа к элементам, но с относительно медленными операциями вставки/удаления элементов в середине списка.

В случае переполнения массива появляется необходимость в новом, имеющем больше места. Размещение и перемещение всех элементов будет занимать O(n) времени. Также, необходимо добавление и удаление элементов для передвижения существующих элементов в массиве. Это, возможно, самое большое неудобство в использовании ArrayList .

Поиск в ArrayList проходит за O(1). Удаление первого элемента (худший случай) происходит за O(n), для последнего элемента (лучший случай) за O(1). Вставка происходит за O(n).

LinkedList

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

Контейнер LinkedList , оптимизированный для последовательного доступа, с быстрыми операциями вставки/удаления в середине списка. Произвольный доступ к элементам LinkedList выполняется относительно медленно, т.к. требует полного перебора элементов. Класс представляет структуру данных связного списка и реализует интерфейсы List , Dequeue , Queue .

Поиск в LinkedList проходит за O(n). Удаление происходит за O(1). Вставка происходит за O(1).

Сравнение LinkedList и ArrayList по скорости операций:

Метод Arraylist LinkedList
get(index) O(1) O(n)
add(E) O(n) O(1)
add(E, index) O(n) O(n)
remove(index) O(n) O(n)
Iterator.remove() O(n) O(1)
Iterator.add(E) O(n) O(1)

Сравнеие производительности Arraylist и LinkedList

Vector

Vector это динамический массив, похожий на ArrayList , за исключением двух моментов: Vector синхронизирован (потоко-безопасен) и Vector содержит много legacy-методов. По умолчанию, Vector удваивает свой размер когда заканчивается выделенная под элементы память. ArrayList же увеличивает свой размер только на половину.

Stack

Стэк является подкласом Vector и работает по принципу LIFO (last-in-first-out rule) — последним пришел, первым ушел. Обратите внимание, что Stack и Vector оба потокобезопасны. Используйте стэк если вы хотите вставлять и удалять элементы только с вершины стэка, что полезно в рекурсивных алгоритмах.

HashSet , TreeSet и LinkedHashSet относятся к семейству Set . В множествах Set каждый элемент хранится только в одном экземпляре, а разные реализации Set используют разный порядок хранения элементов. В HashSet порядок элементов определяется по сложному алгоритму и не гарантирует порядок в котором элементы вставлялись. Если порядок хранения для вас важен, используйте контейнер TreeSet , в котором объекты хранятся отсортированными по возрастанию в порядке сравнения или LinkedHashSet с хранением элементов в порядке добавления.

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

Сравним времени на операцию add() для HashSet , TreeSet , LinkedHashSet .

HashSet

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

  1. HashSet не поддерживает порядок своих элементов, а это значит, что элементы будут возвращены в любом порядже.
  2. HashSet не разрешает хранить дубликаты. Если вы добавите существующий элемент, то старое значение будет переписано.
  3. HashSet разрешает добавить в колекцию null значение, но только одно значение.
  4. HashSet не синхронизировано.

LinkedHashSet

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

TreeSet

TreeSet реализует интерфейс SortedSet .

Класс TreeSet создаёт коллекцию, которая для хранения элементов использует дерево. Объекты сохраняются в отсортированном порядке по возрастанию.

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

TreeSet не поддерживает хранение элементов типа null .

NavigableSet

Интерфейс NavigableSet наследуется от SortedSet и предоставляет возможность навигации по множеству в обоих направлениях.

Очереди предствляют собой упорядоченый список элементов, т.к. реализуют интерфейс List , но есть особености использования. Элементы вставляются в конец очереди, а извлекаются из начала очереди. Обычно, но не обязательно, очереди работают по принципу FIFO — первым пришел, первым ушел.

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

Queue

В Java Collections API интерфейс Queue реализован в

  • LinkedList — реализует принцип FIFO.
  • PriorityQueue — хранит элементы либо в естественном порядке (natural order) либо в соответсвии с Comparator , переданым в конструктор.

Deque

Deque (Double Ended Queues) это двухсторонняя очередь, которая позволяет вставлять/удалять элементы как с конца очереди, так и с начала. Deque интерфейс расширяет Queue интерфейс.

В Java Collections API интерфейс Deque реализован в

  • ArrayDeque — базируется на массиве и используется при реализации стэка (принцип LIFO).
  • LinkedList — базируется на двух-связном списке и используется при реализации очереди (принцип FIFO).

В контейнерах Map (отображения, словарь, ассоциативный массив, карты) хранятся два объекта: ключ и связанное с ним значение. Map позволяет искать объекты по ключу. Объект, ассоциированный с ключом, называется значением. И ключи, и значения являются объектами. Ключи могут быть уникальными, а значения могут дублироваться. Некоторые отображения допускают пустые ключи и пустые значения.

Интерфейс Map соотносит уникальные ключи со значениями. Ключ — это объект, который вы используете для последующего извлечения данных. Задавая ключ и значение, вы можете помещать значения в объект отображения. После того как это значение сохранено, вы можете получить его по ключу.

Основные методы — get() и put() , чтобы получить или поместить значения в отображение.

Интерфейс Map предоставляет три представления (view) хранящихся данных:

  • множество всех ключей
  • множество всех значений
  • множество объектов Entry , содержащих в себе и ключ и значение

Отображения не поддерживают реализацию интерфейса Iterable , поэтому нельзя перебрать карту через цикл for в форме for-each . Можно перебрать отдельно ключи или значения или объекти Entry .

Интерфейс SortedMap расширяет интерфейс Map и гарантирует, что элементы размещаются в возрастающем порядке значений ключей.

Интерфейс NavigableMap расширяет интерфейс SortedMap и определяет поведение отображения, поддерживающее извлечение элементов на основе ближайшего соответствия заданному ключу или ключам.

Интерфейс Map.Entry позволяет работать с элементом отображения, в частности используется при переборе элементов. Основные мотеды интерфейса Map.Entry

  • equals(Object o) сравнение на равенство двух элементов
  • getKey() получить ключ элемента
  • getValue() получить значение элемента
  • hashCode() получить хэш-код элемента
  • setValue(V value) замена значения элемента на value

HashMap

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

HashMap подобен Hashtable с нескольками исключениямия:

  • HashTable потокобезопасна, а HashMap нет
  • HashTable не может содержать элементы null , тогда как HashMap может содержать один ключ null и любое количество значений null
  • Итератор у HashMap , в отличие от перечислителя HashTable , работает по принципу fail-fast (выдает исключение при любой несогласованности данных)

TreeMap

TreeMap реализует Map интерфейс с помощью структуры красно-чёрного дерева и хранит ключи отсортированными по возрастанию (естественный порядок, natural order). Переопределить сортировку можно предоставив экземпляр класса Comparator , метод compare которого и будет использован для сортировки ключей. Обратите внимание, что все ключи добавленные в словарь должны реализовывать интерфейс Comparable (это необходимо для сортировки).

TreeMap предоставляет быстрый доступ к своим элементам.

Для вставки, удаления и поиска элементов в Map лучше использовать HashMap . Если же нужно последовательно обходить карты в неком порядке то лучше использовать TreeMap . Иногда, в зависимости от размера коллекции, лучше добавить элементы в HashMap , а потом сконвертировать в TreeMap для упорядоченого обхода элементов.

LinkedHashMap

LinkedHashMap реализует связанный список элементов отображения и хранит ключи в порядке вставки. Также позволяет сортировать элементы в порядке последнего доступа. LinkedHashMap не обеспечивает скорость поиска как HashMap .

Различия между Iterator и ListIterator?

  • Iterator может использоваться для перебора элементов Set , List и Map . В отличие от него, ListIterator может быть использован только для перебора элементов коллекции List .
  • Iterator позволяет перебирать элементы только в одном направлении, при помощи метода next() . Тогда как ListIterator позволяет перебирать список в обоих направлениях, при помощи методов next() и previous() .
  • При помощи ListIterator вы можете модифицировать список, добавляя/удаляя элементы с помощью методов add() и remove() . Iterator не поддерживает данного функционала.
Понравилась статья? Поделиться с друзьями:
Все языки программирования для начинающих