Collections. Lite. Flashcards
1
Q
Что такое “коллекция”.
A
Коллекция — это структура данных для хранения ссылочных типов данных.
Java Collections Framework – это иерархия интерфейсов и их реализаций.
2
Q
Перечислите основные методы из интерфейса java.util.Collection.
A
Основные:
- add()
- clear()
- contains()
- isEmpty()
- iterator()
- remove()
- size()
- toArray()
Остальные:
- addAll()
- containsAll()
- removeAll()
- retainAll()
- equals()
- hashCode()
2
Q
Назовите преимущества использования коллекций по сравнению с массивами.
A
- Динамическое изменение размера.
- Готовые методы для работы с данными и сортировки.
- Возможность использовать разные типы коллекций (List, Set, Queue, Map).
- Реализуют различные алгоритмы и структуры данных.
- Возможность хранить данные без дублей или в упорядоченном виде.
3
Q
Какие данные могут хранить коллекции?
A
- Любые ссылочные типы данных.
- Для примитивных типов используются классы-обёртки.
4
Q
Какие есть типы коллекций? Как они характеризуются? Расскажите про иерархию коллекций List, Set, Map.
A
-
List: Упорядоченный список по порядку вставки элементов, допускаются дубликаты, доступ по индексу.
ArrayList - динамический массив, упорядочен, быстрый доступ по индексу.
LinkedList – двусвязный список, упорядочен, медленный доступ по индексу. -
Set: Множество - неупорядоченный набор уникальных элементов, нет доступа по индексу.
HashSet — неупорядоченная, основана на хеш-таблице, быстрая вставка, удаление, проверка наличия.
LinkedHashSet — упорядоченная по порядку вставки элементов, основана на хеш-таблице и связанном списке.
TreeSet — упорядоченная по Natural Order или Comparator, основана красно-чёрном дереве. -
Queue: Очередь - упорядочена, для хранения по принципу FIFO или приоритет.
LinkedList – очередь с поддержкой FIFO и LIFO.
PriorityQueue – упорядочена по приоритету элементов через Comparator.
ArrayDeque – реализация Deque, с поддержкой LIFO и FIFO. Более производительна, чем LinkedList. -
Map: Словарь - хранит пары “ключ-значение”, каждый ключ уникален, нет итератора.
HashMap – неупорядоченная, основана на хеш-таблице, быстрый доступ по ключам.
LinkedHashMap – упорядоченная по порядку вставки элементов, основана на хеш-таблице и связанном списке.
TreeMap – упорядоченная по ключам по Natural Order или Comparator, основана на сбалансированном дереве, реализует NavigableMap.
5
Q
Назовите основные классы, которые имплементируют/реализуют интерфейсы List, Set, Map.
A
List:
- ArrayList
- LinkedList
Set:
- HashSet
- LinkedHashSet
- TreeSet
Map:
- HashMap
- LinkedHashMap
- TreeMap
6
Q
В чём отличие ArrayList от LinkedList?
A
- ArrayList: динамический массив, быстрый доступ по индексу О(1), но медленное добавление и удаление элементов в середину или в начало списка т.к. необходимо каждый раз сдвигать элементы.
- LinkedList: двусвязный список, быстрое добавление и удаление элементов в любом месте списка, но медленный доступ по индексу т.к. необходимо каждый раз перебирать все элементы. Используют, если элементы чаще добавляются, чем читаются.
7
Q
В чём отличие HashSet от TreeSet?
A
- HashSet: основана на хеш-таблице, неупорядочена (порядок зависит от хеш-кода), операции вставки, удаления и поиска выполняются в среднем за константное время O(1). Производительность может снижаться из-за коллизий. Хранит значения как ключи в HashMap.
- TreeSet: основана на красно-черном дереве, хранит элементы в отсортированном виде по Natural Order или Comparator, медленнее в плане операций добавления, удаления и поиска O(log n).
8
Q
В чём отличие Set от Map?
A
- Set: не упорядочена, хранит только уникальные элементы и не поддерживает доступ по индексу.
- Map: хранит пары “ключ-значение”, где ключи уникальны, но значения могут повторяться, и доступ осуществляется по ключу. Нет итератора.
9
Q
Как задается порядок следования объектов в коллекции, как отсортировать коллекцию?
A
Для сортировки коллекций используются два основных подхода:
- Естественный порядок (Natural order): Класс должен реализовывать интерфейс Comparable и переопределить метод compareTo(). Сортировка выполняется с помощью: Collections.sort(list) или list.sort(null); или list.sort(Comparator.naturalOrder());.
- Сортировка по пользовательскому порядку: Если нужно отсортировать коллекцию в нестандартном порядке, необходимо создать свой компаратор, реализующий интерфейс Comparator, с методом compare(). Сортировка выполняется с помощью: Collections.sort(list, comparator) или list.sort(comparator);.
Важно! Для сортировки коллекций Set или Map сначала необходимо их преобразовать в List, а затем применить сортировку.
10
Q
Чем отличается Comparable от Comparator?
A
- Comparable - используется для задания естественного порядка объектов, реализуя метод compareTo() внутри класса, поэтому может быть реализован только один раз для одного класса.
- Comparator - позволяет задать порядок вне класса, реализуя метод compare() в отдельном классе, поэтому можно создавать сколько угодно разных компараторов для одного класса.
11
Q
Что такое сортировка по принципу Natural Order?
A
Natural Order — это естественный порядок сортировки элементов, основанный на их типе.
Например, для чисел — по возрастанию, для строк — лексикографически.
12
Q
Что такое equals и hashcode?
A
- equals() - метод для проверки двух объектов на равенство.
- hashCode() - метод для вычисления хэш-кода объекта. Необходим для работы с хэш-структурами, такими как HashMap, HashSet.
Запомнить правило:
- Если два объекта равны по equals(), их hashСode() должен быть одинаковым.
- Если у двух объектов одинаковый hashСode() , то они не обязательно равны по equals(), т.к. возможны коллизии, когда разные объекты имеют одинаковый хеш-код.
13
Q
Какие есть способы перебора всех элементов List?
A
- Циклы: for, for-each, while.
- Итераторы: Iterator, ListIterator.
- Потоки Stream API.
- Метод forEach() (Java 8+)
14
Q
Расскажите о методах Map.
A
- V put(K key, V value) - добавляет пару ключ-значение или обновляет существующее.
- V get(K key) - возвращает значение по ключу.
- keySet() - возвращает коллекцию Set, состоящую из ключей.
- entrySet() - возвращает коллекцию Set, состоящую из объектов Map.Entry, которые содержат ключ и значение.
- values() - возвращает коллекцию Collection, состоящую из значений.
- getKey() - относится к элементу Map.Entry, возвращает ключ.
- getValue() - относится к элементу Map.Entry, возвращает значение.
- remove(key) - удаляет пару по ключу.
15
Q
Расскажите, какие классы реализовывают интерфейс Map?
A
- HashMap – неупорядоченная, основана на хеш-таблице.
- LinkedHashMap – упорядоченная по порядку вставки элементов, основана на хеш-таблице и связанном списке.
- TreeMap – упорядоченная по ключам по Natural Order или Comparator, основана на сбалансированном дереве.
- ConcurentHashMap - неупорядоченная, потокобезопасная, основана на хеш-таблице.
16
Q
Расскажите о методах map.keySet и map.entrySet? Что такое Entry?
A
- keySet() - возвращает коллекция Set всех ключей карты.
- entrySet() - возвращает коллекцию Set всех пар “ключ-значение” карты в виде объектов Map.Entry.
- Map.Entry<K, V> - вложенный интерфейс для пар “ключ-значение”.
17
Q
Что будет если вызвать метод map.put несколько раз с одинаковым ключом?
A
Каждый новый вызов заменит старое значение на новое, связанное с данным ключом.
18
Q
Как реализован цикл foreach?
A
Цикл foreach используется только для классов, реализующих интерфейс Iterable. Вызывает метод iterator() для получения итератора и с помощью него перебирает элементы коллекции.
19
Q
В чем разница между Iterator и Iterable?
A
Интерфейс Iterable — предоставляет итератор для элементов коллекции:
- Метод iterator() — возвращает итератор.
Интерфейс Iterator - используется для перебора элементов коллекции.
- boolean hasNext() - проверяет наличие следующего элемента.
- E next() - получает следующий элемент.
- void remove() - удаляет текущий элемент (опционально).
20
Q
Как происходит удаление элементов из ArrayList?
A
Все элементы сдвигаются влево на 1 элемент (System.arraycopy()), а значение size уменьшается на 1.
- remove(int index); - удаляет и возвращает элемент по индексу.
- remove(Object o); - удаляет первое вхождение объекта.
- removeIf(Predicate<? super E> filter); - удаляет по условию заданному предикатом.
- iterator.remove(); - удаляет текущий элемент итератора.
- removeRange(int fromIndex, int toIndex); - удаляет элементы в диапазоне индексов.
- clear(); - удаляет все элементы.
21
Q
Как происходит удаление элементов из LinkedList?
A
Удаление происходит через изменение ссылок (previous и next) на соседние элементы.
Удаление элементов на позициях в начале или в конце происходит быстрее, чем в ArrayList, поскольку нет необходимости сдвигать элементы.
Однако для удаления элементов в середине списка время выполнения может увеличиваться, так как нужно пройти по цепочке узлов до нужной позиции.
-
remove(int index); - удаляет и возвращает элемент по индексу.
remove(Object o); - удаляет первое вхождение объекта. - removeIf(Predicate<? super E> filter); - удаляет по условию заданному предикатом.
- iterator.remove(); - удаляет текущий элемент итератора.
- subList(fromIndex, toIndex).clear(); - удаляет элементы в диапазоне индексов.
- clear(); - удаляет все элементы.
- pop(); / poll(); / pollFirst(); / removeFirst(); - удаляют и возвращают первый элемент списка, либо null, если список пуст.
- pollLast(); / removeLast(); - удаляет и возвращает последний элемент списка, либо null.
- removeFirstOccurrence(Object o); - удаляет первое вхождение указанного элемента в списке. Если элемент не найден, ничего не происходит.
- removeLastOccurrence(Object o); - удаляет последнее вхождение указанного элемента в списке. Если элемент не найден, ничего не происходит.
22
Q
Что такое автоупаковка и распаковка? Зачем они нужны?
A
- Автоупаковка/распаковка - это автоматическое преобразования примитивных типов в соответствующие объекты классов-оберток, и наоборот, в процессе компиляции или выполнения программы.
- Примитивные типы данных не являются объектами, и поэтому не могут использовать методы и свойства объектов. Однако в некоторых случаях требуется использовать объекты, например, когда нужно сохранить значение примитивного типа в коллекцию или передать его в метод, который принимает только объекты.
23
Q
В каком случае при работе с упакованными значениями может возникнуть проблема с производительностью?
A
- Арифметические операции над значениями объектов классов-обёрток в цикле (т.к. требуется каждый раз распаковать, посчитать, запаковать).
- Частое упаковывание и распаковывание может замедлить работу программы.
24
Опишите недостатки и преимущества в использовании примитивных типов и классов-оберток.
* **Примитивные типы**: занимают меньше памяти, не требуют затрат на автораспаковку/упаковку, но но не поддерживают работу с коллекциями напрямую.
* **Классы-обертки**: занимают больше памяти, но их можно использовать в коллекциях.
25
Что такое очередь? Расскажите принцип работы и для чего она используется.
* **Очередь (Queue)** - это структура данных, которая сохраняет порядок вставки элементов. Элементы добавляются в конец очереди, а извлекаются из начала.
* Реализована с помощью интерфейсов **Queue** (односторонняя очередь, **FIFO**) и **Deque** (двухсторонняя очередь, поддерживающая **FIFO** и **LIFO** поведение).
26
Расскажите про интерфейсы Queue, Deque и их иерархию.
* **Queue** - односторонняя очередь, наследуется от интерфейса **Collection**, работает по принципу **FIFO**. Элементы добавляются в конец очереди и удаляются из начала.
Реализации: **LinkedList**, **PriorityQueue**.
* **Deque** - двухсторонняя очередь, наследуется от **Queue**, поддерживает как **FIFO** (очередь), так и **LIFO** (стек) поведение. Элементы могут добавляться и удаляться с обоих концов.
Реализации: **ArrayDeque**, **LinkedList**.
27
В чем отличие метода poll() от remove()?
Оба метода удаляют и возвращают первый элемент очереди.
* Метод **remove**(); бросает исключение **NoSuchElementException**, если очередь пуста.
* Метод **poll**(); возвращает **null**, если очередь пуста.
28
В чем отличие метода element() от peek()?
Оба метода возвращают первый элемент очереди без удаления.
* Метод **element**(); бросает исключение **NoSuchElementException**, если очередь пуста.
* Метод **peek**(); возвращает **null**, если очередь пуста.
29
В чем отличие метода element() от poll()?
* Метод **element**(); возвращает первый элемент очереди без удаления. Бросает исключение **NoSuchElementException**, если очередь пуста.
* Метод **poll**(); удаляет и возвращает первый элемент очереди. Возвращает **null**, если очередь пуста.
30
Перечислите наиболее часто используемые реализации интерфейса Queue.
* LinkedList;
* PriorityQueue;
* ArrayBlockingQueue;
31
Что такое ограниченные и неограниченные очереди?
* **Ограниченные очереди** имеют фиксированный размер, который задаётся при создании очереди. После достижения этого размера, дальнейшие попытки добавления элементов могут блокироваться или приводить к исключениям, в зависимости от реализации. **ArrayBlockingQueue** реализует интерфейс **BlockingQueue** и использует фиксированный массив.
* **Неограниченные очереди** могут динамически расширяться по мере добавления элементов, их размер не ограничен.
32
Что такой односторонние и двусторонние очереди?
* **Односторонняя очередь** (**Queue**): элементы добавляются в один конец и удаляются из другого. Реализует принцип **FIFO**.
* **Двусторонняя очередь** (**Deque**): Элементы могут быть добавлены и удалены с обеих сторон. Поддерживает как **FIFO**, так и **LIFO** поведение.
33
В чём отличие Deque от Queue?
* **Queue**: Реализует принцип **FIFO** и поддерживает операции только на одном конце очереди (добавление в конец и удаление из начала).
* **Deque**: Реализует как **FIFO**, так и **LIFO** (стек) и поддерживает операции на обоих концах очереди (добавление и удаление как с начала, так и с конца).
34
В чём отличие методов removeLast() и pollLast()?
Оба метода (**Deque**) удаляют и возвращают последний элемент очереди.
* Метод **removeLast**(); бросает исключение **NoSuchElementException**, если очередь пуста.
* Метод **pollLast**(); возвращает **null**, если очередь пуста.
35
Назовите самую распространенную реализацию Deque.
* **ArrayDeque**;
* **LinkedList**;
