Генерические (параметризованные) классы.

Коллекции Java (Java Collections Framework)

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

Во многих языках программирования (Java, C, C++, Pascal) единственным встроенным в язык средством хранения объектов являются массивы. Однако, массивы обладают значительными недостатками.

Одним из них является конечный размер массива, как следствие, необходимость следить за размером массива.

Другим — индексная адресация, что не всегда удобно, т.к. ограничивает возможности добавления и удаления объектов.

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

Интерфейсы

Интерфейсы в Collections Framework играют ключевую роль. Все классы коллекций реализуют различные интерфейсы, которые определяют поведение коллекции. Иными словами, интерфейс определяет «что делает коллекция», а конкретная реализация — «как коллекция делает то что определяет интерфейс».

При разработке приложений рекомендуется, там где это возможного, использовать интерфейсы. Такая организация позволяет легко заменять реализацию интерфейса, с целью повышения производительности, например. А так же позволяет разработчику сконцентрироваться на задаче, а не на особенностях реализации.

Как не трудно догадаться, первая задача которая встает перед разработчиком при использовании Collections Framework — это выбор интерфейса.

К выбору интерфейса следует подходить исходя из предметной области. Например, если в реальном мире Вы имеете дело с очередью на обслуживание, вполне вероятно, что Вам необходимо использовать интерфейс java.util.Queue<E>.

При использовании всех интерфейсов крайне необходимо переопределить методы equals() и hashCode() хранимых объектов, т.к. они используется при сравнении двух объектов.

Рассмотрим интерфейсы подробнее:

java.lang.Iterable<T>

Интерфейс java.lang.Iterable<T> указывает на то что коллекция, реализующая его, может формировать объект-итератор, реализующий интерфейс java.util.Iterator<E>, а значит может быть использована в конструкции for (в виде for-each).

java.util.Collection<E>

Это базовый интерфейс Collections Framework. В интерфейсе java.util.Collection<E> определены основные методы для манипуляции с данными, такие как вставка (add, addAll), удаление (remove, removeAll, clear), поиск (contains).

Однако, в конкретной реализации часть методов может быть не определена, а их использование, в этом случае, вызовет исключение java.lang.UnsupportedOperationException. Поэтому я бы рекомендовал использовать интерфейс более адекватно описывающий предметную область.

Интерфейсы, наследующие java.util.Collection

java.util.List<E>

Интерфейс java.util.List<E> служит для описания списков. Данный интерфейс определяет поведение коллекций, которые служат для хранения упорядоченного набора объектов. Порядок в котором хранятся элементы определяется порядком их добавления в список.

Коллекции, реализующие интерфейс java.util.List<E> могут хранить 1,2 и более копий одного и того же объекта (ссылки на объект). Определена операция получения части списка. А в классе java.util.Collections определен статический метод для сортировки списков.

Реализации: java.util.ArrayList<E>, java.util.LinkedList<E>.

java.util.Queue<E>

Реализует FIFO–буфер. Позволяет добавлять и получать объекты. При этом объекты могут быть получены в том порядке, в котором они были добавлены.

Реализации: java.util.ArrayDeque<E>, java.util.LinkedList<E>.

java.util.Deque<E>

Наследует java.util.Queue<E>. Двунаправленная очередь. Позволяет добавлять и удалять объекты с двух концов. Так же может быть использован в качестве стека.

Реализации: java.util.ArrayDeque<E>, java.util.LinkedList<E>.

java.util.Set<E>

Коллекции, наследующие интерфейс java.util.Set<E> обеспечивают уникальность хранимых объектов. Иными словами, один и тот же объект не может быть добавлен более одного раза.

Реализации: java.util.HashSet<E>, java.util.LinkedHashSet<E>, java.util.TreeSet<E>.

См. хеширование

java.util.SortedSet<E>

Наследует java.util.Set<E>. Реализации этого интерфейса, помимо того что следят за уникальностью хранимых объектов, поддерживают их в порядке возрастания.

Отношение порядка между объектами может быть определено, как с помощью метода compareTo интерфейса java.lang.Comparable<T>, так и при помощи специального класса-компаратора, наследующего интерфейс java.util.Comparator<T>.

Реализации: java.util.TreeSet<E>.

Comparison of Collection Comparison of Lists
	ArrayList	LinkedList
Description	Dynamic (a.k.a. growable, resizable) array	Doubly-linked list
Random Access with index (get())	O(1)	O(n)
Insertion (add()) / removal at the back	amortized O(1)	O(1)
Insertion / removal at the front	O(n)	O(1)
One step of iteration through an Iterator	O(1)	O(1)
Insertion / removal in the middle through an Iterator / ListIterator	O(n)	O(1)
Insertion / removal in the middle through the index	O(n)	O(n)
Search contains() / removal remove() by object	O(n)	O(n)

Comparison of Sets
	HashSet	TreeSet
Description	Hash table	Self-balancing binary search tree
Requirements	Objects need to implement a hash function (hashCode()) which is consistent with equals()	Either objects need to implement the Comparable interface and be able to compare to each other; or a Comparator for the objects must be provided; the ordering must satisfy a "total ordering"
Test for membership (contains())	O(1) average O(n) worst-case	O(log n)
Insertion (add()) / removal (remove())	O(1) average O(n) worst-case	O(log n)
One step of iteration through an Iterator	O(1)	O(1)
Iterates through elements in ascending order	No	Yes

Отображения (карты)

java.util.Map<K,V>

Интерфейс java.util.Map<K,V> используется для отображения каждого элемента из одного множества объектов (ключей) на другое (значений).

При этом, каждому элементу из множества ключей ставится в соответствие ровно 1 элемент из множества значений. В то же время одному элементу из множества значений может соответствовать 1, 2 и более элементов из множества ключей. Интерфейс java.util.Map<K,V> описывает функциональность ассоциативных массивов.

Реализации: java.util.HashMap<K,V>, java.util.LinkedHashMap<K,V>, java.util.TreeMap<K,V>, java.util.WeakHashMap<K,V>.

java.util.SortedMap<K,V>

Наследует java.util.Map<K,V>. Реализации этого интерфейса обеспечивают хранение элементов множества ключей в порядке возрастания (см. java.util.SortedSet).

Реализации: java.util.TreeMap<K,V>.

Java Map Comparison :

• HashMap is the fastest map with O(1) search and insertion times.
• LinkedHashMap is a little slower for inserts, but maintains the insertion order.
• TreeMap is the slowest map, but lets you iterate over the keys in a sorted order.

Реализации

Как видно, Collections Framework обеспечивает богатый выбор интерфейсов, практически на любой случай.

Однако эти интерфейсы всего лишь описание того что класс коллекции должен делать. Интерфейсы не говорят о том как тот или иной класс коллекции реализует свой интерфейс. Более того, различные реализации могут накладывать дополнительные ограничения.

Общие вопросы хранения данных

Для начала разберемся каким образом классы Collections Framework хранят данные. Если вы посмотрите на список реализаций интерфейса java.util.List<E>, например, то увидите десять его реализаций. Возникает резонный вопрос: неужели существует 10 способов хранения списков? Вовсе нет. Все способы хранения данных в Collections Framework можно свести трем основным: массивы, связанные списки, бинарные деревья. Рассмотрим их подробнее.

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

Контейнеры на основе массивов: java.util.ArrayList<E>, java.util.ArrayDeque<E>.

Связанные списки представляют собой цепочку из объектов ссылающихся друг на друга. Рассмотри звено такой цепочки из реализации java.util.LinkedList<E>:

private static class Entry<E> {
 E element;
 Entry<E> next;
 Entry<E> previous;
 ...
}

Как видно, одно звено содержит ссылки на предыдущее и следующее звенья, а так же на объект, хранящийся в списке. Реализация java.util.LinkedList<E> представляет собой замкнутый двунаправленный список. Скорость доступа к произвольному элементу будет зависеть от его положения относительно головы списка (того звена на которое ссылается объект java.util.LinkedList<E>) и в среднем будет пропорциональна размеру списка. Однако, скорость последовательного доступа ко всем элементам списка посредством итератора не будет зависеть от положения элементов в списке. Отсюда можно заключить, что контейнеры на основе связанных списков не стоит использовать там где необходимо часто обращаться к произвольному элементу.

Контейнеры на основе связанных списков: java.util.LinkedList<E>.

Бинарные деревья служат для хранения и поиска упорядоченных объектов. Это значит, что для хранимых объектов необходимо определить отношение порядка при помощи метода compareTo и наследования от интерфейса java.lang.Comparable<T> или класса реализующего интерфейс java.util.Comparator<T>. Скорость доступа к произвольному объекту в таких деревьях пропорциональна логарифму размера контейнера.

Контейнеры на основе бинарных деревьев: java.util.TreeSet<E>, TreeMap<K,V>.

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

Контейнеры на основе хэш-таблиц: java.util.HashSet<E>, java.util.HashMap<K,V>, java.util.WeakHashMap<K,V>.