Когда какую коллекцию использовать java

Когда какую коллекцию использовать java

На интуитивном уровне возможно даже понятно, зачем нужна такая конструкция и что она делает, но сейчас самое время узнать о ней много интересного.

Что такое Generic

Давайте еще раз посмотрим на объявление нашего метода:

public List < Contact >findContacts ( ) ;

Как видим, он возвращает список контактов (это класс, который реализует интерфейс java.util.List). Но что это за угловые скобочки, внутри которых находится слово Contact ? Давайте разбираться.

Старые песни на новый лад. Очередь объектов с Generic

Когда-то я написал статью Что нового в Java SE 5.0 и там упоминал о Generic. Так что кое-что можете посмотреть там тоже. Но и здесь мы будем изучать этот вопрос на примере, который мы разбирали раньше — Пример – очередь объектов.
Наша очередь, которую мы создали в этом примере, предоставляет возможность хранить список (произвольного размера) объектов любого типа. Но это достигается не самым приятным способом — мы вынуждены приводить полученные объекты к нужному нам типу из класса Object. С одной стороны — у нас очень гибкий инструмент. Мы туда можем положить и строки, и даты, и числа — все что угодно. Но на практике такое разнообразие типов в одном списке больше мешает, чем помогает. Идея создания класса, который бы мог работать с одной стороны с любым обхектом, а с другой стороны позволял четко определить с каким именно классом/типом он должен работать «на лету» достаточно продуктивна и поэтоу был создан механизм Generic.
Основную мысль я уже озвучил, так что повторюсь — Generic позволяет во-первых, определить класс, функциональность которого не зависит от типа объектов, с которыми он работает. И во-вторых, вы можете определить точный тип «на лету». Причем как только вы определяете тип, то все методы класса с Generic понимают только этот класс и никакой другой (дальше мы увидим, что это не совсем так, но для простоты я пока предлагаю понимать так). Как определяется Generic рассмотрим на самом простом примере, после которого перейдем к нашей очереди.
Итак, я хочу определить класс, у которого может быть поле произвольного класса и два метода — сеттер и геттер. Если не использовать Generic, то для универсальности мне пришлось бы написать что-то такое:

public class SimpleGeneric
private Object element ;
public Object getElement ( ) < return element ; public void setElement ( Object element ) < this . element = element ;

Использвать это класс для работы со строкой (String) пришлось бы как-то так

SimpleGeneric sg = new SimpleGeneric ( ) ;
sg . setElement ( «12345» ) ;
String s = ( String ) sg . getElement ( ) ;

Самой важной здесь является третья строка с жестким приведением типа. Для одного случая это не самая большая проблема, но когда у вас сотни или даже тысячи разных классов, которые надо помещать в какие-то списки, очереди и т.д., то держать в голове, какие именно классы вы помещали в ту или иную очередь — это очень сложно и неудобно. Попробуем применить Generic.

public class SimpleGeneric < T >
private T element ;
public T getElement ( ) < return element ; public void setElement ( T element ) < this . element = element ;

Давайте внимательно посмотрим, что здесь изменилось. В первую очередь, в самом описании класса мы видим вот такую конструкцию

public class SimpleGeneric < T >

Буква «T» в угловых скобках говорит о том, что это — абстрактный тип (можно использовать не букву «Т», а любое другое имя — например «SIMPLE» или «Test»). И этот абстрактный тип мы будем использовать в дальнейшем описании нашего generic-класса. Если я хочу вернуть объект из метода getElement, то я в описании указываю «T» вместо Object. Это означает, что наш класс в какой-то степени «полуфабрикат» — он заранее не знает, какой именно класс он будет использовать в этих методах. Но т.к. его алгоритм универсален (в данном случае мы делаем очень простые функции, которые не зависят от класса), то мы как бы говорим нашему классу — «не парься, что именно за класс у тебя будет, в свое время узнаешь. И подставишь его вместо «T». Но чтобы ты понимал, в каких методах он встречается, мы тебе создаем подсказку в виде некоторого абстрактного типа «T» в угловых скобках». Именно угловые скобки говорят о том, что этот тип «для подстановки». Давайте посмотрим теперь как делать эту самую подстановку.

public class SimpleGenericTest
public static void main ( String [ ] args ) < SimpleGeneric < String >sg1 = new SimpleGeneric <> ( ) ;
sg1 . setElement ( «12345» ) ;
SimpleGeneric < Integer >sg2 = new SimpleGeneric <> ( ) ;
sg2 . setElement ( 99 ) ;

Обратите внимание, что при объявлении переменной, мы в угловых скобках указываем конкретный класс. В первом случае это String, во втором — Integer. Т.е. при объявлении переменной мы уже точно определяем, с каким типом будет работать эта переменная. Теперь проверка правильности подстановки нужного типа проверяется уже на этапе компиляции. Например, если вы попробуете установить для переменной sg2 строку — будет выдаваться ошибка. Попробуйте сделать вот так — и увидите.

SimpleGeneric < Integer >sg2 = new SimpleGeneric <> ( ) ;
sg2 . setElement ( «99» ) ;

До версии java 1.7 вы должны были дублировать содержиме угловых скобок и для правой части (точнее при вызове конструктора) — посмотрите пример.

public class SimpleGenericTest
public static void main ( String [ ] args ) < // До версии Java 1.7 надо было указывать тип в конструкторе SimpleGeneric < String >sg1 = new SimpleGeneric < String >( ) ;
sg1 . setElement ( «12345» ) ;
SimpleGeneric < Integer >sg2 = new SimpleGeneric < Integer >( ) ;
sg2 . setElement ( 99 ) ;

В работе с Generic-классами важно уловить самое важное — умение работать С ЛЮБЫМ КЛАССОМ. Ну или с некоторой группой классов, имеющих один и тот же интерфейс (мы это еще увидим). Коллекции в этом отношении — самые благодарные. Им в общем-то без разницы объект какого класса у них находится в работе — как грузовику совершенно не важно, коробки с какими надписями лежат у него в кузове.
Нашей очереди в общем не важно, какой именно тип будет использоваться. Но в этом случае объявление абстрактонго типа несколько сложнее, т.к. он используется сразу в двух классах — ObjectQueue и QueueBox. Давайте сначал рассмотрим вложенный класс QueueBox.

// Наш класс теперь Generic — тип хранимого объекта заранее неизвестен.
// Но нам это не важно — мы с ним по сути не работаем — не вызываем его методы
private class ObjectBox < T >
// Поле для хранения объекта — теперь он не определен заранее
private T object ;
// Поле для указания на следующий элемент в цепочке, у которого такой же тип.
// Т.е. мы можем сказать. что использовать надо тот же тип T
private ObjectBox < T >next ;
// Метод возвращает объект заранее неопределнного типа T
public T getObject ( ) < return object ; // Метод принимает на вход объект заранее неизвестного типа T public void setObject ( T object ) < this . object = object ; // Метод возращает указатель на следующий элемент в цепочке, у которого // тоже тип пока абстрактный, но такой же - T public ObjectBox < T >getNext ( ) < return next ; // Метод принимает указатель на следующий элемент в цепочке, у которого // тоже тип пока абстрактный, но такой же - T public void setNext ( ObjectBox < T >next ) < this . next = next ;

Как видите тут описание сложнее. Наверно самое зубодробительное — это описание private ObjectBox next;. Дело в том, что мы описываем переменную next и в этот момент мы должны указать, а какой тип будет использовать ObjectBox для этой переменной. Само собой мы не знаем. Но мы знаем, что он будет таким же, что и у основного класса. Т.е. мы инициализируем next, но инициализируем опять же абстрактным класом. Поэтому такая хитрая конструкция.
На таком же принципе мы определяем и нашу очередь — класс ObjectQueue. Смотрим полный код класса

package edu . javacourse . queue ;
public class ObjectQueue < T >
// Указатель на первый элемент
private ObjectBox < T >head = null ;
// Указатель на последний элемент
private ObjectBox < T >tail = null ;
// Поле для хранения размера очереди
private int size = 0 ;
public void push ( T obj ) < // Сразу создаем вспомогательный объект и помещаем новый элемент в него ObjectBox < T >ob = new ObjectBox <> ( ) ;
ob . setObject ( obj ) ;
// Если очередь пустая — в ней еще нет элементов
if ( head == null ) < // Теперь наша голова указывает на наш первый элемент // Если это не первый элемент, то надо, чтобы последний элемент в очереди // указывал на вновь прибывший элемент tail . setNext ( ob ) ; // И в любом случае нам надо наш "хвост" переместить на новый элемент // Если это первый элемент, то "голова" и "хвост" будут указывать на один и тот же элемент // Увеличиваем размер нашей очереди public T pull ( ) < // Если у нас нет элементов, то возвращаем null if ( size == 0 ) < return null ; // Получаем наш объект из вспомогательного класса из "головы" T obj = head . getObject ( ) ; // Перемещаем "голову" на следующий элемент head = head . getNext ( ) ; // Если это был единственный элемент, то head станет равен null // и тогда tail (хвост) тоже дожен указать на null. if ( head == null ) < tail = null ; // Уменьшаем размер очереди // Возвращаем значение return obj ; public T get ( int index ) < // Если нет элементов или индекс больше размера или индекс меньше 0 if ( size == 0 || index >= size || index < 0 ) < return null ; // Устанавлваем указатель, который будем перемещать на "голову" ObjectBox < T >current = head ;
// В этом случае позиция равну 0
int pos = 0 ;
// Пока позиция не достигла нужного индекса
while ( pos < index ) < // Перемещаемся на следующий элемент current = current . getNext ( ) ; // И увеличиваем позицию // Мы дошли до нужной позиции и теперь можем вернуть элемент T obj = current . getObject ( ) ; return obj ; public int size ( ) < return size ; // Наш вспомогательный класс будет закрыт от посторонних глаз private class ObjectBox < T >
// Поле для хранения объекта
private T object ;
// Поле для указания на следующий элемент в цепочке.
// Если оно равно NULL — значит это последний элемент
private ObjectBox < T >next ;
public T getObject ( ) < return object ; public void setObject ( T object ) < this . object = object ; public ObjectBox getNext ( ) < return next ; public void setNext ( ObjectBox < T >next ) < this . next = next ;

Как видите, теперь мы везде используем абстрактный класс «T». Я вам советую внимательно разобраться в примере. Класс для проверки нашей очереди теперь выглядит вот так

package edu . javacourse . queue ;
public class QueueTest
public static void main ( String [ ] arg ) < ObjectQueue < String >queue = new ObjectQueue <> ( ) ;
for ( int i = 0 ; i < 10 ; i ++ ) < queue . push ( "Строка:" + i* 100 ) ; for ( int i = 0 ; i < queue . size ( ) ; i ++ ) < String s = queue . get ( i ) ; System . out . println ( s ) ; System . out . println ( "============== crayon-sy">) ;
while ( queue . size ( ) > 0 ) < String s = queue . pull ( ) ; System . out . println ( s + " Размер:" + queue . size ( ) ) ;

В первой же строке мы указываем, что наша очередь будет работать со строками. Теперь все методы, которые объявлены с «T» по сути заменят его на String. Наши методы становятся жестко типизироваными (для переменной queue) — мы не сможем положить в нашу очередь queue числа или даты и при вызове метода get или pull методы будут сразу возвращать String. Что несомненно удобно. Причем если мы объявим переменную queue2 и типизируем ее Integer, то для этой переменнй строки будут недоступны.
В качестве домашнего задания попробуйте переписать пример из раздела Визуализация робота с использованием нашей типизированной очереди. На этом я хочу закончить первое знакомство с generic-классами и перейти к коллекциям. Но мы еще вернемся к этой теме.

Классы из CollectionFramework

Итак, мы с вами поззнакомились с понятие generic и теперь пора познакомиться с некоторыми готовыми классами, которые уже написаны и включены в Java SE.
Когда вы приступаете к выбору класса для коллекции, то вам необходимо определить набор характеристик, которые являются важными в рамках тех задач, которые призвана решать эта коллекция. Мы уже прошлись по списку базовых интерфейсов и это первый шаг для выбора коллекции. Например, если у вас предполагается ситуация с одинаковыми элементами в коллекции или вам крайне важен порядок элементов в коллекции, да к тому же вам надо иметь возможность обратиться к элементу на определенной позиции, то практически однозначно вам нужны реализации интерфейса List. Если вам необходима уникальность, быстрый поиск элемента внутри коллекции и порядок не важен — смотрим в сторорну Set. Нужен отсортированный порядок уникальных элементов — смотрим SortedSet.
Если работа с коллекцией требует поиска элемента по ключу, то на первом месте идет Map.
После того, как вы определитесь с базовым интерфейсом, наступает время выбора конкретной реализации, что тоже требует знакомства с конкретными классами. Например вы остановили свой выбор на интерфейсе List. Если зайти на страницу с документацией List (Java Platform SE 8 ), то выбор конечно не огромный, но достаточный, чтобы задуматься. Например, что нам больше подойдет — arrayList, LinkedList, Vector ? Здесь начинается изучение особенностей реализации. Класс ArrayList — прекрасный выбор, если вам нужен быстрый доступ к элементу по индексу и вы заранее знаете (хотя бы приблизительно) сколько элементов будет в этой коллекции. Но если вам надо много добавлений и не требуется доступ к элементу, а нужно пробегать по всему списку, то этот класс невыгоден — он основан на массиве и как только вы достигаете определенного размера, то будет создаваться новый массив, в который будут копироваться все элементы. Это дорогое удовольствие. Зато класс LinkedList прекрасно подходит. Мы уже в этом убедились — ведь мы создавали по сути свою версию этого класса — класс ObjectQueue. Могут быть дополнительные требования — например потокобезопасность (мы будем говорить о потоках позже). В этом случае возможно подойдет что-то еще. Т.е. с одной стороны все выглядит достаточно несложно — надо просто выбрать подходящий класс, но как говорится «дьявол кроется в деталях». Я встречал ситуации, когда разработчики создавали свои версии коллекций, т.к. существующие им не подходили.

Алгоритмы для работы с коллекциями

Алгоритмы для работы с коллекциями реализуются (в основном) в классе java.util.Collections. Не перепутайте с классом, о котором мы уже говорили — java.util.Collection. Отличие минимальное — в конце стоит дополнительная буква s. Если честно, мне не нравится — слишком похожие имена легко путаются, что меня никогда не радовало. Но что сделано, то сделано.
Я надеюсь, что вы уже достаточно продвинулись в изучении java и тратить кучу слов на описание методов мне бы не хотелось. Поэтому сразу предлагаю посмотреть пример — в нем последовательно приведены вызовы с некоторым набором функций класса java.utilCollections. просто посмотрите код, потом запустите и посмотрите на результаты. Весь пример посвящен нескольким операциям, результат которых демонстрируется выводом коллекции

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

— Сегодня мы разберемся с устройством коллекций раз и навсегда.

— Давно этого ждал.

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

Интерфейсы коллекций. Структура наследования интерфейсов коллекций выглядит примерно так:

Обрати внимание, на две вещи.

Во-первых, все, что ты тут видишь – это интерфейсы.

Во-вторых, стрелочки обозначают «наследуется от».

— Т.е. List, Set, Queue наследуются от Collection, а Map – нет?

— Ага. Потом от этих интерфейсов наследуются абстрактные классы, а от них в свою очередь – известные тебе реализации: ArrayList, Hashtable, TreeSet,…

— Есть такое дело.

Теперь давай посмотрим, что за методы есть у этих интерфейсов:

Методы интерфейса Iterable:

Методы	Описание
Iterator iterator();	Возвращает объект-итератор.

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

Методы интерфейса Collection:

Методы	Описание
boolean add(E e);	Добавляет элемент в коллекцию
boolean addAll(Collection c);	Добавляет элементы в коллекцию
void clear();	Удаляет все элементы из коллекции
boolean contains(Object o);	Проверяет – есть ли в коллекции элемент?
boolean containsAll(Collection c);	Проверяет – есть ли в коллекции элементы?
boolean equals(Object o);	Сравнивает коллекции
int hashCode();	Возвращает хэш-код
boolean isEmpty();	Проверяет – пуста ли коллекция?
Iterator iterator();	Возвращает объект-итератор
boolean remove(Object o);	Удаляет элемент из коллекции
boolean removeAll(Collection c);	Удаляет элементы из коллекции
boolean retainAll(Collection c);	Удаляет все элементы, которых нет «с»
int size();	Возвращает размер коллекции
Object[] toArray();	Преобразовывает коллекцию к массиву
T[] toArray(T[] a);	Преобразовывает коллекцию к массиву

— Тут уже посолиднее все. Половину из этих методов я использовал, а со второй сталкивался.

— Отлично, тогда продолжим.

Методы интерфейса List:

Методы	Описание
void add(int index, E element);	Добавляет элементы в середину коллекции
boolean addAll(int index, Collection c);	Добавляет элементы в коллекцию
E get(int index);	Возвращает элемент по номеру
int indexOf(Object o);	Возвращает индекс(номер) элемента
int lastIndexOf(Object o);	Возвращает последний индекс элемента.
ListIterator listIterator();	Возвращает итератор для списка
ListIterator listIterator(int index);	Возвращает итератор для списка
E remove(int index);	Удаляет элемент по индексу
E set(int index, E element);	Устанавливает новое значение по индексу
List subList(int fromIndex, int toIndex);	Возвращает подколлекцию

— Тоже ничего кардинально нового. Я уже практически все знаю по коллекциям, что не может не радовать.

— Ну, я думаю, у меня найдется, чем тебя удивить. Но давай продолжим изучат интерфейсы:

Методы интерфейса Set:

Методы	Описание
нет методов

Интерфейс Set не содержит новых методов, только унаследованные.

— Да, я смотрю, интерфейс Iterable был еще ничего.

С другой стороны – меньше методов – меньше запоминать!

— Меня радует твой жизнеутверждающий оптимизм.

У интерфейса Set есть два интерфейса-наследника с методами: SortedSet и NavigableSet, но я не буду их приводить, а то мы никогда не закончим.

Давай я лучше дам тебе общую картину классов и интерфейсов, описывающих коллекции в Java.

— Ничего себе, да она просто огромная!

— Ну, не такая уж она и большая. Кроме того, запоминать абстрактные классы совсем не обязательно. А вот какой класс, какие интерфейсы реализует лучше запомнить – такое может пригодиться довольно часто.

— Ну, еще хотелось бы отметить, что некоторые коллекции были признаны устаревшими.

— Это я про классы Vector, Stack, Dictionary, Hashtable – они являются синхронизированными (потокобезопасными) версиями обычных коллекций.

Но в Java появилась специальная библиотека — concurrency , где содержится очень много коллекций, к которым не только можно обращаться из других потоков/нитей, но и которые написаны гораздо эффективнее. ConcurrentHashMap гораздо эффективнее Hashtable.

Использовать коллекции Vector, Stack, Dictionary, Hashtable можно, но не рекомендуется.

— Ясно, буду иметь в виду.

Коллекции

Для хранения наборов данных в 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 является базовым для всех коллекций, определяя основной функционал:

public interface Collection extends Iterable < // определения методов >

Интерфейс 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 — коллекции (Collections) (вопросы и ответы)

Список вопросов и ответов по теме “Коллекции в Java”.

К списку вопросов по всем темам

Вопросы

1. Дайте определение понятию “коллекция”.
2. Назовите преимущества использования коллекций.
3. Какие данные могут хранить коллекции?
4. Какова иерархия коллекций?
5. Что вы знаете о коллекциях типа List?
6. Что вы знаете о коллекциях типа Set?
7. Что вы знаете о коллекциях типа Queue?
8. Что вы знаете о коллекциях типа Map, в чем их принципиальное отличие?
9. Назовите основные реализации List, Set, Map.
10. Какие реализации SortedSet вы знаете и в чем их особенность?
11. В чем отличия/сходства List и Set?
12. Что разного/общего у классов ArrayList и LinkedList, когда лучше использовать ArrayList, а когда LinkedList?
13. В каких случаях разумно использовать массив, а не ArrayList?
14. Чем отличается ArrayList от Vector?
15. Что вы знаете о реализации классов HashSet и TreeSet?
16. Чем отличаются HashMap и TreeMap? Как они устроены и работают? Что со временем доступа к объектам, какие зависимости?
17. Что такое Hashtable, чем она отличается от HashMap? На сегодняшний день она deprecated, как все-таки использовать нужную функциональность?
18. Что будет, если в Map положить два значения с одинаковым ключом?
19. Как задается порядок следования объектов в коллекции, как отсортировать коллекцию?
20. Дайте определение понятию “итератор”.
21. Какую функциональность представляет класс Collections?
22. Как получить не модифицируемую коллекцию?
23. Какие коллекции синхронизированы?
24. Как получить синхронизированную коллекцию из не синхронизированной?
25. Как получить коллекцию только для чтения?
26. Почему Map не наследуется от Collection?
27. В чем разница между Iterator и Enumeration?
28. Как реализован цикл foreach?
29. Почему нет метода iterator.add() чтобы добавить элементы в коллекцию?
30. Почему в классе iterator нет метода для получения следующего элемента без передвижения курсора?
31. В чем разница между Iterator и ListIterator?
32. Какие есть способы перебора всех элементов List?
33. В чем разница между fail-safe и fail-fast свойствами?
34. Что делать, чтобы не возникло исключение ConcurrentModificationException?
35. Что такое стек и очередь, расскажите в чем их отличия?
36. В чем разница между интерфейсами Comparable и Comparator?
37. Почему коллекции не наследуют интерфейсы Cloneable и Serializable?

Ответы

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

1. Дайте определение понятию “коллекция”.

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

2. Назовите преимущества использования коллекций.

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

3. Какие данные могут хранить коллекции?

Коллекции могут хранить любые ссылочные типы данных.

4. Какова иерархия коллекций?

Здесь следует обратить внимание, что interface Map не входит в иерархию interface Collection.

С Java 1.6 классы TreeSet и TreeMap имплементируют интерфейсы NavigableSet и NavigableMap, которые расширяют интерфейсы SortedSet и SortedMap соответственно (SortedSet и SortedMap расширяют Set и Map).

Подробная статья про коллекции с описанием основных методов: http://www.quizful.net/post/Java-Collections

5. Что вы знаете о коллекциях типа List?

List — это упорядоченный список. Объекты хранятся в порядке их добавления в список. Доступ к элементам списка осуществляется по индексу.

6. Что вы знаете о коллекциях типа Set?

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

7. Что вы знаете о коллекциях типа Queue?

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

Очереди обычно, но не обязательно, упорядочивают элементы в FIFO (first-in-first-out, «первым вошел — первым вышел») порядке.

Метод offer() вставляет элемент в очередь, если это не удалось — возвращает false . Этот метод отличается от метода add() интерфейса Collection тем, что метод add() может не выполнить добавление элемента только с использованием unchecked исключения.

Методы remove() и poll() удаляют верхушку очереди и возвращают ее. Какой элемент будет удален (первый или последний) зависит от реализации очереди. Методы remove() и poll() отличаются лишь поведением, когда очередь пустая: метод remove() генерирует исключение, а метод poll() возвращает null .

Методы element() и peek() возвращают (но не удаляют) верхушку очереди.

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

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

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

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

Подробнее http://www.seostella.com/ru/article/2012/08/09/kollekcii-collections-v-java-queue.html

8. Что вы знаете о коллекциях типа Map, в чем их принципиальное отличие?

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

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

java.util.SortedMap наследует java.util.Map . Реализации этого интерфейса обеспечивают хранение элементов множества ключей в порядке возрастания (см. java.util.SortedSet). Реализации: java.util.TreeMap .

http://developer.alexanderklimov.ru/android/java/map.php

9. Назовите основные реализации List, Set, Map.

Интерфейс	Класс/Реализация	Описание
List	ArrayList	Список
	LinkedList	Список
	Vector	Вектор
	Stack	Стек
Set	HashSet	Множество
	TreeSet	Множество
	SortedSet (расширяющий интерфейс)	Отсортированное множество
Map	HashMap	Карта/Словарь
	TreeMap	Карта/Словарь
	SortedMap (расширяющий интерфейс)	Отсортированный словарь
	Hashtable	Хеш-таблица

10. Какие реализации SortedSet вы знаете и в чем их особенность?

java.util.SortedSet наследует java.util.Set . Реализации этого интерфейса, помимо того что следят за уникальностью хранимых объектов, поддерживают их в порядке возрастания. Отношение порядка между объектами может быть определено, как с помощью метода compareTo интерфейса java.lang.Comparable , так и при помощи специального класса-компаратора, наследующего интерфейс java.util.Comparator .

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

11. В чем отличия/сходства List и Set?

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

12. Что разного/общего у классов ArrayList и LinkedList, когда лучше использовать ArrayList, а когда LinkedList?

ArrayList реализован внутри в виде обычного массива . Поэтому при вставке элемента в середину, приходится сначала сдвигать на один все элементы после него, а уже затем в освободившееся место вставлять новый элемент. Зато в нем быстро реализованы взятие и изменение элемента – операции get, set , так как в них мы просто обращаемся к соответствующему элементу массива.

LinkedList реализован внутри по-другому. Он реализован в виде связного списка : набора отдельных элементов, каждый из которых хранит ссылку на следующий и предыдущий элементы. Чтобы вставить элемент в середину такого списка, достаточно поменять ссылки его будущих соседей. А вот чтобы получить элемент с номером 130, нужно пройтись последовательно по всем объектам от 0 до 130. Другими словами операции set и get тут реализованы очень медленно . Посмотри на таблицу:

Описание	Операция	ArrayList	LinkedList
Взятие элемента	get	Быстро	Медленно
Присваивание элемента	set	Быстро	Медленно
Добавление элемента	add	Быстро	Быстро
Вставка элемента	add(i, value)	Медленно	Быстро
Удаление элемента	remove	Медленно	Быстро

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

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

Из лекции javarush.ru

Структуры данных в картинках. LinkedList: http://habrahabr.ru/post/127864/

13. В каких случаях разумно использовать массив, а не ArrayList?

Если коротко, то Oracle пишет — используйте ArrayList вместо массивов. Если ответить на этот вопрос нужно по-другому, то можно сказать следующее: массивы могут быть быстрее и кушать меньше памяти. Списки теряют в производительности из-за возможности автоматического увеличения размера и сопутствующих проверок. Плюс к этому, что размер списка увеличивается не на 1, а на большее кол-во элементов (+15)*. Так же доступ к [10] в массиве может быть быстрее чем вызов get(10) у списка.

*Читатель прислал комментарий «У ArrayList увеличение происходит в 1.5 раза. int newCapacity = oldCapacity + (oldCapacity >> 1);».

Структуры данных в картинках. ArrayList: http://habrahabr.ru/post/128269/

Еще о ArrayList на сайте http://developer.alexanderklimov.ru/android/java/arraylist.php

14. Чем отличается ArrayList от Vector?

Vector deprecated. У Vector некоторые методы синхронизированы и поэтому они медленные. В любом случае Vector не рекомендуется использовать вообще.

15. Что вы знаете о реализации классов HashSet и TreeSet?

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

HashSet реализован на основе хеш-таблицы, а TreeSet — на основе бинарного дерева.

Подробнее о Set, HashSet, LinkedHashSet, TreeSet: http://developer.alexanderklimov.ru/android/java/set.php

HashSet гораздо быстрее чем TreeSet (константное время против логарифмического для большинства операций, таких как add , remove , contains ), но TreeSet гарантирует упорядоченность объектов. Оба не синхронизированы.

• предоставляет константное время для add() , remove() , contains() и size()
• порядок элементов в контейнере может меняться
• производительность итерации по контейнеру зависит от емкости и «коэффициента загрузки» (рекомендуется оставлять load factor значением по умолчанию равным 0.75, что является хорошим компромиссом между временем доступа и объемом хранимых данных)

• время для базовых операций add() , remove() , contains() — log(n)
• гарантирует порядок элементов
• не предоставляет каких-либо параметров для настройки производительности
• предоставляет дополнительные методы для упорядоченного списка: first() , last() , headSet() , tailSet() и т.д.

Годный ответ на StackOverflow http://stackoverflow.com/questions/1463284/hashset-vs-treeset

16. Чем отличаются HashMap и TreeMap? Как они устроены и работают? Что со временем доступа к объектам, какие зависимости?

В целом ответ про HashSet и TreeSet подходит и к этому вопросу.

HashMap работает строго быстрее TreeMap .

TreeMap реализован на красно-черном дереве, время добавления/поиска/удаления элемента — O(log N), где N — число элементов в TreeMap на данный момент.

У HashMap время доступа к отдельному элементу — O(1) при условии, что хэш-функция ( Object.hashCode() ) определена нормально (что является правдой в случае Integer ).

Общая рекомендация — если не нужна упорядоченность, использовать HashMap . Исключение — ситуация с вещественными числами, которые в качестве ключей почти всегда очень плохи. Для них нужно использовать TreeMap , предварительно поставив ему компаратор, который сравнивает вещественные числа так, как это нужно в данной задаче. Например, для обычных геометрических задач два вещественных числа могут считаться равными, если отличаются не более, чем на 1e-9.

Структуры данных в картинках. HashMap: http://habrahabr.ru/post/128017/

17. Что такое Hashtable, чем она отличается от HashMap? На сегодняшний день она deprecated, как все-таки использовать нужную функциональность?

Некоторые методы HashTable синхронизированы, поэтому она медленнее HashMap .

• HashTable синхронизирована, а HashMap нет.
• HashTable не позволяет иметь null ключи или значения. HashMap позволяет иметь один null ключ и сколько угодно null значений.
• У HashMap есть подкласс LinkedHashMap , который добавляет возможности по итерации. Если вам нужна эта функциональность, то можно легко переключаться между классами.

Общее замечание — не рекомендуется использовать HashTable даже в многопоточных приложениях. Для этого есть ConcurrentHashMap .

http://stackoverflow.com/questions/40471/differences-between-hashmap-and-hashtable

18. Что будет, если в Map положить два значения с одинаковым ключом?

Последнее значение перезапишет предыдущее.

19. Как задается порядок следования объектов в коллекции, как отсортировать коллекцию?

Класс ТгееМар полностью реализует интерфейс SortedMap . Он реализован как бинарное дерево поиска, значит его элементы хранятся в упорядоченном виде. Это значительно ускоряет поиск нужного элемента. Порядок задается либо естественным следованием элементов, либо объектом, реализующим интерфейс сравнения Comparator .

В этом классе четыре конструктора:

ТгееМар() — создает пустой объект с естественным порядком элементов;
TreeМар(Comparator с) — создает пустой объект, в котором порядок задается объектом сравнения с;
ТгееМар(Map f) — создает объект, содержащий все элементы отображения f, с естественным порядком его элементов;
ТгееМар(SortedMap sf) — создает объект, содержащий все элементы отображения sf, в том же порядке.

Интерфейс Comparator описывает два метода сравнения:

int compare(Object obj1, object obj2) — возвращает отрицательное число, если obj1 в каком-то смысле меньше obj2 ; нуль, если они считаются равными; положительное число, если obj1 больше obj2 . Для читателей, знакомых с теорией множеств, скажем, что этот метод сравнения обладает свойствами тождества, антисимметричности и транзитивности;

boolean equals(Object obj) — сравнивает данный объект с объектом obj , возвращая true , если объекты совпадают в каком-либо смысле, заданном этим методом.

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