# Cобеседование по Java. Разбор вопросов и ответов.       Нажмите ★, если вам нравится проект. Ваш вклад сердечно ♡ приветствуется. Если вам интересно мое резюме: https://github.com/DEBAGanov Java Collections: # Java Collections Framework - [Cобеседование по Java. Разбор вопросов и ответов.](#cобеседование-по-java-разбор-вопросов-и-ответов) - [Java Collections Framework](#java-collections-framework) - [Что такое _«коллекция»_?](#что-такое-коллекция) - [Назовите основные интерфейсы JCF и их реализации.](#назовите-основные-интерфейсы-jcf-и-их-реализации) - [Расположите в виде иерархии следующие интерфейсы: `List`, `Set`, `Map`, `SortedSet`, `SortedMap`, `Collection`, `Iterable`, `Iterator`, `NavigableSet`, `NavigableMap`.](#расположите-в-виде-иерархии-следующие-интерфейсы-list-set-map-sortedset-sortedmap-collection-iterable-iterator-navigableset-navigablemap) - [Почему `Map` — это не `Collection`, в то время как `List` и `Set` являются `Collection`?](#почему-map--это-не-collection-в-то-время-как-list-и-set-являются-collection) - [В чем разница между классами `java.util.Collection` и `java.util.Collections`?](#в-чем-разница-между-классами-javautilcollection-и-javautilcollections) - [Что такое «fail-fast поведение»?](#что-такое-fail-fast-поведение) - [Какая разница между fail-fast и fail-safe?](#какая-разница-между-fail-fast-и-fail-safe) - [Приведите примеры итераторов реализующих поведение fail-safe](#приведите-примеры-итераторов-реализующих-поведение-fail-safe) - [Чем различаются `Enumeration` и `Iterator`.](#чем-различаются-enumeration-и-iterator) - [Как между собой связаны `Iterable` и `Iterator`?](#как-между-собой-связаны-iterable-и-iterator) - [Как между собой связаны `Iterable`, `Iterator` и «for-each»?](#как-между-собой-связаны-iterable-iterator-и-for-each) - [Сравните `Iterator` и `ListIterator`.](#сравните-iterator-и-listiterator) - [Что произойдет при вызове `Iterator.next()` без предварительного вызова `Iterator.hasNext()`?](#что-произойдет-при-вызове-iteratornext-без-предварительного-вызова-iteratorhasnext) - [Сколько элементов будет пропущено, если `Iterator.next()` будет вызван после 10-ти вызовов `Iterator.hasNext()`?](#сколько-элементов-будет-пропущено-если-iteratornext-будет-вызван-после-10-ти-вызовов-iteratorhasnext) - [Как поведёт себя коллекция, если вызвать `iterator.remove()`?](#как-поведёт-себя-коллекция-если-вызвать-iteratorremove) - [Как поведёт себя уже инстанциированный итератор для `collection`, если вызвать `collection.remove()`?](#как-поведёт-себя-уже-инстанциированный-итератор-для-collection-если-вызвать-collectionremove) - [Как избежать `ConcurrentModificationException` во время перебора коллекции?](#как-избежать-concurrentmodificationexception-во-время-перебора-коллекции) - [Какая коллекция реализует дисциплину обслуживания FIFO?](#какая-коллекция-реализует-дисциплину-обслуживания-fifo) - [Какая коллекция реализует дисциплину обслуживания FILO?](#какая-коллекция-реализует-дисциплину-обслуживания-filo) - [Comparator vs Comparable](#comparator-vs-comparable) - [Чем отличается `ArrayList` от `Vector`?](#чем-отличается-arraylist-от-vector) - [Зачем добавили `ArrayList`, если уже был `Vector`?](#зачем-добавили-arraylist-если-уже-был-vector) - [Чем отличается `ArrayList` от `LinkedList`? В каких случаях лучше использовать первый, а в каких второй?](#чем-отличается-arraylist-от-linkedlist-в-каких-случаях-лучше-использовать-первый-а-в-каких-второй) - [Что работает быстрее `ArrayList` или `LinkedList`?](#что-работает-быстрее-arraylist-или-linkedlist) - [Какое худшее время работы метода `contains()` для элемента, который есть в `LinkedList`?](#какое-худшее-время-работы-метода-contains-для-элемента-который-есть-в-linkedlist) - [Какое худшее время работы метода `contains()` для элемента, который есть в `ArrayList`?](#какое-худшее-время-работы-метода-contains-для-элемента-который-есть-в-arraylist) - [Какое худшее время работы метода `add()` для `LinkedList`?](#какое-худшее-время-работы-метода-add-для-linkedlist) - [Какое худшее время работы метода `add()` для `ArrayList`?](#какое-худшее-время-работы-метода-add-для-arraylist) - [Необходимо добавить 1 млн. элементов, какую структуру вы используете?](#необходимо-добавить-1-млн-элементов-какую-структуру-вы-используете) - [Как происходит удаление элементов из `ArrayList`? Как меняется в этом случае размер `ArrayList`?](#как-происходит-удаление-элементов-из-arraylist-как-меняется-в-этом-случае-размер-arraylist) - [Предложите эффективный алгоритм удаления нескольких рядом стоящих элементов из середины списка, реализуемого `ArrayList`.](#предложите-эффективный-алгоритм-удаления-нескольких-рядом-стоящих-элементов-из-середины-списка-реализуемого-arraylist) - [Сколько необходимо дополнительной памяти при вызове `ArrayList.add()`?](#сколько-необходимо-дополнительной-памяти-при-вызове-arraylistadd) - [Сколько выделяется дополнительно памяти при вызове `LinkedList.add()`?](#сколько-выделяется-дополнительно-памяти-при-вызове-linkedlistadd) - [Оцените количество памяти на хранение одного примитива типа `byte` в `LinkedList`?](#оцените-количество-памяти-на-хранение-одного-примитива-типа-byte-в-linkedlist) - [Оцените количество памяти на хранение одного примитива типа `byte` в `ArrayList`?](#оцените-количество-памяти-на-хранение-одного-примитива-типа-byte-в-arraylist) - [Для `ArrayList` или для `LinkedList` операция добавления элемента в середину (`list.add(list.size()/2, newElement)`) медленнее?](#для-arraylist-или-для-linkedlist-операция-добавления-элемента-в-середину-listaddlistsize2-newelement-медленнее) - [В реализации класса `ArrayList` есть следующие поля: `Object[] elementData`, `int size`. Объясните, зачем хранить отдельно `size`, если всегда можно взять `elementData.length`?](#в-реализации-класса-arraylist-есть-следующие-поля-object-elementdata-int-size-объясните-зачем-хранить-отдельно-size-если-всегда-можно-взять-elementdatalength) - [Сравните интерфейсы `Queue` и `Deque`.](#сравните-интерфейсы-queue-и-deque) - [Кто кого расширяет: `Queue` расширяет `Deque`, или `Deque` расширяет `Queue`?](#кто-кого-расширяет-queue-расширяет-deque-или-deque-расширяет-queue) - [Почему `LinkedList` реализует и `List`, и `Deque`?](#почему-linkedlist-реализует-и-list-и-deque) - [`LinkedList` — это односвязный, двусвязный или четырехсвязный список?](#linkedlist--это-односвязный-двусвязный-или-четырехсвязный-список) - [Как перебрать элементы `LinkedList` в обратном порядке, не используя медленный `get(index)`?](#как-перебрать-элементы-linkedlist-в-обратном-порядке-не-используя-медленный-getindex) - [Что позволяет сделать `PriorityQueue`?](#что-позволяет-сделать-priorityqueue) - [`Stack` считается «устаревшим». Чем его рекомендуют заменять? Почему?](#stack-считается-устаревшим-чем-его-рекомендуют-заменять-почему) - [Зачем нужен `HashMap`, если есть `Hashtable`?](#зачем-нужен-hashmap-если-есть-hashtable) - [В чем разница между `HashMap` и `IdentityHashMap`? Для чего нужна `IdentityHashMap`?](#в-чем-разница-между-hashmap-и-identityhashmap-для-чего-нужна-identityhashmap) - [В чем разница между `HashMap` и `WeakHashMap`? Для чего используется `WeakHashMap`?](#в-чем-разница-между-hashmap-и-weakhashmap-для-чего-используется-weakhashmap) - [В `WeakHashMap` используются WeakReferences. А почему бы не создать `SoftHashMap` на SoftReferences?](#в-weakhashmap-используются-weakreferences-а-почему-бы-не-создать-softhashmap-на-softreferences) - [В `WeakHashMap` используются WeakReferences. А почему бы не создать `PhantomHashMap` на PhantomReferences?](#в-weakhashmap-используются-weakreferences-а-почему-бы-не-создать-phantomhashmap-на-phantomreferences) - [`LinkedHashMap` - что в нем от `LinkedList`, а что от `HashMap`?](#linkedhashmap---что-в-нем-от-linkedlist-а-что-от-hashmap) - [В чем проявляется «сортированность» `SortedMap`, кроме того, что `toString()` выводит все элементы по порядку?](#в-чем-проявляется-сортированность-sortedmap-кроме-того-что-tostring-выводит-все-элементы-по-порядку) - [Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресации и на основе метода цепочек. Как реализована `HashMap`? Почему, по вашему мнению, была выбрана именно эта реализация? В чем плюсы и минусы каждого подхода?](#согласно-кнуту-и-кормену-существует-две-основных-реализации-хэш-таблицы-на-основе-открытой-адресации-и-на-основе-метода-цепочек-как-реализована-hashmap-почему-по-вашему-мнению-была-выбрана-именно-эта-реализация-в-чем-плюсы-и-минусы-каждого-подхода) - [Как работает `HashMap` при попытке сохранить в него два элемента по ключам с одинаковым `hashCode()`, но для которых `equals() == false`?](#как-работает-hashmap-при-попытке-сохранить-в-него-два-элемента-по-ключам-с-одинаковым-hashcode-но-для-которых-equals--false) - [Какое начальное количество корзин в `HashMap`?](#какое-начальное-количество-корзин-в-hashmap) - [Какова оценка временной сложности операций над элементами из `HashMap`? Гарантирует ли `HashMap` указанную сложность выборки элемента?](#какова-оценка-временной-сложности-операций-над-элементами-из-hashmap-гарантирует-ли-hashmap-указанную-сложность-выборки-элемента) - [Возможна ли ситуация, когда `HashMap` выродится в список даже с ключами имеющими разные `hashCode()`?](#возможна-ли-ситуация-когда-hashmap-выродится-в-список-даже-с-ключами-имеющими-разные-hashcode) - [В каком случае может быть потерян элемент в `HashMap`?](#в-каком-случае-может-быть-потерян-элемент-в-hashmap) - [Почему нельзя использовать `byte[]` в качестве ключа в `HashMap`?](#почему-нельзя-использовать-byte-в-качестве-ключа-в-hashmap) - [Какова роль `equals()` и `hashCode()` в `HashMap`?](#какова-роль-equals-и-hashcode-в-hashmap) - [Каково максимальное число значений `hashCode()`?](#каково-максимальное-число-значений-hashcode) - [Какое худшее время работы метода get(key) для ключа, которого нет в `HashMap`?](#какое-худшее-время-работы-метода-getkey-для-ключа-которого-нет-в-hashmap) - [Сколько переходов происходит в момент вызова `HashMap.get(key)` по ключу, который есть в таблице?](#сколько-переходов-происходит-в-момент-вызова-hashmapgetkey-по-ключу-который-есть-в-таблице) - [Сколько создается новых объектов, когда вы добавляете новый элемент в `HashMap`?](#сколько-создается-новых-объектов-когда-вы-добавляете-новый-элемент-в-hashmap) - [Как и когда происходит увеличение количества корзин в `HashMap`?](#как-и-когда-происходит-увеличение-количества-корзин-в-hashmap) - [Объясните смысл параметров в конструкторе `HashMap(int initialCapacity, float loadFactor)`.](#объясните-смысл-параметров-в-конструкторе-hashmapint-initialcapacity-float-loadfactor) - [Будет ли работать `HashMap`, если все добавляемые ключи будут иметь одинаковый `hashCode()`?](#будет-ли-работать-hashmap-если-все-добавляемые-ключи-будут-иметь-одинаковый-hashcode) - [Как перебрать все ключи `Map`?](#как-перебрать-все-ключи-map) - [Как перебрать все значения `Map`?](#как-перебрать-все-значения-map) - [Как перебрать все пары «ключ-значение» в `Map`?](#как-перебрать-все-пары-ключ-значение-в-map) - [В чем отличия `TreeSet` и `HashSet`?](#в-чем-отличия-treeset-и-hashset) - [Что будет, если добавлять элементы в `TreeSet` по возрастанию?](#что-будет-если-добавлять-элементы-в-treeset-по-возрастанию) - [Чем `LinkedHashSet` отличается от `HashSet`?](#чем-linkedhashset-отличается-от-hashset) - [Для `Enum` есть специальный класс `java.util.EnumSet`. Зачем? Чем авторов не устраивал `HashSet` или `TreeSet`?](#для-enum-есть-специальный-класс-javautilenumset-зачем-чем-авторов-не-устраивал-hashset-или-treeset) - [Какие существуют способы перебирать элементы списка?](#какие-существуют-способы-перебирать-элементы-списка) - [Каким образом можно получить синхронизированные объекты стандартных коллекций?](#каким-образом-можно-получить-синхронизированные-объекты-стандартных-коллекций) - [Как получить коллекцию только для чтения?](#как-получить-коллекцию-только-для-чтения) - [Напишите однопоточную программу, которая заставляет коллекцию выбросить `ConcurrentModificationException`.](#напишите-однопоточную-программу-которая-заставляет-коллекцию-выбросить-concurrentmodificationexception) - [Приведите пример, когда какая-либо коллекция выбрасывает `UnsupportedOperationException`.](#приведите-пример-когда-какая-либо-коллекция-выбрасывает-unsupportedoperationexception) - [Реализуйте симметрическую разность двух коллекций используя методы `Collection` (`addAll(...)`, `removeAll(...)`, `retainAll(...)`).](#реализуйте-симметрическую-разность-двух-коллекций-используя-методы-collection-addall-removeall-retainall) - [Как, используя LinkedHashMap, сделать кэш c «invalidation policy»?](#как-используя-linkedhashmap-сделать-кэш-c-invalidation-policy) - [Как одной строчкой скопировать элементы любой `collection` в массив?](#как-одной-строчкой-скопировать-элементы-любой-collection-в-массив) - [Как одним вызовом из `List` получить `List` со всеми элементами, кроме первых и последних 3-х?](#как-одним-вызовом-из-list-получить-list-со-всеми-элементами-кроме-первых-и-последних-3-х) - [Как одной строчкой преобразовать `HashSet` в `ArrayList`?](#как-одной-строчкой-преобразовать-hashset-в-arraylist) - [Как одной строчкой преобразовать `ArrayList` в `HashSet`?](#как-одной-строчкой-преобразовать-arraylist-в-hashset) - [Сделайте `HashSet` из ключей `HashMap`.](#сделайте-hashset-из-ключей-hashmap) - [Сделайте `HashMap` из `HashSet>`.](#сделайте-hashmap-из-hashsetmapentryk-v) - [Источник](#источник) ## Что такое _«коллекция»_? _«Коллекция»_ - это структура данных, набор каких-либо объектов. Данными (объектами в наборе) могут быть числа, строки, объекты пользовательских классов и т.п. [к оглавлению](#java-collections-framework) ## Назовите основные интерфейсы JCF и их реализации. На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: `Collection` и `Map`. Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» соответственно. ![Image alt](https://github.com/Shell26/Java-Developer/raw/master/img/Core4.png) Интерфейс `Collection` расширяют интерфейсы: + `List` (список) представляет собой коллекцию, в которой допустимы дублирующие значения. Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу. Реализации: - `ArrayList` - инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов. Позволяет хранить любые данные, включая null в качестве элемента. - `LinkedList` (двунаправленный связный список) - состоит из узлов, каждый из которых содержит как собственно данные, так и две ссылки на следующий и предыдущий узел. Позволяет хранить любые данные, включая null. - `Vector` — реализация динамического массива объектов, методы которой синхронизированы. Позволяет хранить любые данные, включая null в качестве элемента. Синхронизирован, но как и Hashtable, эту коллекцию не рекомендуется использовать, если не требуется достижения потокобезопасности. - `Stack` — реализация стека LIFO (last-in-first-out). Является частично синхронизированной коллекцией (кроме метода добавления push() + `Set` (сет) описывает неупорядоченную коллекцию, не содержащую повторяющихся элементов. Реализации: - `HashSet` - использует HashMap для хранения данных. В качестве ключа используется добавляемый элемент, а в качестве значения — объект-пустышка new Object(). Из-за особенностей реализации порядок элементов не гарантируется при добавлении. - `LinkedHashSet` — гарантирует, что порядок элементов при обходе коллекции будет идентичен порядку добавления элементов. - `SortedSet` — расширяющий интерфейс `Set`, описывает упорядоченное множество, отсортированное в возрастающем порядке или по порядку, заданному реализацией интерфейса `Comparator`. - `TreeSet` — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта `Comparator`, либо сохраняет элементы с использованием «natural ordering». + `Queue` — (очередь) предназначена для хранения элементов с предопределённым способом вставки и извлечения FIFO (first-in-first-out): - `PriorityQueue` — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта `Comparator`, либо сохраняет элементы с использованием «natural ordering». - интерфейс `Deque` — расширяет вышеописанный интерфейс `Queue` и определяет поведение двунаправленной очереди, которая работает как обычная однонаправленная очередь, либо как стек, действующий по принципу LIFO (последний вошел - первый вышел). - `ArrayDeque` — реализация интерфейса `Deque`, который расширяет интерфейс `Queue` методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out). Интерфейс `Map` реализован классами: + `WeakHashMap` — реализация хэш-таблицы, которая организована с использованием _weak references_ для ключей (сборщик мусора автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элемента нет жёстких ссылок). + `Hashtable` — хэш-таблица, методы которой синхронизированы. Не позволяет использовать `null` в качестве значения или ключа и не является упорядоченной. + `HashMap` — хэш-таблица. Не синхронизирована, позволяет использовать `null` в качестве значения или ключа и не является упорядоченной. - `LinkedHashMap` — упорядоченная реализация хэш-таблицы, благодаря двунаправленным связям между элементами (аналогично LinkedList) + интерфейс `SortesMap` - интерфейс `NavigableMap` - `TreeMap` — реализация основанная на красно-чёрных деревьях. Является упорядоченной и предоставляет возможность управлять порядком элементов в коллекции при помощи объекта `Comparator`, либо сохраняет элементы с использованием «natural ordering». ![Image alt](https://github.com/Shell26/Java-Developer/raw/master/img/Core3.png) [к оглавлению](#java-collections-framework) ## Расположите в виде иерархии следующие интерфейсы: `List`, `Set`, `Map`, `SortedSet`, `SortedMap`, `Collection`, `Iterable`, `Iterator`, `NavigableSet`, `NavigableMap`. + `Iterable` + `Collection` + `List` + `Set` + `SortedSet` + `NavigableSet` + `Map` + `SortedMap` + `NavigableMap` + `Iterator` [к оглавлению](#java-collections-framework) ## Почему `Map` — это не `Collection`, в то время как `List` и `Set` являются `Collection`? `Collection` представляет собой совокупность некоторых элементов. `Map` - это совокупность пар «ключ-значение». [к оглавлению](#java-collections-framework) ## В чем разница между классами `java.util.Collection` и `java.util.Collections`? `java.util.Collections` - набор статических методов для работы с коллекциями. `java.util.Collection` - один из основных интерфейсов Java Collections Framework. [к оглавлению](#java-collections-framework) ## Что такое «fail-fast поведение»? __fail-fast поведение__ означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом. Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени. В Java Collections API некоторые итераторы ведут себя как fail-fast и выбрасывают `ConcurrentModificationException`, если после его создания была произведена модификация коллекции, т.е. добавлен или удален элемент напрямую из коллекции, а не используя методы итератора. Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count): + при изменении коллекции счетчик модификаций так же изменяется; + при создании итератора ему передается текущее значение счетчика; + при каждом обращении к итератору сохраненное значение счетчика сравнивается с текущим, и, если они не совпадают, возникает исключение. [к оглавлению](#java-collections-framework) ## Какая разница между fail-fast и fail-safe? В противоположность fail-fast, итераторы fail-safe не вызывают никаких исключений при изменении структуры, потому что они работают с клоном коллекции вместо оригинала. [к оглавлению](#java-collections-framework) ## Приведите примеры итераторов реализующих поведение fail-safe Итератор коллекции `CopyOnWriteArrayList` и итератор представления `keySet` коллекции `ConcurrentHashMap` являются примерами итераторов fail-safe. [к оглавлению](#java-collections-framework) ## Чем различаются `Enumeration` и `Iterator`. Хотя оба интерфейса и предназначены для обхода коллекций между ними имеются существенные различия: + с помощью `Enumeration` нельзя добавлять/удалять элементы; + в `Iterator` исправлены имена методов для повышения читаемости кода (`Enumeration.hasMoreElements()` соответствует `Iterator.hasNext()`, `Enumeration.nextElement()` соответствует `Iterator.next()` и т.д); + `Enumeration` присутствуют в устаревших классах, таких как `Vector`/`Stack`, тогда как `Iterator` есть во всех современных классах-коллекциях. [к оглавлению](#java-collections-framework) ## Как между собой связаны `Iterable` и `Iterator`? Интерфейс `Iterable` имеет только один метод - `iterator()`, который возвращает `Iterator`. [к оглавлению](#java-collections-framework) ## Как между собой связаны `Iterable`, `Iterator` и «for-each»? Классы, реализующие интерфейс `Iterable`, могут применяться в конструкции `for-each`, которая использует `Iterator`. [к оглавлению](#java-collections-framework) ## Сравните `Iterator` и `ListIterator`. + `ListIterator` расширяет интерфейс `Iterator` + `ListIterator` может быть использован только для перебора элементов коллекции `List`; + `Iterator` позволяет перебирать элементы только в одном направлении, при помощи метода `next()`. Тогда как `ListIterator` позволяет перебирать список в обоих направлениях, при помощи методов `next()` и `previous()`; + `ListIterator` не указывает на конкретный элемент: его текущая позиция располагается между элементами, которые возвращают методы `previous()` и `next()`. + При помощи `ListIterator` вы можете модифицировать список, добавляя/удаляя элементы с помощью методов `add()` и `remove()`. `Iterator` не поддерживает данного функционала. [к оглавлению](#java-collections-framework) ## Что произойдет при вызове `Iterator.next()` без предварительного вызова `Iterator.hasNext()`? Если итератор указывает на последний элемент коллекции, то возникнет исключение `NoSuchElementException`, иначе будет возвращен следующий элемент. [к оглавлению](#java-collections-framework) ## Сколько элементов будет пропущено, если `Iterator.next()` будет вызван после 10-ти вызовов `Iterator.hasNext()`? Нисколько - `hasNext()` осуществляет только проверку наличия следующего элемента. [к оглавлению](#java-collections-framework) ## Как поведёт себя коллекция, если вызвать `iterator.remove()`? Если вызову `iterator.remove()` предшествовал вызов `iterator.next()`, то `iterator.remove()` удалит элемент коллекции, на который указывает итератор, в противном случае будет выброшено `IllegalStateException()`. [к оглавлению](#java-collections-framework) ## Как поведёт себя уже инстанциированный итератор для `collection`, если вызвать `collection.remove()`? При следующем вызове методов итератора будет выброшено `ConcurrentModificationException`. [к оглавлению](#java-collections-framework) ## Как избежать `ConcurrentModificationException` во время перебора коллекции? + Попробовать подобрать другой итератор, работающий по принципу fail-safe. К примеру, для `List` можно использовать `ListIterator`. + Использовать `ConcurrentHashMap` и `CopyOnWriteArrayList`. + Преобразовать список в массив и перебирать массив. + Блокировать изменения списка на время перебора с помощью блока `synchronized`. Отрицательная сторона последних двух вариантов - ухудшение производительности. [к оглавлению](#java-collections-framework) ## Какая коллекция реализует дисциплину обслуживания FIFO? FIFO, First-In-First-Out («первым пришел-первым ушел») - по этому принципу построена коллекция `Queue`. [к оглавлению](#java-collections-framework) ## Какая коллекция реализует дисциплину обслуживания FILO? FILO, First-In-Last-Out («первым пришел, последним ушел») - по этому принципу построена коллекция `Stack`. [к оглавлению](#java-collections-framework) ## Comparator vs Comparable Интерфейс Comparable В нем находится всего один метод: ```java public interface Comparable { public int compareTo(T o); } ``` Вы могли заметить, что метод compareTo(T o) возвращает int. Он возвращает: + ноль, если два объекта равны; + +1, если первый объект (на котором вызывается метод) больше, чем второй (который передается в качестве параметра); + -1, если первый объект меньше второго. Давайте посмотрим на примере. Представим, что мы хотим сравнить два дома. Давайте у нас будет класс House: ```java public class House { int area; int price; String city; boolean hasFurniture; } ``` Как Вы можете видеть, у нас есть четыре параметра - размер дома, цена, город, в котором дом находится, и boolean "hasFurniture" ("продается ли дом с мебелью"). Мы НЕ сделали эти переменные приватными чтобы не отягощать код и не писать гетеры и сеттеры на каждый параметр - но Вы для практики можете это сделать 🙂 Давайте просто добавим конструктор и метод "вывести все параметры": ```java public class House { int area; int price; String city; boolean hasFurniture; public House(int area, int price, String city, boolean hasFurniture) { this.area = area; this.price = price; this.city = city; this.hasFurniture = hasFurniture; } @Override public String toString() { final StringBuffer sb = new StringBuffer("House{"); sb.append("area=").append(area); sb.append(", price=").append(price); sb.append(", city='").append(city).append('\''); sb.append(", hasFurniture=").append(hasFurniture); sb.append('}'); return sb.toString(); } } ``` Отлично! Но пока мы не можем сравнить два объекта типа House. Например, если мы попробуем создать TreeSet из объектов типа House (а TreeSet всегда сортирует свои элементы) и добавить туда элемент: ```java public class Test { public static void main(String[] args) { TreeSet myHouseArrayList = new TreeSet(); House firstHouse = new House(100, 120000, "Tokyo", true); myHouseArrayList.add(firstHouse); } } ``` получим ошибку. TreeSet сортирует свои элементы - но в данном случае сортировать у него не получится, поскольку он не знает, по какому критерию нужно сортировать Теперь, давайте имплементируем Comparable: ```java public class House implements Comparable{ int area; int price; String city; boolean hasFurniture; public House(int area, int price, String city, boolean hasFurniture) { this.area = area; this.price = price; this.city = city; this.hasFurniture = hasFurniture; } @Override public String toString() { final StringBuffer sb = new StringBuffer("House{"); sb.append("area=").append(area); sb.append(", price=").append(price); sb.append(", city='").append(city).append('\''); sb.append(", hasFurniture=").append(hasFurniture); sb.append('}'); return sb.toString(); } public int compareTo(House anotherHouse) { if (this.area == anotherHouse.area) { return 0; } else if (this.area < anotherHouse.area) { return -1; } else { return 1; } } } ``` Как видите, мы решили сортировать дома по площади. Теперь давайте создадим три объекта House и положим их в TreeSet: ```java public class Test { public static void main(String[] args) { TreeSet myHouseArrayList = new TreeSet(); House firstHouse = new House(100, 120000, "Tokyo", true); House secondHouse = new House(40, 70000, "Oxford", true); House thirdHouse = new House(70, 180000, "Paris", false); myHouseArrayList.add(firstHouse); myHouseArrayList.add(secondHouse); myHouseArrayList.add(thirdHouse); for (House h: myHouseArrayList) { System.out.println(h); } } } ``` На экране получим: ```java Area: 40, price: 70000, city: Oxford, hasFurniture: true Area: 70, price: 180000, city: Paris, hasFurniture: false Area: 100, price: 120000, city: Tokyo, hasFurniture: true Process finished with exit code 0 ``` Как видите, наши дома стоят не в порядке добавления (Токио, Оксфорд, Париж), а отсортированы по площади (Оксфорд, Париж, Токио). Ну, и ошибок, естественно, тоже нет. Кстати, метод compareTo(T o), который требует реализовать интерфейс Comparable, часто называют "естественным сравнением" ("natural comparison method") - т.е. методом по умолчанию. Основные типы (например, Integer, String, Float) уже имеют свои методы compareTo(T o). Тем не менее, если Вам нужен "нестандартный" вид сортировки - следует использовать __Comparator__. Интерфейс Comparator Итак, нестандартная сортировка. Допустим, мы все согласны что логичнее всего сравнивать дома по площади. Ну а если их нужно отсортировать, например, по цене? Для этой цели мы можем создать отдельный класс, который реализует интерфейс Comparator. Например, у нас уже есть класс House. Давайте создадим отдельный класс, которые будут выполнять функцию сравнения - PriceComparator: ```java public class PriceComparator implements Comparator { public int compare(House h1, House h2) { if (h1.price == h2.price) { return 0; } if (h1.price > h2.price) { return 1; } else { return -1; } } } ``` Обратите внимение: мы указываем тип объектов, которые хотим сравнивать (House) в скобках после слова "Comparator". Теперь давайте возьмем main из предыдущего примера, только поместим наши объекты не в TreeSet, а в ArrayList: ```java public class Test { public static void main(String[] args) { ArrayList myHouseArrayList = new ArrayList(); House firstHouse = new House(100, 120000, "Tokyo", true); House secondHouse = new House(40, 70000, "Oxford", true); House thirdHouse = new House(70, 180000, "Paris", false); myHouseArrayList.add(firstHouse); myHouseArrayList.add(secondHouse); myHouseArrayList.add(thirdHouse); for (House h: myHouseArrayList) { System.out.println(h); } } } ``` Если запустить этот код, то мы увидим, что все наши элементы лежат в порядке добавление - т.е. они не отсортированы. Теперь давайте создадим объект класса PriceComparator, а потом вызовем у нашего ArrayList метод sort(), который принимает на вход как раз объект класса, реализующего интерфейс Comparator, в нашем PriceComparator-а отсортируем наш ArrayList: ```java public class Test { public static void main(String[] args) { ArrayList myHouseArrayList = new ArrayList(); House firstHouse = new House(100, 120000, "Tokyo", true); House secondHouse = new House(40, 70000, "Oxford", true); House thirdHouse = new House(70, 180000, "Paris", false); myHouseArrayList.add(firstHouse); myHouseArrayList.add(secondHouse); myHouseArrayList.add(thirdHouse); for (House h: myHouseArrayList) { System.out.println(h); } PriceComparator myPriceComparator = new PriceComparator(); myHouseArrayList.sort(myPriceComparator); System.out.println("Sorted: "); for (House h: myHouseArrayList) { System.out.println(h); } } } ``` В консоли получим: ```java Area: 100, price: 120000, city: Tokyo, hasFurniture: true Area: 40, price: 70000, city: Oxford, hasFurniture: true Area: 70, price: 180000, city: Paris, hasFurniture: false Sorted: Area: 40, price: 70000, city: Oxford, hasFurniture: true Area: 100, price: 120000, city: Tokyo, hasFurniture: true Area: 70, price: 180000, city: Paris, hasFurniture: false Process finished with exit code 0 ``` Наши дома отсортированы по цене. ## Чем отличается `ArrayList` от `Vector`? ## Зачем добавили `ArrayList`, если уже был `Vector`? + Методы класса `Vector` синхронизированы, а `ArrayList` - нет; + По умолчанию, `Vector` удваивает свой размер, когда заканчивается выделенная под элементы память. `ArrayList` же увеличивает свой размер только на половину. `Vector` это устаревший класс и его использование не рекомендовано. [к оглавлению](#java-collections-framework) ## Чем отличается `ArrayList` от `LinkedList`? В каких случаях лучше использовать первый, а в каких второй? `ArrayList` это список, реализованный на основе массива, а `LinkedList` — это классический двусвязный список, основанный на объектах с ссылками между ними. `ArrayList`: + доступ к произвольному элементу по индексу за время _O(1)_; + доступ к элементам по значению за линейное время _O(N)_; + вставка в конец в среднем производится за время _O(1)_; + удаление произвольного элемента из списка занимает значительное время т.к. при этом все элементы находящиеся «правее» смещаются на одну ячейку влево (реальный размер массива (capacity) не изменяется); + вставка элемента в произвольное место списка занимает значительное время т.к. при этом все элементы находящиеся «правее» смещаются на одну ячейку вправо; + минимум накладных расходов при хранении. `LinkedList`: + на получение элемента по индексу или значению потребуется линейное время _O(N)_; + на добавление и удаление в начало или конец списка потребуется _O(1)_; + вставка или удаление в/из произвольного место _O(N)_; + требует больше памяти для хранения такого же количества элементов, потому что кроме самого элемента хранятся еще указатели на следующий и предыдущий элементы списка. В целом, `LinkedList` в абсолютных величинах проигрывает `ArrayList` и по потребляемой памяти и по скорости выполнения операций. `LinkedList` предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список. [к оглавлению](#java-collections-framework) ## Что работает быстрее `ArrayList` или `LinkedList`? Смотря какие действия будут выполняться над структурой. см. [Чем отличается `ArrayList` от `LinkedList`](#Чем-отличается-arraylist-от-linkedlist-В-каких-случаях-лучше-использовать-первый-а-в-каких-второй) [к оглавлению](#java-collections-framework) ## Какое худшее время работы метода `contains()` для элемента, который есть в `LinkedList`? _O(N)_. Время поиска элемента линейно пропорционально количеству элементов с списке. [к оглавлению](#java-collections-framework) ## Какое худшее время работы метода `contains()` для элемента, который есть в `ArrayList`? _O(N)_. Время поиска элемента линейно пропорционально количеству элементов с списке. [к оглавлению](#java-collections-framework) ## Какое худшее время работы метода `add()` для `LinkedList`? _O(N)_. Добавление в начало/конец списка осуществляется за время _O(1)_. [к оглавлению](#java-collections-framework) ## Какое худшее время работы метода `add()` для `ArrayList`? _O(N)_. Вставка элемента в конец списка осуществляется за время _O(1)_, но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый. [к оглавлению](#java-collections-framework) ## Необходимо добавить 1 млн. элементов, какую структуру вы используете? Однозначный ответ можно дать только исходя из информации о том в какую часть списка происходит добавление элементов, что потом будет происходить с элементами списка, существуют ли какие-то ограничения по памяти или скорости выполнения. см. [Чем отличается `ArrayList` от `LinkedList`](#Чем-отличается-arraylist-от-linkedlist-В-каких-случаях-лучше-использовать-первый-а-в-каких-второй) [к оглавлению](#java-collections-framework) ## Как происходит удаление элементов из `ArrayList`? Как меняется в этом случае размер `ArrayList`? При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево и реальный размер массива (его емкость, capacity) не изменяется никак. Механизм автоматического «расширения» массива существует, а вот автоматического «сжатия» нет, можно только явно выполнить «сжатие» командой `trimToSize()`. [к оглавлению](#java-collections-framework) ## Предложите эффективный алгоритм удаления нескольких рядом стоящих элементов из середины списка, реализуемого `ArrayList`. Допустим нужно удалить `n` элементов с позиции `m` в списке. Вместо выполнения удаления одного элемента `n` раз (каждый раз смещая на 1 позицию элементы, стоящие «правее» в списке), нужно выполнить смещение всех элементов, стоящих «правее» `n + m` позиции на `n` элементов «левее» к началу списка. Таким образом, вместо выполнения `n` итераций перемещения элементов списка, все выполняется за 1 проход. [к оглавлению](#java-collections-framework) ## Сколько необходимо дополнительной памяти при вызове `ArrayList.add()`? Если в массиве достаточно места для размещения нового элемента, то дополнительной памяти не требуется. Иначе происходит создание нового массива размером в 1,5 раза превышающим существующий (это верно для JDK выше 1.7, в более ранних версиях размер увеличения иной). [к оглавлению](#java-collections-framework) ## Сколько выделяется дополнительно памяти при вызове `LinkedList.add()`? Создается один новый экземпляр вложенного класса `Node`. [к оглавлению](#java-collections-framework) ## Оцените количество памяти на хранение одного примитива типа `byte` в `LinkedList`? Каждый элемент `LinkedList` хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные. ```java private static class Node { E item; Node next; Node prev; //... } ``` Для 32-битных систем каждая ссылка занимает 32 бита (4 байта). Сам объект (заголовок) вложенного класса `Node` занимает 8 байт. 4 + 4 + 4 + 8 = 20 байт, а т.к. размер каждого объекта в Java кратен 8, соответственно получаем 24 байта. Примитив типа `byte` занимает 1 байт памяти, но в JCF примитивы упаковываются: объект типа `Byte` занимает в памяти 16 байт (8 байт на заголовок объекта, 1 байт на поле типа `byte` и 7 байт для кратности 8). Также напомню, что значения от -128 до 127 кэшируются и для них новые объекты каждый раз не создаются. Таким образом, в x32 JVM 24 байта тратятся на хранение одного элемента в списке и 16 байт - на хранение упакованного объекта типа `Byte`. Итого 40 байт. Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны: 8 + 8 + 8 + 16 = 40байт и 24 байта. Итого 64 байта. [к оглавлению](#java-collections-framework) ## Оцените количество памяти на хранение одного примитива типа `byte` в `ArrayList`? `ArrayList` основан на массиве, для примитивных типов данных осуществляется автоматическая упаковка значения, поэтому 16 байт тратится на хранение упакованного объекта и 4 байта (8 для x64) - на хранение ссылки на этот объект в самой структуре данных. Таким образом, в x32 JVM 4 байта используются на хранение одного элемента и 16 байт - на хранение упакованного объекта типа `Byte`. Для x64 - 8 байт и 24 байта соотвтетсвенно. [к оглавлению](#java-collections-framework) ## Для `ArrayList` или для `LinkedList` операция добавления элемента в середину (`list.add(list.size()/2, newElement)`) медленнее? Для `ArrayList`: + проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив (_O(N)_); + копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо (_O(N)_); + вставка элемента (_O(1)_). Для `LinkedList`: + поиск позиции вставки (_O(N)_); + вставка элемента (_O(1)_). В худшем случае вставка в середину списка эффективнее для `LinkedList`. В остальных - скорее всего, для `ArrayList`, поскольку копирование элементов осуществляется за счет вызова быстрого системного метода `System.arraycopy()`. [к оглавлению](#java-collections-framework) ## В реализации класса `ArrayList` есть следующие поля: `Object[] elementData`, `int size`. Объясните, зачем хранить отдельно `size`, если всегда можно взять `elementData.length`? Размер массива `elementData` представляет собой вместимость (capacity) `ArrayList`, которая всегда больше переменной `size` - реального количества хранимых элементов. При необходимости вместимость автоматически возрастает. [к оглавлению](#java-collections-framework) ## Сравните интерфейсы `Queue` и `Deque`. ## Кто кого расширяет: `Queue` расширяет `Deque`, или `Deque` расширяет `Queue`? `Queue` - это очередь, которая обычно (но необязательно) строится по принципу FIFO (First-In-First-Out) - соответственно извлечение элемента осуществляется с начала очереди, вставка элемента - в конец очереди. Хотя этот принцип нарушает, к примеру `PriorityQueue`, использующая «natural ordering» или переданный `Comparator` при вставке нового элемента. `Deque` (Double Ended Queue) расширяет `Queue` и согласно документации это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого реализации интерфейса `Deque` могут строится по принципу FIFO, либо LIFO. Реализации и `Deque`, и `Queue` обычно не переопределяют методы `equals()` и `hashCode()`, вместо этого используются унаследованные методы класса Object, основанные на сравнении ссылок. [к оглавлению](#java-collections-framework) ## Почему `LinkedList` реализует и `List`, и `Deque`? `LinkedList` позволяет добавлять элементы в начало и конец списка за константное время, что хорошо согласуется с поведением интерфейса `Deque`. [к оглавлению](#java-collections-framework) ## `LinkedList` — это односвязный, двусвязный или четырехсвязный список? `Двусвязный`: каждый элемент `LinkedList` хранит ссылку на предыдущий и следующий элементы. [к оглавлению](#java-collections-framework) ## Как перебрать элементы `LinkedList` в обратном порядке, не используя медленный `get(index)`? Для этого в `LinkedList` есть обратный итератор, который можно получить вызва метод `descendingIterator()`. [к оглавлению](#java-collections-framework) ## Что позволяет сделать `PriorityQueue`? Особенностью `PriorityQueue` является возможность управления порядком элементов. По-умолчанию, элементы сортируются с использованием «natural ordering», но это поведение может быть переопределено при помощи объекта `Comparator`, который задаётся при создании очереди. Данная коллекция не поддерживает null в качестве элементов. Используя `PriorityQueue`, можно, например, реализовать алгоритм Дейкстры для поиска кратчайшего пути от одной вершины графа к другой. Либо для хранения объектов согласно определённого свойства. [к оглавлению](#java-collections-framework) ## `Stack` считается «устаревшим». Чем его рекомендуют заменять? Почему? `Stack` был добавлен в Java 1.0 как реализация стека LIFO (last-in-first-out) и является расширением коллекции `Vector`, хотя это несколько нарушает понятие стека (например, класс `Vector` предоставляет возможность обращаться к любому элементу по индексу). Является частично синхронизированной коллекцией (кроме метода добавления `push()`) с вытекающими отсюда последствиями в виде негативного воздействия на производительность. После добавления в Java 1.6 интерфейса `Deque`, рекомендуется использовать реализации именно этого интерфейса, например `ArrayDeque`. [к оглавлению](#java-collections-framework) ## Зачем нужен `HashMap`, если есть `Hashtable`? + Методы класса `Hashtable` синхронизированы, что приводит к снижению производительности, а `HashMap` - нет; + `HashTable` не может содержать элементы `null`, тогда как `HashMap` может содержать один ключ `null` и любое количество значений `null`; + Iterator у `HashMap`, в отличие от Enumeration у `HashTable`, работает по принципу «fail-fast» (выдает исключение при любой несогласованности данных). `Hashtable` это устаревший класс и его использование не рекомендовано. [к оглавлению](#java-collections-framework) ## В чем разница между `HashMap` и `IdentityHashMap`? Для чего нужна `IdentityHashMap`? `IdentityHashMap` - это структура данных, так же реализующая интерфейс `Map` и использующая при сравнении ключей (значений) сравнение ссылок, а не вызов метода `equals()`. Другими словами, в `IdentityHashMap` два ключа `k1` и `k2` будут считаться равными, если они указывают на один объект, т.е. выполняется условие `k1` == `k2`. `IdentityHashMap` не использует метод `hashCode()`, вместо которого применяется метод `System.identityHashCode()`, по этой причине `IdentityHashMap` по сравнению с `HashMap` имеет более высокую производительность, особенно если последний хранит объекты с дорогостоящими методами `equals()` и `hashCode()`. Одним из основных требований к использованию `HashMap` является неизменяемость ключа, а, т.к. `IdentityHashMap` не использует методы `equals()` и `hashCode()`, то это правило на него не распространяется. `IdentityHashMap` может применяться для реализации сериализации/клонирования. При выполнении подобных алгоритмов программе необходимо обслуживать хэш-таблицу со всеми ссылками на объекты, которые уже были обработаны. Такая структура не должна рассматривать уникальные объекты как равные, даже если метод `equals()` возвращает `true`. [к оглавлению](#java-collections-framework) ## В чем разница между `HashMap` и `WeakHashMap`? Для чего используется `WeakHashMap`? В Java существует 4 типа ссылок: _сильные (strong reference)_, _мягкие (SoftReference)_, _слабые (WeakReference)_ и _фантомные (PhantomReference)_. Особенности каждого типа ссылок связаны с работой Garbage Collector. Если объект можно достичь только с помощью цепочки WeakReference (то есть на него отсутствуют сильные и мягкие ссылки), то данный объект будет помечен на удаление. `WeakHashMap` - это структура данных, реализующая интерфейс `Map` и основанная на использовании WeakReference для хранения ключей. Таким образом, пара «ключ-значение» будет удалена из `WeakHashMap`, если на объект-ключ более не имеется сильных ссылок. В качестве примера использования такой структуры данных можно привести следующую ситуацию: допустим имеются объекты, которые необходимо расширить дополнительной информацией, при этом изменение класса этих объектов нежелательно либо невозможно. В этом случае добавляем каждый объект в `WeakHashMap` в качестве ключа, а в качестве значения - нужную информацию. Таким образом, пока на объект имеется сильная ссылка (либо мягкая), можно проверять хэш-таблицу и извлекать информацию. Как только объект будет удален, то WeakReference для этого ключа будет помещен в ReferenceQueue и затем соответствующая запись для этой слабой ссылки будет удалена из `WeakHashMap`. [к оглавлению](#java-collections-framework) ## В `WeakHashMap` используются WeakReferences. А почему бы не создать `SoftHashMap` на SoftReferences? `SoftHashMap` представлена в сторонних библиотеках, например, в `Apache Commons`. [к оглавлению](#java-collections-framework) ## В `WeakHashMap` используются WeakReferences. А почему бы не создать `PhantomHashMap` на PhantomReferences? PhantomReference при вызове метода `get()` возвращает всегда `null`, поэтому тяжело представить назначение такой структуры данных. [к оглавлению](#java-collections-framework) ## `LinkedHashMap` - что в нем от `LinkedList`, а что от `HashMap`? Реализация `LinkedHashMap` отличается от `HashMap` поддержкой двухсвязанного списка, определяющего порядок итерации по элементам структуры данных. По умолчанию элементы списка упорядочены согласно их порядку добавления в `LinkedHashMap` (insertion-order). Однако порядок итерации можно изменить, установив параметр конструктора `accessOrder` в значение `true`. В этом случае доступ осуществляется по порядку последнего обращения к элементу (access-order). Это означает, что при вызове методов `get()` или `put()` элемент, к которому обращаемся, перемещается в конец списка. При добавлении элемента, который уже присутствует в `LinkedHashMap` (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется. [к оглавлению](#java-collections-framework) ## В чем проявляется «сортированность» `SortedMap`, кроме того, что `toString()` выводит все элементы по порядку? Так же оно проявляется при итерации по коллекции. [к оглавлению](#java-collections-framework) ## Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресации и на основе метода цепочек. Как реализована `HashMap`? Почему, по вашему мнению, была выбрана именно эта реализация? В чем плюсы и минусы каждого подхода? `HashMap` реализован с использованием метода цепочек, т.е. каждой ячейке массива (корзине) соответствует свой связный список и при возникновении коллизии осуществляется добавление нового элемента в этот список. Для метода цепочек коэффициент заполнения может быть больше 1 и с увеличением числа элементов производительность убывает линейно. Такие таблицы удобно использовать, если заранее неизвестно количество хранимых элементов, либо их может быть достаточно много, что приводит к большим значениям коэффициента заполнения. Среди методов открытой реализации различают: + линейное пробирование; + квадратичное пробирование; + двойное хэширование. Недостатки структур с методом открытой адресации: + Количество элементов в хэш-таблице не может превышать размера массива. По мере увеличения числа элементов и повышения коэффициента заполнения производительность структуры резко падает, поэтому необходимо проводить перехэширование. + Сложно организовать удаление элемента. + Первые два метода открытой адресации приводят к проблеме первичной и вторичной группировок. Преимущества хэш-таблицы с открытой адресацией: + отсутствие затрат на создание и хранение объектов списка; + простота организации сериализации/десериализации объекта. [к оглавлению](#java-collections-framework) ## Как работает `HashMap` при попытке сохранить в него два элемента по ключам с одинаковым `hashCode()`, но для которых `equals() == false`? По значению `hashCode()` вычисляется индекс ячейки массива, в список которой этот элемент будет добавлен. Перед добавлением осуществляется проверка на наличие элементов в этой ячейке. Если элементы с таким `hashCode()` уже присутствует, но их `equals()` методы не равны, то элемент будет добавлен в конец списка. [к оглавлению](#java-collections-framework) ## Какое начальное количество корзин в `HashMap`? В конструкторе по умолчанию - 16, используя конструкторы с параметрами можно задавать произвольное начальное количество корзин. [к оглавлению](#java-collections-framework) ## Какова оценка временной сложности операций над элементами из `HashMap`? Гарантирует ли `HashMap` указанную сложность выборки элемента? В общем случае операции добавления, поиска и удаления элементов занимают константное время. Данная сложность не гарантируется, т.к. если хэш-функция распределяет элементы по корзинам равномерно, временная сложность станет не хуже _O(lg(N))_, а в случае, когда хэш-функция постоянно возвращает одно и то же значение `HashMap` превратится в связный список со сложностью О(n) . [к оглавлению](#java-collections-framework) ## Возможна ли ситуация, когда `HashMap` выродится в список даже с ключами имеющими разные `hashCode()`? Это возможно в случае, если метод, определяющий номер корзины будет возвращать одинаковые значения. [к оглавлению](#java-collections-framework) ## В каком случае может быть потерян элемент в `HashMap`? Допустим, в качестве ключа используется не примитив, а объект с несколькими полями. После добавления элемента в `HashMap` у объекта, который выступает в качестве ключа, изменяют одно поле, которое участвует в вычислении хэш-кода. В результате при попытке найти данный элемент по исходному ключу, будет происходить обращение к правильной корзине, а вот `equals` уже не найдет указанный ключ в списке элементов. Тем не менее, даже если `equals` реализован таким образом, что изменение данного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хэш-кодов элементов, указанный элемент, с измененным значением поля, с большой долей вероятности попадет в совершенно другую корзину и тогда уже потеряется совсем. [к оглавлению](#java-collections-framework) ## Почему нельзя использовать `byte[]` в качестве ключа в `HashMap`? Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному `Object.hashCode()` на основании адреса массива). Так же у массивов не переопределен `equals` и выполняется сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента. [к оглавлению](#java-collections-framework) ## Какова роль `equals()` и `hashCode()` в `HashMap`? `hashCode` позволяет определить корзину для поиска элемента, а `equals` используется для сравнения ключей элементов в списке корзины и искомого ключа. [к оглавлению](#java-collections-framework) ## Каково максимальное число значений `hashCode()`? Число значений следует из сигнатуры `int hashCode()` и равно диапазону типа `int` — __232__. [к оглавлению](#java-collections-framework) ## Какое худшее время работы метода get(key) для ключа, которого нет в `HashMap`? ___O(N)___. Худший случай - это поиск ключа в `HashMap`, вырожденного в список по причине совпадения ключей по `hashCode()` и для выяснения хранится ли элемент с определённым ключом может потребоваться перебор всего списка. [к оглавлению](#java-collections-framework) ## Сколько переходов происходит в момент вызова `HashMap.get(key)` по ключу, который есть в таблице? + ключ равен `null`: __1__ - выполняется единственный метод `getForNullKey()`. + любой ключ отличный от `null`: __4__ - вычисление хэш-кода ключа; определение номера корзины; поиск значения; возврат значения. [к оглавлению](#java-collections-framework) ## Сколько создается новых объектов, когда вы добавляете новый элемент в `HashMap`? __Один__ новый объект статического вложенного класса `Entry`. [к оглавлению](#java-collections-framework) ## Как и когда происходит увеличение количества корзин в `HashMap`? Помимо `capacity` у `HashMap` есть еще поле `loadFactor`, на основании которого, вычисляется предельное количество занятых корзин `capacity * loadFactor`. По умолчанию `loadFactor = 0.75`. По достижению предельного значения, число корзин увеличивается в 2 раза и для всех хранимых элементов вычисляется новое «местоположение» с учетом нового числа корзин. [к оглавлению](#java-collections-framework) ## Объясните смысл параметров в конструкторе `HashMap(int initialCapacity, float loadFactor)`. + `initialCapacity` - исходный размер `HashMap`, количество корзин в хэш-таблице в момент её создания. + `loadFactor` - коэффициент заполнения `HashMap`, при превышении которого происходит увеличение количества корзин и автоматическое перехэширование. Равен отношению числа уже хранимых элементов в таблице к её размеру. [к оглавлению](#java-collections-framework) ## Будет ли работать `HashMap`, если все добавляемые ключи будут иметь одинаковый `hashCode()`? Да, будет, но в этом случае `HashMap` вырождается в связный список и теряет свои преимущества. ## Как перебрать все ключи `Map`? Использовать метод `keySet()`, который возвращает множество `Set` ключей. [к оглавлению](#java-collections-framework) ## Как перебрать все значения `Map`? Использовать метод `values()`, который возвращает коллекцию `Collection` значений. [к оглавлению](#java-collections-framework) ## Как перебрать все пары «ключ-значение» в `Map`? Использовать метод `entrySet()`, который возвращает множество `Set` пар «ключ-значение». [к оглавлению](#java-collections-framework) ## В чем отличия `TreeSet` и `HashSet`? `TreeSet` обеспечивает упорядоченно хранение элементов в виде красно-черного дерева. Сложность выполнения основных операций не хуже _O(lg(N))_. `HashSet` использует для хранения элементов такой же подход, что и `HashMap`, за тем отличием, что в `HashSet` в качестве ключа и значения выступает сам `элемент`, кроме того `HashSet` не поддерживает упорядоченное хранение элементов и обеспечивает временную сложность выполнения операций аналогично `HashMap`. [к оглавлению](#java-collections-framework) ## Что будет, если добавлять элементы в `TreeSet` по возрастанию? В основе `TreeSet` лежит красно-черное дерево, которое умеет само себя балансировать. В итоге, `TreeSet` все равно в каком порядке вы добавляете в него элементы, преимущества этой структуры данных будут сохраняться. [к оглавлению](#java-collections-framework) ## Чем `LinkedHashSet` отличается от `HashSet`? `LinkedHashSet` отличается от `HashSet` только тем, что в его основе лежит `LinkedHashMap` вместо `HashMap`. Благодаря этому порядок элементов при обходе коллекции является идентичным порядку добавления элементов (insertion-order). При добавлении элемента, который уже присутствует в `LinkedHashSet` (т.е. с одинаковым ключом), порядок обхода элементов не изменяется. [к оглавлению](#java-collections-framework) ## Для `Enum` есть специальный класс `java.util.EnumSet`. Зачем? Чем авторов не устраивал `HashSet` или `TreeSet`? `EnumSet` - это реализация интерфейса `Set` для использования с перечислениями (`Enum`). В структуре данных хранятся объекты только одного типа `Enum`, указываемого при создании. Для хранения значений `EnumSet` использует массив битов (_bit vector_), - это позволяет получить высокую компактность и эффективность. Проход по `EnumSet` осуществляется согласно порядку объявления элементов перечисления. Все основные операции выполняются за _O(1)_ и обычно (но негарантированно) быстрей аналогов из `HashSet`, а пакетные операции (_bulk operations_), такие как `containsAll()` и `retainAll()` выполняются даже горазда быстрей. Помимо всего `EnumSet` предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров. [к оглавлению](#java-collections-framework) ## Какие существуют способы перебирать элементы списка? + Цикл с итератором ```java Iterator iterator = list.iterator(); while (iterator.hasNext()) { //iterator.next(); } ``` + Цикл `for` ```java for (int i = 0; i < list.size(); i++) { //list.get(i); } ``` + Цикл `while` ```java int i = 0; while (i < list.size()) { //list.get(i); i++; } ``` + «for-each» ```java for (String element : list) { //element; } ``` [к оглавлению](#java-collections-framework) ## Каким образом можно получить синхронизированные объекты стандартных коллекций? С помощью статических методов `synchronizedMap()` и `synchronizedList()` класса `Collections`. Данные методы возвращают синхронизированный декоратор переданной коллекции. При этом все равно в случае обхода по коллекции требуется ручная синхронизация. ```java Map m = Collections.synchronizedMap(new HashMap()); List l = Collections.synchronizedList(new ArrayList()); ``` Начиная с Java 6 JCF был расширен специальными коллекциями, поддерживающими многопоточный доступ, такими как `CopyOnWriteArrayList` и `ConcurrentHashMap`. [к оглавлению](#java-collections-framework) ## Как получить коллекцию только для чтения? При помощи: + `Collections.unmodifiableList(list)`; + `Collections.unmodifiableSet(set)`; + `Collections.unmodifiableMap(map)`. Эти методы принимают коллекцию в качестве параметра, и возвращают коллекцию только для чтения с теми же элементами внутри. [к оглавлению](#java-collections-framework) ## Напишите однопоточную программу, которая заставляет коллекцию выбросить `ConcurrentModificationException`. ```java public static void main(String[] args) { List list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); for (Integer integer : list) { list.remove(1); } } ``` [к оглавлению](#java-collections-framework) ## Приведите пример, когда какая-либо коллекция выбрасывает `UnsupportedOperationException`. ```java public static void main(String[] args) { List list = Collections.emptyList(); list.add(0); } ``` [к оглавлению](#java-collections-framework) ## Реализуйте симметрическую разность двух коллекций используя методы `Collection` (`addAll(...)`, `removeAll(...)`, `retainAll(...)`). Симметрическая разность двух коллекций - это множество элементов, одновременно не принадлежащих обоим исходным коллекциям. ```java Collection symmetricDifference(Collection a, Collection b) { // Объединяем коллекции. Collection result = new ArrayList<>(a); result.addAll(b); // Получаем пересечение коллекций. Collection intersection = new ArrayList<>(a); intersection.retainAll(b); // Удаляем элементы, расположенные в обоих коллекциях. result.removeAll(intersection); return result; } ``` [к оглавлению](#java-collections-framework) ## Как, используя LinkedHashMap, сделать кэш c «invalidation policy»? Необходимо использовать _LRU-алгоритм (Least Recently Used algorithm)_ и `LinkedHashMap` с access-order. В этом случае при обращении к элементу он будет перемещаться в конец списка, а наименее используемые элементы будут постепенно группироваться в начале списка. Так же в стандартной реализации `LinkedHashMap` есть метод `removeEldestEntries()`, который возвращает `true`, если текущий объект `LinkedHashMap` должен удалить наименее используемый элемент из коллекции при использовании методов `put()` и `putAll()`. ```java public class LRUCache extends LinkedHashMap { private static final int MAX_ENTRIES = 10; public LRUCache(int initialCapacity) { super(initialCapacity, 0.85f, true); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES; } } ``` Стоит заметить, что `LinkedHashMap` не позволяет полностью реализовать LRU-алгоритм, поскольку при вставке уже имеющегося в коллекции элемента порядок итерации по элементам не меняется. [к оглавлению](#java-collections-framework) ## Как одной строчкой скопировать элементы любой `collection` в массив? ```java Object[] array = collection.toArray(); ``` [к оглавлению](#java-collections-framework) ## Как одним вызовом из `List` получить `List` со всеми элементами, кроме первых и последних 3-х? ```java List subList = list.subList(3, list.size() - 3); ``` [к оглавлению](#java-collections-framework) ## Как одной строчкой преобразовать `HashSet` в `ArrayList`? ```java ArrayList list = new ArrayList<>(new HashSet<>()); ``` [к оглавлению](#java-collections-framework) ## Как одной строчкой преобразовать `ArrayList` в `HashSet`? ```java HashSet set = new HashSet<>(new ArrayList<>()); ``` [к оглавлению](#java-collections-framework) ## Сделайте `HashSet` из ключей `HashMap`. ```java HashSet set = new HashSet<>(map.keySet()); ``` [к оглавлению](#java-collections-framework) ## Сделайте `HashMap` из `HashSet>`. ```java HashMap map = new HashMap<>(set.size()); for (Map.Entry entry : set) { map.put(entry.getKey(), entry.getValue()); } ``` [к оглавлению](#java-collections-framework) # Источник + [parshinpn.pro](http://www.parshinpn.pro/content/voprosy-i-otvety-na-sobesedovanii-po-teme-java-collection-framework-chast-1) + [Хабрахабр](https://habrahabr.ru/post/162017/) + [Quizful](http://www.quizful.net/interview/java) + [JavaRush](http://info.javarush.ru/) + [Хабрахабр:Справочник по Java Collections Framework](https://habrahabr.ru/post/237043/) [Вопросы для собеседования](README.md) 1. Что такое Java-коллекции? 2. Какие интерфейсы являются основными интерфейсами коллекций в Java? 3. Какие классы реализуют основные интерфейсы коллекций в Java? 4. Чем отличаются ArrayList и LinkedList? В каких случаях лучше использовать одну или другую коллекцию? 5. Какие методы есть у List? 6. Какие методы есть у Set? 7. Какие методы есть у Map? 8. Что такое fail-fast поведение в коллекциях? 9. Какие коллекции в Java упорядочены? 10. Какие коллекции в Java разрешают дубликаты элементов? 11. Какие коллекции в Java не разрешают дубликаты элементов? 12. Что такое capacity у ArrayList и HashMap? 13. Как работает hashCode() и equals() в Java? 14. Какие алгоритмы используются для хранения элементов в HashSet и HashMap? 15. Что такое TreeMap? Как он отличается от HashMap? 16. Какие методы есть у PriorityQueue? 17. Что такое Comparator? Как он используется? 18. Каким образом можно отсортировать элементы в ArrayList? 19. Какие интерфейсы необходимо реализовать, чтобы класс стал сравнимым? 20. Что такое обобщенные типы в Java? Как они используются при работе с коллекциями? 21. Какие методы есть у Collections? 22. Какие методы есть у Arrays? 23. Какой интерфейс нужно реализовать, чтобы создать свою собственную коллекцию? 24. Как работает итератор в Java-коллекциях? 25. Как добавлять элементы в конец списка? 26. Что произойдет, если попытаться добавить null-элемент в LinkedList или HashSet? 27. Что такое weak reference в Java и как он используется в коллекциях? 28. Каким образом можно создать immutable коллекции в Java? 29. Что такое ConcurrentModificationException и как ее избежать? 30. Как использовать Stream API для работы с коллекциями? 31. Какие коллекции в Java являются потокобезопасными? 32. Чем отличается ConcurrentHashMap от HashMap? 33. Какие коллекции лучше использовать, если нужно обеспечить уникальность элементов и быстрый доступ к ним? 34. Можно ли использовать null-ключ в HashMap? 35. Какой метод используется для удаления элемента из ArrayList? 36. Каким образом можно создать копию коллекции в Java? 37. Как работает метод subList() в List? 38. Какие коллекции могут быть использованы для реализации стека или очереди? 39. Как сравнить две коллекции на равенство? 40. Как добавить все элементы одной коллекции в другую коллекцию? 41. Как отсортировать список с помощью Comparator? 42. Как получить первый (или последний) элемент из LinkedList? 43. Что такое ListIterator? Как он используется? 44. Как удалить дубликаты элементов из списка? 45. Как производится сортировка в TreeMap? 46. Как создать неизменяемую карту в Java? 47. Какие коллекции в Java поддерживают обратный порядок элементов? 48. Как удалить все элементы из коллекции? 49. Как проверить, содержит ли коллекция определенный элемент? 50. Как получить количество элементов в коллекции? 51. Каким образом можно сравнить две карты (Map) на равенство? 52. Что такое LinkedHashMap? Как он отличается от HashMap? 53. Можно ли использовать TreeSet с объектами не реализующими интерфейс Comparable? 54. Как создать TreeMap, который будет сортироваться по значению, а не по ключу? 55. Что такое IdentityHashMap? В каких случаях он может быть полезен? 56. Как удалить все элементы из HashSet? 57. Как получить подмножество элементов из Set? 58. Как перемешать элементы в ArrayList? 59. Как сделать копию HashMap? 60. Как проверить, является ли коллекция пустой? 61. Каким образом можно превратить массив в список (List)? 62. Как проверить, содержится ли определенное значение в Map? 63. Как отсортировать HashMap? 64. Как производится сортировка в PriorityQueue? 65. Как узнать, есть ли определенный ключ в HashMap? 66. Как изменить порядок элементов в ArrayList? 67. Как сделать копию List? 68. Каким образом можно удалить элементы из списка по условию? 69. Как проверить, является ли ArrayList отсортированным? 70. Каким образом можно добавить все элементы из одной карты в другую? 71. Как установить максимальную емкость (capacity) для ArrayList? 72. Как создать карту с заданными ключами и значениями? 73. Как узнать количество элементов в HashMap? 74. Что такое CopyOnWriteArrayList? В каких случаях он может быть полезен? 75. Как проверить, является ли коллекция упорядоченной? 76. Каким образом можно отсортировать массив объектов? 77. Как добавить элемент в TreeSet? 78. Как создать карту с заданным значением для всех ключей? 79. Как удалить все элементы из TreeMap? 80. Как получить все ключи или значения из карты? 81. Как производится сортировка в TreeSet? 82. Каким образом можно убедиться, что две коллекции содержат одинаковые элементы? 83. Как создать массив из списка? 84. Как производится сортировка в LinkedList? 85. Что такое List.subList() и как его использовать? 86. Как получить первый и последний элементы из PriorityQueue без удаления? 87. Как сделать копию Set? 88. Какой алгоритм используется для сортировки в Arrays.sort()? 89. Как узнать, содержит ли коллекция все элементы другой коллекции? 90. Каким образом можно создать множество (Set) из массива? 91. Как проверить, что две карты содержат одинаковые значения? 92. Как сделать копию TreeMap? 93. Что такое EnumMap? В каких случаях его использование может быть полезно? 94. Как добавить все элементы из массива в ArrayList? 95. Каким образом можно отсортировать список с помощью Comparable? 96. Как проверить, является ли TreeSet отсортированным? 97. Как создать массив заданного размера? 98. Как проверить, что коллекция не содержит дубликатов? 99. Как сделать копию ArrayDeque? 100. Каким образом можно преобразовать массив в строку? 101. Как вывести все элементы коллекции на экран? 102. Как добавить элементы в начало списка? 103. Каким образом можно получить первый элемент из TreeSet? 104. Что такое IdentityHashSet? В каких случаях его использование может быть полезно? 105. Как узнать, является ли определенный ключ в TreeMap первым или последним? 106. Как проверить, что две карты содержат одни и те же ключи? 107. Как добавить элементы в конец списка? 108. Как создать массив заданного типа? 109. Как сделать копию HashMap без изменения оригинальной карты? 110. Каким образом можно создать пустой список? 111. Как вывести все ключи из карты на экран? 112. Как проверить, что две коллекции содержат одни и те же элементы, но не обязательно в том же порядке? 113. Как получить последний элемент из LinkedList? 114. Как проверить, содержит ли множество (Set) все элементы другого множества? 115. Как удалить все элементы из Stack? 116. Как создать список заданного размера? 117. Как узнать, что ключ уже присутствует в HashMap? 118. Как сделать копию HashSet? 119. Каким образом можно отсортировать массив строк? 120. Что такое Collections.synchronizedList()? В каких случаях его использование может быть полезно? 121. Как производится сортировка в EnumSet? 122. Как проверить, содержат ли две коллекции одинаковые элементы в том же порядке? 123. Как узнать, был ли определенный элемент добавлен в PriorityQueue? 124. Каким образом можно отсортировать массив чисел? 125. Что такое WeakHashMap? В каких случаях его использование может быть полезно? 126. Как проверить, содержит ли Set определенный элемент? 127. Как добавить все элементы из списка в множество (Set)? 128. Как узнать, является ли TreeMap пустой? 129. Как сделать копию Vector? 130. Как получить первый элемент из LinkedList? 131. Как проверить, что две карты содержат одни и те же значения, но не обязательно для одних и тех же ключей? 132. Как удалить все элементы из PriorityQueue? 133. Как создать список заданного типа? 134. Что такое «коллекция»? 135. Назовите основные интерфейсы JCF и их реализации. 136. Расположите в виде иерархии следующие интерфейсы: List, Set, Map, SortedSet, SortedMap, Collection, Iterable, Iterator, NavigableSet, NavigableMap. 137. Почему Map — это не Collection, в то время как List и Set являются Collection? 138. В чем разница между классами java.util.Collection и java.util.Collections? 139. Что такое «fail-fast поведение»? 140. Какая разница между fail-fast и fail-safe? 141. Приведите примеры итераторов, реализующих поведение fail-safe 142. Чем различаются Enumeration и Iterator. 143. Как между собой связаны Iterable и Iterator? 144. Как между собой связаны Iterable, Iterator и «for-each»? 145. Сравните Iterator и ListIterator. 146. Что произойдет при вызове Iterator.next() без предварительного вызова Iterator.hasNext()? 147. Сколько элементов будет пропущено, если Iterator.next() будет вызван после 10-ти вызовов Iterator.hasNext()? 148. Как поведёт себя коллекция, если вызвать iterator.remove()? 149. Как поведёт себя уже инстанциированный итератор для collection, если вызвать collection.remove()? 150. Как избежать ConcurrentModificationException во время перебора коллекции? 151. Какая коллекция реализует дисциплину обслуживания FIFO? 152. Какая коллекция реализует дисциплину обслуживания FILO? 153. Чем отличается ArrayList от Vector? 154. Зачем добавили ArrayList, если уже был Vector? 155. Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй? 156. Что работает быстрее ArrayList или LinkedList? 157. Какое худшее время работы метода contains() для элемента, который есть в LinkedList? 158. Какое худшее время работы метода contains() для элемента, который есть в ArrayList? 159. Какое худшее время работы метода add() для LinkedList? 160. Какое худшее время работы метода add() для ArrayList? 161. Необходимо добавить 1 млн. элементов, какую структуру вы используете? 162. Как происходит удаление элементов из ArrayList? Как меняется в этом случае размер ArrayList? 163. Предложите эффективный алгоритм удаления нескольких рядом стоящих элементов из середины списка, реализуемого ArrayList. 164. Сколько необходимо дополнительной памяти при вызове ArrayList.add()? 165. Сколько выделяется дополнительно памяти при вызове LinkedList.add()? 166. Оцените количество памяти на хранение одного примитива типа byte в LinkedList? 167. Оцените количество памяти на хранение одного примитива типа byte в ArrayList? 168. Для ArrayList или для LinkedList операция добавления элемента в середину (list.add(list.size()/2, newElement)) медленнее? 169. В реализации класса ArrayList есть следующие поля: Object[] elementData, int size. Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length? 170. Сравните интерфейсы Queue и Deque. 171. Кто кого расширяет: Queue расширяет Deque, или Deque расширяет Queue? 172. Почему LinkedList реализует и List, и Deque? 173. LinkedList — это односвязный, двусвязный или четырехсвязный список? 174. Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index)? 175. Что позволяет сделать PriorityQueue? 176. Stack считается «устаревшим». Чем его рекомендуют заменять? Почему? 177. Зачем нужен HashMap, если есть Hashtable? 178. В чем разница между HashMap и IdentityHashMap? Для чего нужна IdentityHashMap? 179. В чем разница между HashMap и WeakHashMap? Для чего используется WeakHashMap? 180. В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences? 181. В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences? 182. LinkedHashMap - что в нем от LinkedList, а что от HashMap? 183. В чем проявляется «сортированность» SortedMap, кроме того, что toString() выводит все элементы по порядку? 184. Как устроен HashMap? 185. Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресации и на основе метода цепочек. Как реализована HashMap? Почему, по вашему мнению, была выбрана именно эта реализация? В чем плюсы и минусы каждого подхода? 186. Как работает HashMap при попытке сохранить в него два элемента по ключам с одинаковым hashCode(), но для которых equals() == false? 187. Какое начальное количество корзин в HashMap? 188. Какова оценка временной сложности операций над элементами из HashMap? Гарантирует ли HashMap указанную сложность выборки элемента? 189. Возможна ли ситуация, когда HashMap выродится в список даже с ключами имеющими разные hashCode()? 190. В каком случае может быть потерян элемент в HashMap? 191. Почему нельзя использовать byte[] в качестве ключа в HashMap? 192. Какова роль equals() и hashCode() в HashMap? 193. Каково максимальное число значений hashCode()? 194. Какое худшее время работы метода get(key) для ключа, которого нет в HashMap? 195. Какое худшее время работы метода get(key) для ключа, который есть в HashMap? 196. Сколько переходов происходит в момент вызова HashMap.get(key) по ключу, который есть в таблице? 197. Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap? 198. Как и когда происходит увеличение количества корзин в HashMap? 199. Объясните смысл параметров в конструкторе HashMap(int initialCapacity, float loadFactor). 200. Будет ли работать HashMap, если все добавляемые ключи будут иметь одинаковый hashCode()? 201. Как перебрать все ключи Map? 202. Как перебрать все значения Map? 203. Как перебрать все пары «ключ-значение» в Map? 204. В чем отличия TreeSet и HashSet? 205. Что будет, если добавлять элементы в TreeSet по возрастанию? 206. Чем LinkedHashSet отличается от HashSet? 207. Для Enum есть специальный класс java.util.EnumSet. Зачем? Чем авторов не устраивал HashSet или TreeSet? 208. Какие существуют способы перебирать элементы списка? 209. Каким образом можно получить синхронизированные объекты стандартных коллекций? 210. Как получить коллекцию только для чтения? 211. Напишите однопоточную программу, которая заставляет коллекцию выбросить ConcurrentModificationException. 212. Приведите пример, когда какая-либо коллекция выбрасывает UnsupportedOperationException. 213. Реализуйте симметрическую разность двух коллекций используя методы Collection (addAll(...), removeAll(...), retainAll(...)). 214. Как, используя LinkedHashMap, сделать кэш c «invalidation policy»? 215. Как одной строчкой скопировать элементы любой collection в массив? 216. Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х? 217. Как одной строчкой преобразовать HashSet в ArrayList? 218. Как одной строчкой преобразовать ArrayList в HashSet? 219. Сделайте HashSet из ключей HashMap. 220. Сделайте HashMap из HashSet>.