Java Collections Flashcards
Что такое «коллекция»?
«Коллекция» - это структура данных, набор каких-либо объектов. Данными (объектами в наборе) могут быть числа, строки, объекты пользовательских классов и т.п.
Назовите основные интерфейсы JCF и их реализации.
На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: Collection и Map. Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» соответственно.
Интерфейс Collection расширяют интерфейсы:
* List (список) представляет собой коллекцию, в которой допустимы дублирующие значения. Реализации:
– ArrayList - инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов. Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу.
– LinkedList (двунаправленный связный список) - состоит из узлов, каждый из которых содержит как собственно данные, так и две ссылки на следующий и предыдущий узел.
– Vector — реализация динамического массива объектов, методы которой синхронизированы.
– Stack — реализация стека LIFO (last-in-first-out).
* Set (сет) описывает неупорядоченную коллекцию, не содержащую повторяющихся элементов. Реализации:
– HashSet - использует HashMap для хранения данных. В качестве ключа и значения используется добавляемый элемент. Из-за особенностей реализации порядок элементов не гарантируется при добавлении.
– LinkedHashSet — гарантирует, что порядок элементов при обходе коллекции будет идентичен порядку добавления элементов.
– TreeSet — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».
* Queue (очередь) предназначена для хранения элементов с предопределённым способом вставки и извлечения FIFO (first-in-first-out):
– PriorityQueue — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».
– ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out).
Интерфейс Map реализован классами:
* Hashtable — хэш-таблица, методы которой синхронизированы. Не позволяет использовать null в качестве значения или ключа и не является упорядоченной.
* HashMap — хэш-таблица. Позволяет использовать null в качестве значения или ключа и не является упорядоченной.
* LinkedHashMap — упорядоченная реализация хэш-таблицы.
* TreeMap — реализация, основанная на красно-чёрных деревьях. Является упорядоченной и предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».
* WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references для ключей (сборщик мусора автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элемента нет жёстких ссылок).
Расположите в виде иерархии следующие интерфейсы: List, Set, Map, SortedSet, SortedMap, Collection, Iterable, Iterator, NavigableSet, NavigableMap.
—Iterable<br></br>—--Collection<br></br>———List<br></br>———Set<br></br>———–SortedSet<br></br>————–NavigableSet<br></br><br></br>
—Map<br></br>——-SortedMap<br></br>————NavigableMap<br></br><br></br>
—Iterator
Почему Map — это не Collection, в то время как List и Set являются Collection?
Collection представляет собой совокупность некоторых элементов. Map - это совокупность пар «ключ-значение».
В чем разница между классами java.util.Collection и java.util.Collections?
java.util.Collections - набор статических методов для работы с коллекциями.
java.util.Collection - один из основных интерфейсов Java Collections Framework.
Что такое «fail-fast поведение»?
fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом. Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени.
В Java Collections API некоторые итераторы ведут себя как fail-fast и выбрасывают ConcurrentModificationException, если после его создания была произведена модификация коллекции, т.е. добавлен или удален элемент напрямую из коллекции, а не используя методы итератора.
Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):
* при изменении коллекции счетчик модификаций так же изменяется;
* при создании итератора ему передается текущее значение счетчика;
* при каждом обращении к итератору сохраненное значение счетчика сравнивается с текущим, и, если они не совпадают, возникает исключение.
Какая разница между fail-fast и fail-safe?
Хотя оба интерфейса и предназначены для обхода коллекций между ними имеются существенные различия:
* с помощью Enumeration нельзя добавлять/удалять элементы;
* в Iterator исправлены имена методов для повышения читаемости кода (Enumeration.hasMoreElements() соответствует Iterator.hasNext(), Enumeration.nextElement() соответствует Iterator.next() и т.д);
* Enumeration присутствуют в устаревших классах, таких как Vector/Stack, тогда как Iterator есть во всех современных классах-коллекциях.
Как между собой связаны Iterable и Iterator?
Интерфейс Iterable имеет только один метод - iterator(), который возвращает Iterator.
Как между собой связаны Iterable, Iterator и «for-each»?
Классы, реализующие интерфейс Iterable, могут применяться в конструкции for-each, которая использует Iterator.
Сравните Iterator и ListIterator.
- ListIterator расширяет интерфейс Iterator
- ListIterator может быть использован только для перебора элементов коллекции List;
- Iterator позволяет перебирать элементы только в одном направлении, при помощи метода next(). Тогда как ListIterator позволяет перебирать список в обоих направлениях, при помощи методов next() и previous();
- ListIterator не указывает на конкретный элемент: его текущая позиция располагается между элементами, которые возвращают методы previous() и next().
- При помощи ListIterator вы можете модифицировать список, добавляя/удаляя элементы с помощью методов add() и remove(). Iterator не поддерживает данного функционала.
Что произойдет при вызове Iterator.next() без предварительного вызова Iterator.hasNext()?
Если итератор указывает на последний элемент коллекции, то возникнет исключение NoSuchElementException, иначе будет возвращен следующий элемент.
Сколько элементов будет пропущено, если Iterator.next() будет вызван после 10-ти вызовов Iterator.hasNext()?
Нисколько - hasNext() осуществляет только проверку наличия следующего элемента.
Как поведёт себя коллекция, если вызвать iterator.remove()?
Если вызову iterator.remove() предшествовал вызов iterator.next(), то iterator.remove() удалит элемент коллекции, на который указывает итератор, в противном случае будет выброшено IllegalStateException().
Как поведёт себя уже инстанциированный итератор для collection, если вызвать collection.remove()?
При следующем вызове методов итератора будет выброшено ConcurrentModificationException.
Как избежать ConcurrentModificationException во время перебора коллекции?
- Попробовать подобрать или реализовать самостоятельно другой итератор, работающий по принципу fail-safe.
- Использовать ConcurrentHashMap и CopyOnWriteArrayList.
- Преобразовать список в массив и перебирать массив.
- Блокировать изменения списка на время перебора с помощью блока synchronized.
Отрицательная сторона последних двух вариантов - ухудшение производительности.
Какая коллекция реализует дисциплину обслуживания FIFO?
FIFO, First-In-First-Out («первым пришел-первым ушел») - по этому принципу построена коллекция Queue.
Какая коллекция реализует дисциплину обслуживания FILO?
FILO, First-In-Last-Out («первым пришел, последним ушел») - по этому принципу построена коллекция Stack.
Чем отличается ArrayList от Vector?
- Методы класса Vector синхронизированы, а ArrayList - нет;
- По умолчанию, Vector удваивает свой размер, когда заканчивается выделенная под элементы память. ArrayList же увеличивает свой размер только на половину.
Vector это устаревший класс и его использование не рекомендовано.
Чем отличается ArrayList от LinkedList?
В каких случаях лучше использовать первый, а в каких второй?
ArrayList это список, реализованный на основе массива, а LinkedList — это классический двусвязный список, основанный на объектах с ссылками между ними.
ArrayList:
* доступ к произвольному элементу по индексу за константное время O(1);
* доступ к элементам по значению за линейное время O(N);
* вставка в конец в среднем производится за константное время O(1);
* удаление произвольного элемента из списка занимает значительное время т.к. при этом все элементы, находящиеся «правее» смещаются на одну ячейку влево (реальный размер массива (capacity) не изменяется);
* вставка элемента в произвольное место списка занимает значительное время т.к. при этом все элементы, находящиеся «правее» смещаются на одну ячейку вправо;
* минимум накладных расходов при хранении.
LinkedList:
* на получение элемента по индексу или значению потребуется линейное время O(N);
* но доступ к первому и последнему элементу списка всегда осуществляется за константное время O(1) — ссылки постоянно хранятся на первый и последний элемент;
* на добавление и удаление в начало или конец списка потребуется константное O(1);
* вставка или удаление в/из произвольного место константное O(1);
* но поиск позиции вставки и удаления за линейное время O(N);
* требует больше памяти для хранения такого же количества элементов, потому что кроме самого элемента хранятся еще указатели на следующий и предыдущий элементы списка.
В целом, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти, и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список.
Что работает быстрее ArrayList или LinkedList?
Смотря какие действия будут выполняться над структурой.
Есть здесь такой вопрос об отличиях ArrayList и LinkedList
Какое худшее время работы метода contains() для элемента, который есть в LinkedList и ArrayList?
O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.
Какое худшее время работы метода add() для LinkedList?
O(N). Добавление в начало/конец списка осуществляется за время O(1).
Какое худшее время работы метода add() для ArrayList?
O(N). Вставка элемента в конец списка осуществляется за время O(1), но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый.
Необходимо добавить 1 млн. элементов, какую структуру вы используете?
Однозначный ответ можно дать только исходя из информации о том в какую часть списка происходит добавление элементов, что потом будет происходить с элементами списка, существуют ли какие-то ограничения по памяти или скорости выполнения.
Как происходит удаление элементов из ArrayList? Как меняется в этом случае размер ArrayList?
При удалении произвольного элемента из списка, все элементы, находящиеся «правее» смещаются на одну ячейку влево и реальный размер массива (его емкость, capacity) не изменяется никак. Механизм автоматического «расширения» массива существует, а вот автоматического «сжатия» нет, можно только явно выполнить «сжатие» командой trimToSize().
Предложите эффективный алгоритм удаления нескольких рядом стоящих элементов из середины списка, реализуемого ArrayList.
Допустим нужно удалить n элементов с позиции m в списке. Вместо выполнения удаления одного элемента n раз (каждый раз смещая на 1 позицию элементы, стоящие «правее» в списке), нужно выполнить смещение всех элементов, стоящих «правее» n + m позиции на n элементов «левее» к началу списка. Таким образом, вместо выполнения n итераций перемещения элементов списка, все выполняется за 1 проход. Но если говорить об общей эффективности - то самый быстрый способ будет с использованием System.arraycopy(), и получить к нему доступ можно через метод - subList(int fromIndex, int toIndex)
Пример:
~~~
import java.io.*;
import java.util.ArrayList;
public class Main {
//позиция, с которой удаляем
private static int m = 0;
//количество удаляемых элементов
private static int n = 0;
//количество элементов в списке
private static final int size = 1000000;
//основной список (для удаления вызовом remove() и его копия для удаления путём перезаписи)
private static ArrayList<Integer> initList, copyList;</Integer>
public static void main(String[] args){
initList = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
initList.add(i);
}
System.out.println("Список из 1.000.000 элементов заполнен");
copyList = new ArrayList<>(initList);
System.out.println("Создана копия списка\n");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try{
System.out.print("С какой позиции удаляем? > ");
m = Integer.parseInt(br.readLine());
System.out.print("Сколько удаляем? > ");
n = Integer.parseInt(br.readLine());
} catch(IOException e){
System.err.println(e.toString());
}
System.out.println("\nВыполняем удаление вызовом remove()...");
long start = System.currentTimeMillis();
for (int i = m - 1; i < m + n - 1; i++) {
initList.remove(i);
}
long finish = System.currentTimeMillis() - start;
System.out.println("Время удаления с помощью вызова remove(): " + finish);
System.out.println("Размер исходного списка после удаления: " + initList.size());
System.out.println("\nВыполняем удаление путем перезаписи...\n");
start = System.currentTimeMillis();
removeEfficiently();
finish = System.currentTimeMillis() - start;
System.out.println("Время удаления путём смещения: " + finish);
System.out.println("Размер копии списка:" + copyList.size());
System.out.println("\nВыполняем удаление через SubList...\n");
start = System.currentTimeMillis();
initList.subList(m - 1, m + n).clear();
finish = System.currentTimeMillis() - start;
System.out.println("Время удаления через саблист: " + finish);
System.out.println("Размер копии списка:" + copyList.size());
}
private static void removeEfficiently(){
/* если необходимо удалить все элементы, начиная с указанного,
* то удаляем элементы с конца до m
*/
if (m + n >= size){
int i = size - 1;
while (i != m - 1){
copyList.remove(i);
i--;
}
} else{
//переменная k необходима для отсчёта сдвига начиная от места вставка m
for (int i = m + n, k = 0; i < size; i++, k++) {
copyList.set(m + k, copyList.get(i));
}
/* удаляем ненужные элементы в конце списка
* удаляется всегда последний элемент, так как время этого действия
* фиксировано и не зависит от размера списка
*/
int i = size - 1;
while (i != size - n - 1){
copyList.remove(i);
i--;
}
//сокращаем длину списка путём удаления пустых ячеек
copyList.trimToSize();
}
} } ~~~
Результат выполнения:
run:
Список из 1.000.000 элементов заполнен
Создана копия списка
С какой позиции удаляем? > 600000
Сколько удаляем? > 20000
Выполняем удаление вызовом remove()…
Время удаления с помощью вызова remove(): 928
Размер исходного списка после удаления: 980000
Выполняем удаление путем перезаписи…
Время удаления путём смещения: 17
Размер копии списка:980000
Выполняем удаление через SubList…
Время удаления через саблист: 1
Размер копии списка:980000
СБОРКА УСПЕШНО ЗАВЕРШЕНА (общее время: 33 секунды)
Сколько необходимо дополнительной памяти при вызове ArrayList.add()?
Если в массиве достаточно места для размещения нового элемента, то дополнительной памяти не требуется. Иначе происходит создание нового массива размером в 1,5 раза превышающим существующий (это верно для JDK выше 1.7, в более ранних версиях размер увеличения иной).
Сколько выделяется дополнительно памяти при вызове LinkedList.add()?
Создается один новый экземпляр вложенного класса Node.
Оцените количество памяти на хранение одного примитива типа byte в LinkedList?
Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные.
~~~
private static class Node<E> {
E item;
Node<E> next;
Node<E> 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 байт.</E></E></E>
Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны: 8 + 8 + 8 + 16 = 40байт и 24 байта. Итого 64 байта.
Оцените количество памяти на хранение одного примитива типа byte в ArrayList?
ArrayList основан на массиве, для примитивных типов данных осуществляется автоматическая упаковка значения, поэтому 16 байт тратится на хранение упакованного объекта и 4 байта (8 для x64) - на хранение ссылки на этот объект в самой структуре данных. Таким образом, в x32 JVM 4 байта используются на хранение одного элемента и 16 байт - на хранение упакованного объекта типа Byte. Для x64 - 8 байт и 24 байта соответственно.
Для ArrayList или для LinkedList операция добавления элемента в середину (list.add(list.size()/2, newElement)) медленнее?
Для ArrayList:
* проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив (O(N));
* копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо (O(N));
* вставка элемента (O(1)).
Для LinkedList:
* поиск позиции вставки (O(N));
* вставка элемента (O(1)).
В худшем случае вставка в середину списка эффективнее для LinkedList. В остальных - скорее всего, для ArrayList, поскольку копирование элементов осуществляется за счет вызова быстрого системного метода System.arraycopy().
В реализации класса ArrayList есть следующие поля: Object[] elementData, int size. Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length?
Размер массива elementData представляет собой вместимость (capacity) ArrayList, которая всегда больше переменной size - реального количества хранимых элементов. При необходимости вместимость автоматически возрастает.
