Что такое collection framework

Collections Framework Overview

Introduction

The primary advantages of a collections framework are that it:

The collections framework consists of:

Collection Interfaces

The collection interfaces are divided into two groups. The most basic interface, java.util.Collection, has the following descendants:

The other collection interfaces are based on java.util.Map and are not true collections. However, these interfaces contain collection-view operations, which enable them to be manipulated as collections. Map has the following offspring:

Many of the modification methods in the collection interfaces are labeled optional. Implementations are permitted to not perform one or more of these operations, throwing a runtime exception (UnsupportedOperationException) if they are attempted. The documentation for each implementation must specify which optional operations are supported. Several terms are introduced to aid in this specification:

Some implementations restrict what elements (or in the case of Maps, keys and values) can be stored. Possible restrictions include requiring elements to:

Attempting to add an element that violates an implementation’s restrictions results in a runtime exception, typically a ClassCastException, an IllegalArgumentException, or a NullPointerException. Attempting to remove or test for the presence of an element that violates an implementation’s restrictions can result in an exception. Some restricted collections permit this usage.

Collection Implementations

The general-purpose implementations support all of the optional operations in the collection interfaces and have no restrictions on the elements they may contain. They are unsynchronized, but the Collections class contains static factories called synchronization wrappers that can be used to add synchronization to many unsynchronized collections. All of the new implementations have fail-fast iterators, which detect invalid concurrent modification, and fail quickly and cleanly (rather than behaving erratically).

The AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList and AbstractMap classes provide basic implementations of the core collection interfaces, to minimize the effort required to implement them. The API documentation for these classes describes precisely how each method is implemented so the implementer knows which methods must be overridden, given the performance of the basic operations of a specific implementation.

Concurrent Collections

Applications that use collections from more than one thread must be carefully programmed. In general, this is known as concurrent programming. The Java platform includes extensive support for concurrent programming. See Java Concurrency Utilities for details.

Collections are so frequently used that various concurrent friendly interfaces and implementations of collections are included in the APIs. These types go beyond the synchronization wrappers discussed previously to provide features that are frequently needed in concurrent programming.

These concurrent-aware interfaces are available:

The following concurrent-aware implementation classes are available. See the API documentation for the correct usage of these implementations.

Design Goals

The main design goal was to produce an API that was small in size and, more importantly, in «conceptual weight.» It was critical that the new functionality not seem too different to current Java programmers; it had to augment current facilities, rather than replace them. At the same time, the new API had to be powerful enough to provide all the advantages described previously.

To keep the number of core interfaces small, the interfaces do not attempt to capture such subtle distinctions as mutability, modifiability, and resizability. Instead, certain calls in the core interfaces are optional, enabling implementations to throw an UnsupportedOperationException to indicate that they do not support a specified optional operation. Collection implementers must clearly document which optional operations are supported by an implementation.

To keep the number of methods in each core interface small, an interface contains a method only if either:

It was critical that all reasonable representations of collections interoperate well. This included arrays, which cannot be made to implement the Collection interface directly without changing the language. Thus, the framework includes methods to enable collections to be moved into arrays, arrays to be viewed as collections, and maps to be viewed as collections.

Источник

Collections Framework Overview

Introduction

The primary advantages of a collections framework are that it:

The collections framework consists of:

Collection Interfaces

The collection interfaces are divided into two groups. The most basic interface, java.util.Collection, has the following descendants:

The other collection interfaces are based on java.util.Map and are not true collections. However, these interfaces contain collection-view operations, which enable them to be manipulated as collections. Map has the following offspring:

Many of the modification methods in the collection interfaces are labeled optional. Implementations are permitted to not perform one or more of these operations, throwing a runtime exception (UnsupportedOperationException) if they are attempted. The documentation for each implementation must specify which optional operations are supported. Several terms are introduced to aid in this specification:

Some implementations restrict what elements (or in the case of Maps, keys and values) can be stored. Possible restrictions include requiring elements to:

Attempting to add an element that violates an implementation’s restrictions results in a runtime exception, typically a ClassCastException, an IllegalArgumentException, or a NullPointerException. Attempting to remove or test for the presence of an element that violates an implementation’s restrictions can result in an exception. Some restricted collections permit this usage.

Collection Implementations

The general-purpose implementations support all of the optional operations in the collection interfaces and have no restrictions on the elements they may contain. They are unsynchronized, but the Collections class contains static factories called synchronization wrappers that can be used to add synchronization to many unsynchronized collections. All of the new implementations have fail-fast iterators, which detect invalid concurrent modification, and fail quickly and cleanly (rather than behaving erratically).

The AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList and AbstractMap classes provide basic implementations of the core collection interfaces, to minimize the effort required to implement them. The API documentation for these classes describes precisely how each method is implemented so the implementer knows which methods must be overridden, given the performance of the basic operations of a specific implementation.

Concurrent Collections

Applications that use collections from more than one thread must be carefully programmed. In general, this is known as concurrent programming. The Java platform includes extensive support for concurrent programming. See Java Concurrency Utilities for details.

Collections are so frequently used that various concurrent friendly interfaces and implementations of collections are included in the APIs. These types go beyond the synchronization wrappers discussed previously to provide features that are frequently needed in concurrent programming.

These concurrent-aware interfaces are available:

The following concurrent-aware implementation classes are available. See the API documentation for the correct usage of these implementations.

Design Goals

The main design goal was to produce an API that was small in size and, more importantly, in «conceptual weight.» It was critical that the new functionality not seem too different to current Java programmers; it had to augment current facilities, rather than replace them. At the same time, the new API had to be powerful enough to provide all the advantages described previously.

To keep the number of core interfaces small, the interfaces do not attempt to capture such subtle distinctions as mutability, modifiability, and resizability. Instead, certain calls in the core interfaces are optional, enabling implementations to throw an UnsupportedOperationException to indicate that they do not support a specified optional operation. Collection implementers must clearly document which optional operations are supported by an implementation.

To keep the number of methods in each core interface small, an interface contains a method only if either:

It was critical that all reasonable representations of collections interoperate well. This included arrays, which cannot be made to implement the Collection interface directly without changing the language. Thus, the framework includes methods to enable collections to be moved into arrays, arrays to be viewed as collections, and maps to be viewed as collections.

Источник

Немного о Java Collections Framework. Часть 1

В англоязычном сегменте сети достаточно много статьей по этой теме. Чаще всего они несут поверхностный, ознакомительный характер и иногда довольно сложно из-за языкового барьера уловить суть изучаемой темы. Надеюсь, наше небольшое путешествие в Java Collections Framework принесет вам некоторое разъяснение. Чем больше предметной информации, тем легче собрать всю мозаику воедино, отбрасывая не понятные выкладки и описания. Для более эффективного изучения количество примеров является критичным. Так же дело обстоит и с коллекциями, обойдем стороной интерфейсы, и перейдем сразу к классам, их реализующие.

Класс ArrayList

«Не стоит недооценивать важность метафор. Метафоры имеют одно неоспоримое достоинство: описываемое ими поведение предсказуемо и понятно всем людям…”.
Фернандо Дж. Корбати.

Я полностью согласен с Фернандо Дж. Корбати о важности метафор в изучение определённой предметной области. Так как программирование является смесью математики и искусства, использование метафор имеет наивысший приоритет. Для объяснения сути назначения ArrayList мы будем использовать «Транспортную» метафору. Представьте, что это обычный массив, похожий на семейный автомобиль, купленный с расчётом на количество членов семьи.

Если у нашей семьи родиться ещё один ребёнок, то придется покупать более вместительный автомобиль. Предположим, родители заведомо не знают, сколько детей у них будет и какой ещё вместимости необходим новый автомобиль. Есть вероятность прогадать и зря потратить сбережения. Так вот, ArrayList подобна городскому транспорту. Здесь нет ограничений в вместимости. Каждый в состоянии доехать из пункта A в пункт B. Поэтому если отец семейства не уверен или не знает о количестве будущих детей, он выберет городской транспорт, или в нашем случае ArrayList. Данный класс имеет три конструктора, мы будем разбирать самый простой. Давайте напишем код.

Вывод программы на консоль:
[1, 2, 3]
[1, 2]

Программа очень интуитивно понятна и проста, но давайте немного копнем глубже и взглянем изнутри, как всё работает. Во-первых, класс ArrayList является обобщенным, относительно нашего объявления, мы должны работать с объектами класса Integer. Однако судя по коду программы этого не происходит. Установим breakpoint на строку: запустим Debug и войдем в метод(Step Into). Если всё прошло успешно, то обнаружим следующий код.

Как видите, имя метода не совпадает с тем методом, в который мы входили, плюс ко всему мы оказались в классе Integer. Обратим наше внимание на строку:

Это и есть знаменитая „Autoboxing Java“, из простого int в объект класса Integer. Теперь всё встало на свои места и вписывается в картину объявления обобщенного класса ArrayList. Далее рассмотрим метод добавления элемента в коллекцию.

Данный метод не только записывает элемент в коллекцию, но и поддерживает „транспортную“ метафору путем увеличение вместимости массива при определенном условие. Жесткая связь между оператором return и возвращаемым булевым значением true, говорит нам о том, что если возникнет исключительная ситуация, выполнение прервётся. Устойчивость метода оставляет желать лучшего.

Вернемся опять к нашему исходному коду. И рассмотрим следующие строку кода:

Возникает вопрос, если взять в расчет авто упаковку, какой элемент удалится? По выводу на консоль мы ясно видим, что это будет 3. Итак, что-то пошло не так. Исследуя класс ArrayList, в окне Outline обнаруживаем два одинаковых имени вызываемого метода.

Рассмотрим первый метод и определим его назначение:

Беглым анализом можно определить, что метод копирует одну часть относительно значения переменой numMoved одного и того же массива в другую позицию(index+1, index). То есть затирание и есть удаление элемента массива по его индексу, при этом старое значение возвращается методом и метка конца (null) массива перезаписывается заново, относительно новых смещений. Определённо, в нашей программе вызывается именно данный метод и авто упаковка не происходит. В противном случае после авто упаковки удалился бы элемент 2, а не элемент из массива на позиции [2]. Для ясности проверим код другой версии метода remove().

Если соответствующий элемент будет обнаружен, он будет незамедлительно удален из массива. Для наглядности видоизменим строку удаления элемента, передав в качестве аргумента адрес на объект класс Integer:

Вывод программы на консоль:
[1, 2, 3]
[1, 3]

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

Кстати, если посмотреть внимательно, то в обоих методах удаления элемента, используется native метод System.arraycopy(), очень быстро копирующий одну часть памяти в другую.

Java Native Interface.
Native methods-methods used by a Java program but written in a different language-have been in the JDK since the beginning. As promised, the native methods interface from 1.0 has been completely rewritten and formalized. This interface is now named the Java Native Interface, or JNI for short.

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

Объект IdCustomer сам предоставляет строку в виде коллекции, для этого управление передаётся его внутреннему переопределенному методу toString(). Используя Debug мы можем сразу войти в тело метода или пойти другим путем и отыскать его в иерархии классов:

Проанализировав код, мы можем выделить три составные части.

Источник

Готовимся к собеседованию: что нужно знать о коллекциях в Java

Освежаем знания о коллекциях в Java и закрепляем их на практике.

Коллекции в Java — одна из любимых тем на собеседованиях Java-разработчиков любого уровня. Без них не обходятся и экзамены на сертификат Java Professional.

Вспомним основные типы коллекций, их реализации в Java, проверим понимание на практике.

Что такое коллекции

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

Инструменты для работы с такими структурами в Java содержатся в Java Collections Framework. Фреймворк состоит из интерфейсов, их реализаций и утилитарных классов для работы со списками: сортировки, поиска, преобразования.

Фулстек-разработчик. Любимый стек: Java + Angular, но в хорошей компании готова писать хоть на языке Ада.

Галопом по Европам, или Кратко об интерфейсах

Set — это неупорядоченное множество уникальных элементов.

Например, мешочек с бочонками для игры в лото: каждый номер от 1 до 90 встречается в нём ровно один раз, и заранее неизвестно, в каком порядке бочонки вынут при игре.

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

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

Queue — очередь. В таком списке элементы можно добавлять только в хвост, а удалять — только из начала. Так реализуется концепция FIFO ( first in, first out) — «первым пришёл — первым ушёл». Вам обязательно напомнят это правило, если попробуете пролезть без очереди в магазине:

А ещё есть LIFO (last in, first out), то есть «последним пришёл — первым ушёл». Пример — стопка рекламных буклетов на ресепшене отеля: первыми забирают самые верхние (положенные последними). Структуру, которая реализует эту концепцию, называют стеком.

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

Будет здорово, если на собеседовании вы назовёте Deque правильно: «дэк», а не «д экью», как часто говорят.

Map состоит из пар «ключ-значение». Ключи уникальны, а значения могут повторяться. Порядок элементов не гарантирован. Map позволяет искать объекты (значения) по ключу.

Пример: стопка карточек с иностранными словами и их значениями. Для каждого слова (ключ) на обороте карточки есть вариант перевода (значение), а вытаскивать карточки можно в любом порядке.

Не путайте интерфейс Collection и фреймворк Collections. Map не наследуется от интерфейса Collection, но входит в состав фреймворка Collections.

Соберём всё вместе

❌ для ключейСохраняется порядок добавления❌✅✅❌

Такие разные реализации

Реализаций интерфейсов так много, что при желании можно организовать вполне себе упорядоченный Map и даже отсортированное множество. Пройдёмся кратко по основным классам.

Реализации List

Класс ArrayList подойдёт в большинстве случаев, если вы уже определились, что вам нужен именно список (а не Map, например).

Строится на базе обычного массива. Если при создании не указать размерность, то под значения выделяется 10 ячеек. При попытке добавить элемент, для которого места уже нет, массив автоматически расширяется — программисту об этом специально заботиться не нужно.

Список проиндексирован. При включении нового элемента в его середину все элементы с б ольшим индексом сдвигаются вправо:

При удалении элемента все остальные с бо́льшим индексом сдвигаются влево:

Класс LinkedList реализует одновременно List и Deque. Это список, в котором у каждого элемента есть ссылка на предыдущий и следующий элементы:

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

На собеседованиях часто спрашивают, когда выгоднее использовать LinkedList, а когда — ArrayList.

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

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

Реализации Queue

Про одну из них, LinkedList, мы рассказали выше.

Класс ArrayDeque — это реализация двунаправленной очереди в виде массива с переменным числом элементов.

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

Класс PriorityQueue — упорядоченная очередь. По умолчанию элементы добавляются в естественном порядке: числа по возрастанию, строки по алфавиту и так далее, либо алгоритм сравнения задаёт разработчик.

Этот класс может быть полезен, например, для нахождения n минимальных чисел в большом неупорядоченном списке:

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

Реализации Set

Класс HashSet использует для хранения данных в хеш-таблице. Это значит, что при манипуляциях с элементами используется хеш-функция — hashCode() в Java.

Хеш-таблица — структура данных, в которой все элементы помещаются в бакеты (buckets), соответствующие результату вычисления хеш-функции.

Например, администратор в гостинице может класть ключ в коробку с номером от 1 до 9, вычисляя его по такому алгоритму: складывать все цифры номера, пока не получится одноразрядное число.

Здесь алгоритм вычисления — хеш-функция, а результат вычисления — хеш-код.

Тогда ключ от номера 356 попадёт в коробку 5 (3 + 5 + 6 = 14; 1 + 4 = 5), а ключ от номера 123 — в коробку с номером 6.

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

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

Реализации Map

Класс HashMap хранит данные в виде хеш-таблицы, как и HashSet. Более того, HashSet внутри использует HashMap. При этом ключом выступает сам элемент.

Класс TreeMap строится тоже на базе красно-чёрного дерева. Элементы здесь упорядочены (в естественном или заданном при создании порядке) в каждый момент времени. При этом вставка и удаление более затратны, чем в случае с HashMap.

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

Ещё один хитрый вопрос на собеседовании: в каких коллекциях допускаются null-элементы?

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

Обоснование: мух советуют отделять от котлет — иными словами, нельзя сравнивать принципиально разные, несопоставимые вещи. Так же и в Java невозможно понять, что больше: null или число 1, или null или строка «hello».

Поэтому null-значения запрещены в TreeMap и TreeSet.

Ещё они недопустимы в ArrayDeque, так как методы этого класса (например, poll() — удаление элемента из начала очереди) используют null как признак пустоты коллекции.

Попрактикуемся

Чтобы убедиться, что вы не просто вызубрили теорию, а хорошо понимаете предмет, на собеседовании вам могут предложить задания вроде «что произойдёт при выполнении кода»

Разберём типовые задачи на понимание коллекций.

Задачи для ArrayList

Что будет напечатано после выполнения кода ниже:

Правильный ответ: test2:test4:test1:test4:test2:test3:

Элементы в ArrayList нумеруются начиная с нуля. Поэтому элемент с номером 1 — это test2.

Следующим действием мы добавляем строку «test4» в ячейку с индексом 1. При этом элементы с бо́льшим индексом сдвигаются вправо.

Вторая часть вывода ( test4) показывает, что теперь по индексу 1 извлекается именно test4.

Далее мы обходим все элементы списка и убеждаемся, что они выводятся именно в порядке добавления.

Что будет выведено при выполнении кода:

Правильный ответ: 2:2

Первая часть понятна: добавили два элемента, поэтому размер списка равен двум. Остаётся вопрос: почему не был удалён «test1»?

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

Строки сравниваются по значению, поэтому «test3» не эквивалентно «test1» и «test2». А раз ни один элемент не соответствует критерию поиска, ничего не удалится — размер списка останется прежним.

Проверьте себя: подумайте, что произойдёт, если вместо

Задачи для Set

Что выведет фрагмент кода ниже:

Правильный ответ: 3:, а дальше точно не известно.

Так как строки сравниваются по значению, а дубликаты во множествах недопустимы, второй «Иван» не станет частью множества. В итоге размер множества будет равен 3.

В каком порядке будут выведены элементы множества — определённо мы сказать не можем: во множествах порядок добавления не сохраняется.

Что выведет фрагмент кода:

Правильный ответ: 4.

Как же так, ведь во множество должны попадать уникальные элементы?

Прежде чем добавить новый элемент в множество, вычисляется его hashCode() — чтобы определить бакет, куда он может быть помещён.

Если бакет пуст, элемент будет добавлен. Иначе уже добавленные элементы с таким же значением хеша сравниваются с кандидатом при помощи метода equals(). Если дубликат не найден, новый элемент становится частью множества. Он попадёт в тот же бакет.

Мы добавляем в Set объекты типа Person — созданного нами класса. Этот класс, как и все ссылочные типы, наследуется от класса Object.

Так как мы не переопределили метод hashCode(), будет использована родительская реализация. В ней хеш вычисляется на основе данных адреса (реализация зависит от JVM).

Метод equals() тоже не переопределён. В классе-родителе этот метод просто сравнивает ссылки на объекты. Это значит, что даже если хеш случайно совпадёт для каких-то из четырёх элементов, equals() в любом случае вернёт false.

Таким образом, каждый из четырёх кандидатов попадёт в множество.

Проверьте себя: изменится ли что-нибудь, если переопределить hashCode() вот так:

А если ещё и equals() переопределить, как на фрагменте ниже:

Источник