Core-2: Java Collections Framework Flashcards
Что такое коллекция?
«Коллекция» - это структура данных, или объект, который содержит набор объектов одного класса. Каждый из этих объектов в коллекции называется элементом.Классы коллекций являются дженерик-параметрами
Иерархия Коллекций: главные интерфейсы.
На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: Collection (extends Iterable) и Map. Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» соответственно.
Методы Collection
- - int size(); - void clear(); - boolean isEmpty(); - Iterator<E> iterator(); - Object[] toArray(); - T[] toArray(new T[0]) - boolean contains(Object o); - boolean containsAll(Collection<?> c); - boolean add(E e); - boolean addAll(Collection<? extends E> c); - boolean remove(Object o); - boolean removeAll(Collection<?> c); - boolean retainAll(Collection<?> c); - default boolean removeIf(Predicate<? super E> filter) - default void forEach(Consumer<? super T> action)` : from Iterable
Какие интерфейсы расширяют Collection и какие у них реализации?
Интерфейс Collection расширяют интерфейсы:
1) List (список): упорядоченная последовательность элементов, позволяющая хранить дубликаты и null.
2) Set (сет) описывает неупорядоченную коллекцию, хранящую уникальные элементы.
3) Queue (очередь) предназначена для хранения и извлечения элементов по принципу FIFO.
Какие методы добавляет List в Collection?
- get(int index) - set(int index, element) - indexOf(element) - lastIndexOf(element) - ListIterator<E> listIterator(); - List<E> subList(int from, int to); - default void replaceAll(UnaryOperator<E> operator) - static <E> List<E> of(E... elms) - static <E> List<E> copyOf(Collection<? extends E> coll) - add(int index, element) - addAll(int index, Collection c) - remove(int index)
Какие методы добавляет Set в Collection?
- static <E> Set<E> of(E... elms)</E></E>
- static <E> Set<E> copyOf(Collection<? extends E> coll)</E></E>
Какие методы добавляет Queue в Collection?
*add - throws
- boolean offer(E e) - null;
- E remove() - throws
- E poll() - null
- E element() - throws
- E peek() - null
Какие методы добавляет Deque к Queue?
Deque (двунаправленная очередь) предназначена для хранения и извлечения элементов по принципу FIFO + LIFO.
- addFirst()
- addLast()
- …element->getFirst()
Описать Механизм Работы List
init capacity = 10.
при заполнении массива создаётся новый x1.5 и туда копируется старый через System.arraycopy();
Назвать главные реализации List
- ArrayList - инкапсулирует в себе обычный массив Oblect, длина которого автоматически увеличивается при добавлении новых элементов. Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу.
- LinkedList (implements Deque)
двунаправленный связный список - состоит из узлов, каждый из которых содержит как собственно данные, так и две ссылки на следующий и предыдущий узел. - Vector — реализация динамического массива объектов, методы которой синхронизированы.
- Stack — расширяет Vector добавляя LIFO (last-in-first-out).
Какие методы ArrayList добавляет в List?
-
public void trimToSize() public void ensureCapacity(int minCap)- -
Назвать главные реализации Set
- HashSet - использует HashMap для хранения данных: в качестве ключа используется добавляемый элемент. В качестве значения объект-заглушка(константа). Порядок хранения элементов неупорядочен.
- LinkedHashSet — гарантирует, что порядок элементов при обходе коллекции будет идентичен порядку добавления элементов.
- SortedSet->NavigableSet->TreeSet — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».
Не может хранить null.
Какие доп.методы есть у TreeSet?
- public NavigableSet<E> **subSet**(E from, boolean fromIncl, E to, boolean toIncl)</E>
- public NavigableSet<E> **tailSet**(E fromElement, boolean inclusive)</E>
- public NavigableSet<E> **headSet**(E toElement, boolean inclusive)</E>
- first()
- last()
Назвать главные реализации Queue
- I AbstractQueue => PriorityQueue — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».
- I Deque => ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out).
- I Deque => LinkedList
Что такое java.util.Collections?
набор статических методов для работы с коллекциями.
Что такое «fail-fast поведение»?
fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом. Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени.
Что такое fail-fast в контексте коллекций?
В Java Collections API некоторые итераторы ведут себя как fail-fast и выбрасывают ConcurrentModificationException, если после его создания была произведена модификация коллекции, т.е. добавлен или удален элемент напрямую из коллекции, а не используя методы итератора.
Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):
при изменении коллекции счетчик модификаций изменяется;
при создании итератора ему передается текущее значение счетчика;
при каждом обращении к итератору сохраненное значение счетчика сравнивается с текущим, и, если они не совпадают, возникает исключение.
Какая разница между fail-fast и fail-safe?
В противоположность fail-fast, итераторы fail-safe не вызывают никаких исключений при изменении структуры, потому что они работают с клоном коллекции вместо оригинала.
Пример fail-safe & fail-fast
Пример fail-safe - CopyOnWriteArrayList и итератор keySet коллекции ConcurrentHashMap.
Пример fail-fast - Vector и Hashtable.
Чем различаются Enumeration и Iterator.
Iterator имеет больше методов работы с коллекциями и был специально введен в java2, вместо Enumeration(interface). Рекоммендуется юзать Iterator.
-с помощью Enumeration нельзя добавлять/удалять элементы;
-в Iterator исправлены имена методов для повышения читаемости кода (Enumeration.hasMoreElements() соответствует Iterator.hasNext(), Enumeration.nextElement() соответствует Iterator.next() и т.д);
-Enumeration присутствуют в устаревших классах, таких как Vector/Stack, тогда как Iterator есть во всех современных коллекциях.
Как между собой связаны Iterable и Iterator?
Интерфейс Iterable имеет только один метод - iterator(), который возвращает Iterator.
Как между собой связаны Iterable, Iterator и «foreach»?
Классы, реализующие интерфейс Iterable, могут применяться в конструкции foreach, которая использует Iterator.
Сравните Iterator и ListIterator.
- ListIterator расширяет интерфейс Iterator
- ListIterator может быть использован только для перебора элементов коллекции List;
- Iterator позволяет перебирать элементы только в одном направлении, при помощи метода next(). Тогда как ListIterator позволяет перебирать список в обоих направлениях, при помощи методов next() и previous();
- ListIterator не указывает на конкретный элемент: его текущая позиция располагается между элементами, которые возвращают методы previous() и next().
- При помощи ListIterator вы можете модифицировать список, добавляя/удаляя элементы с помощью методов add(), set() и remove(). Iterator не поддерживает данного функционала.
Что произойдет при вызове Iterator.next() без предварительного вызова Iterator.hasNext()?
Если итератор указывает на последний элемент коллекции, то возникнет исключение NoSuchElementException, иначе будет возвращен следующий элемент.
Как поведёт себя коллекция, если вызвать iterator.remove()?
Если вызову iterator.remove() предшествовал вызов iterator.next(), то iterator.remove() удалит элемент коллекции, на который указывает итератор, в противном случае будет выброшено IllegalStateException().
Как избежать ConcurrentModificationException во время перебора коллекции? (3)
- Использовать ConcurrentHashMap и CopyOnWriteArrayList.
- Преобразовать список в массив и перебирать массив.
- Блокировать изменения списка на время перебора с помощью блока synchronized.
Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй?
Чем отличается 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 операция добавления элемента в середину (list.add(list.size()/2, newElement)) медленнее?
Для ArrayList:
проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив (O(N));
копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо (O(N));
вставка элемента (O(1)).
Для LinkedList:
поиск позиции вставки (O(N));
вставка элемента (O(1)).
В худшем случае вставка в середину списка эффективнее для LinkedList. В остальных - скорее всего, для ArrayList, поскольку копирование элементов осуществляется за счет вызова быстрого системного метода System.arraycopy().
Почему LinkedList реализует и List, и Deque?
LinkedList позволяет добавлять элементы в начало и конец списка за константное время, что хорошо согласуется с поведением интерфейса Deque.
Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index)?
Для этого в LinkedList есть обратный итератор, который можно получить вызва метод descendingIterator() - унаследовано от Deque.
Основные Методы Map
- int size();
- void clear();
- boolean isEmpty();
- boolean containsKey(Object key);
- boolean containsValue(Object value);
- V get(Object key);
- default V getOrDefault(Object key, V defaultValue)
- V put(K key, V value) : returns previous value
- default V putIfAbsent(K key, V value)
- V remove(Object key) : returns previous value
- void putAll(Map<? extends K, ? extends V> m);
- Set<K> keySet();
- Collection<V> values();
- Set<Map.Entry<K, V>> entrySet();
- K getKey();
- V getValue();
- V setValue(V value);
- public static <K, V> Comparator<Map.Entry<K, V>>
comparingByKey(Comparator<? super K> cmp)
comparingByValue(Comparator<? super K> cmp)
- default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction)
- default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) NPE if no key is present. returns new value
- default V computeIfPresent(...) :like compute(), but doesn't throw NPE.
- default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) :
returns new value or null if no key in the map.
- `default void forEach(BiConsumer<? super K, ? super V> action)`
- default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)Как устроен HashMap?
HashMap - это массив, элементами которого являются структуры SinglyList, содержащие ноды(hash+key+value+next).
= new HashMap<>(16, 0.75f); => создается массив с 16 бакетами(16 - init capacity, 0.75 - load factor).
map.put(K,V) => K.hashCode() => вычисляем hashvalue(индекс в корзине) на основе hash&capacity=>
сверяем hash c имеющимися =>
если разные => кладем в конец листа
если совпадают =>
equals() => заменяем
!equals() => сравниваем со след…
по достижении 8 элементов, бакет превращается в самобалансирующееся дерево ( > направо, < налево).
Зачем нужен HashMap, если есть Hashtable?
Методы класса Hashtable синхронизированы, что приводит к снижению производительности, а HashMap - нет;
HashTable не может содержать элементы null, тогда как HashMap может содержать один ключ null и любое количество значений null;
Iterator у HashMap, в отличие от Enumeration у HashTable, работает по принципу «fail-fast» (выдает исключение при любой несогласованности данных).
Hashtable это устаревший класс и его использование не рекомендовано.
В чем разница между HashMap и IdentityHashMap? Для чего нужна IdentityHashMap?
IdentityHashMap - это структура данных, так же реализующая интерфейс Map и использующая при сравнении ключей (значений) сравнение ссылок, а не вызов метода equals(). Другими словами, в IdentityHashMap два ключа k1 и k2 будут считаться равными, если они указывают на один объект, т.е. выполняется условие k1 == k2.
Одним из основных требований к использованию HashMap является неизменяемость ключа, а, т.к. IdentityHashMap не использует методы equals() и hashCode(), то это правило на него не распространяется.
Что такое TreeMap?
Map => SortedMap => NavigableMap = TreeMap. В основе лежит красно-черное дерево, а элементы хранятся в порядке возрастания ключа.
Класс ключа должен имплементировать Comparable() или задать Comparator() в анонимном классе при создании TreeMap.
Все поиски по ключу идут при помощи CompareTo(): нет необходимости переопределять equals() & hashcode().
Как устроено красно-черное дерево?
- узел красный или черный
- корень и листья(NIL) черные
- если узел красный - его дети черные
- все пути от узла к листьям содержат равное количество черных узлов
Сложность: O(log n)
Стратегия:
вставить узел(Z) и сделать красным
a) Z - root
- make it black
b) Z’s uncle = red
- recolor uncle, parent, grandP
c) Z’s uncle = black (triangle)
- rotate Z with parent
d) Z’s uncle = black (line)
- left rotate parent & greatP
- ротация и перекрашивание
Что такое LinkedHashMap?
Наследник HashMap, хранящий информацию о порядке добавления и использования элементов.
= new LinkedHashMap<>(16, 0.75f, accessOrder (boolean));
=> false: хранятся как добавлены.
=> true: последний использованный попадает в конец.
Что такое WeakHashMap?
Пара «ключ-значение» будет удалена из WeakHashMap, если на объект-ключ более не имеется сильных ссылок.
Почему нельзя использовать byte[] в качестве ключа в HashMap?
Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива).
Сколько переходов происходит в момент вызова HashMap.get(key) по ключу, который есть в таблице?
- ключ равен null: 1 - выполняется единственный метод getForNullKey().
- любой ключ отличный от null: 4 - вычисление хэш-кода ключа; определение номера корзины;
поиск значения;
возврат значения.
Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap?
Один новый объект статического вложенного класса Entry<K,V>.
Как перебрать все ключи Map?
Использовать метод keySet(), который возвращает множество Set<K> ключей.
Как перебрать все значения Map?
Использовать метод values(), который возвращает коллекцию Collection<V> значений.
Как перебрать все пары «ключ-значение» в Map?
Использовать метод entrySet(), который возвращает множество Set<Map.Entry<K, V> пар «ключ-значение».
Для Enum есть специальный класс java.util.EnumSet. Зачем? Чем авторов не устраивал HashSet или TreeSet?
EnumSet - это реализация интерфейса Set для использования с перечислениями (Enum). В структуре данных хранятся объекты только одного типа Enum, указываемого при создании. Для хранения значений EnumSet использует массив битов (bit vector), - это позволяет получить высокую компактность и эффективность.
Все оснвные операции выполняются за O(n)/.
Как получить коллекцию только для чтения?
Collections.unmodifiableList(list); Collections.unmodifiableSet(set); Collections.unmodifiableMap(map).
Напишите однопоточную программу, которая заставляет коллекцию выбросить ConcurrentModificationException.
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
for (Integer integer : list) {
list.remove(1);
}Приведите пример, когда какая-либо коллекция выбрасывает UnsupportedOperationException.
public static void main(String[] args) {
List<Integer> list = Collections.emptyList();
list.add(0);
}Реализуйте симметрическую разность двух коллекций используя методы Collection (addAll(…), removeAll(…), retainAll(…)).
Симметрическая разность двух коллекций - это множество элементов, одновременно не принадлежащих обоим исходным коллекциям.
<T> Collection<T> symmetricDifference(Collection<T> a, Collection<T> b) {
// Объединяем коллекции.
Collection<T> result = new ArrayList<>(a);
result.addAll(b);
// Получаем пересечение коллекций.
Collection<T> intersection = new ArrayList<>(a);
intersection.retainAll(b);
// Удаляем элементы, расположенные в обоих коллекциях.
result.removeAll(intersection);
return result;
}
