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

Собеседование по 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 вторым конструктором. Элементы коллекции будут автоматически отсортированы в заданном порядке.

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

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

Екатерина Степанова

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Set	List	Queue	Map
Возможны дубликаты	❌	✅	✅	✅ для значений

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

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

Реализации List

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализации Map

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

// Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); /** * Constructs a new, empty set; the backing HashMap instance has * default initial capacity (16) and load factor (0.75). */ public HashSet() < map =new HashMap<>(); >

Фрагмент класса HashSet

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

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

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

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

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

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

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

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

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

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

Задачи для ArrayList

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

import java.util.ArrayList; public class SimpleTestArrayList < public static void main (String[] args) < ArrayListlist = new ArrayList<>(); list.add("test1"); list.add("test2"); list.add("test3"); System.out.print(list.get(1)+":"); list.add(1, "test4"); System.out.print(list.get(1)+":"); for (int i=0; i< list.size(); i++)< System.out.print(list.get(i)+":"); > > >

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

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

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

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

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

Вариант посложнее

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

import java.util.ArrayList; public class TestArrayList < public static void main(String args[]) < ArrayListString> list = new ArrayList<>(); String t1 = "test1"; String t2 = "test2"; list.add(t1); list.add(t2); System.out.print(list.size() + ":"); t1 = "test3"; list.remove(t1); System.out.print(list.size()); > >

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

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

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

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

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

list.remove(t1);

list.remove(“test1”);

Задачи для Set

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

import java.util.HashSet; public class SimpleTestSet < public static void main (String[] args)< HashSetString> set = new HashSet<>(); set.add("Иван"); set.add("Марья"); set.add("Пётр"); set.add("Иван"); System.out.print(set.size()+":"); for (String s: set)< System.out.print(s+" "); > > >

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

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

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

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

import java.util.HashSet; class Person < String name; Person(String name) < this.name = name; > public String toString() < return name; > > class TestHashSet < public static void main(String args[]) < HashSetset = new HashSet<>(); Person p1 = new Person("Иван"); Person p2 = new Person("Мария"); Person p3 = new Person("Пётр"); Person p4 = new Person("Мария"); set.add(p1); set.add(p2); set.add(p3); set.add(p4); System.out.print(set.size()); > >

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

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

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

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

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

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

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

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

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

@Override public int hashCode() < return 10; >

Параметры коллекций java

И совершенно нет ясности, какие объекты в какую коллекцию можно положить. Экспериментально выяснил, что в коллекцию 2 — можно добавить объекты (Object). А в коллекцию 3 — только с типом Integer. Вопрос 1: как понять по декларированию, какие объекты может содержать коллекция? Вопрос 2: для каких прикладных задач можно использовать первый, второй и третий вариант декларирования коллекций?

Отслеживать
1,478 14 14 серебряных знаков 24 24 бронзовых знака
задан 26 июл 2016 в 14:44
Andrew Kachalin Andrew Kachalin
2,895 3 3 золотых знака 28 28 серебряных знаков 49 49 бронзовых знаков
quizful.net/post/Java-Collections Вместо тысячи слов.
26 июл 2016 в 15:18
quizful.net/post/java-generics-tutorial — Дженерики. Ключ к пониманию коллекций.
26 июл 2016 в 15:19

По вопросу 1: Тот тип, что в угловых скобках — должен быть у объектов, которые может вмещать коллекция. По вопросу 2: 1 и 3 — используем, когда нужно хранить изменяемый по вместимости массив целых чисел. 2 — когда нужно оперировать с коллекциями, которые могут содержать разные типы данных. Т.е. мы можем под list иметь как коллекцию целых, так и коллекцию строк или коллекцию коллекций. Про интерфейсы (в ООП или в Java в частности) рекомендую почитать в первую очередь. И про модель организации данных в памяти компьютера.

26 июл 2016 в 15:24

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

По вопросу 1: Тот тип, что в угловых скобках <> — должен быть у объектов, которые может вмещать коллекция.

По вопросу 2: 1 и 3 — используем, когда нужно хранить изменяемый по вместимости массив целых чисел. 2 — когда нужно оперировать с коллекциями, которые могут содержать разные типы данных. Т.е. мы можем под list иметь как коллекцию целых, так и коллекцию строк или коллекцию коллекций. Про интерфейсы (в ООП или в Java в частности) рекомендую почитать в первую очередь. И про модель организации данных в памяти компьютера.

Если кратко, то все классы в Java — наследники класса Object . Интерфейс List определён как public interface List extends Collection (см. docs.oracle.com/javase/8/docs/api/java/util/List.html). Объявление List list можно читать как List list . Соответственно, раз в листе могут содержаться любые объекты, которые расширяют класс, который может содержать коллекция — то мы можем поместить под ссылку list объект листа объектов любого класса. (arininav.ru/js/java04.htm см. пункты 5.4.1.3. и 5.4.1.4.)

Коллекции

Для хранения наборов данных в 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 возвращать количество элементов в коллекции.