Core-2 · Тема 2 из 5

Collections Framework

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

  • 39вопросов

Чек-лист подготовки

Вопросы для самопроверки

Что такое «коллекция»?

Короткий ответ

Коллекция – это объект, который содержит набор объектов одного типа. Каждый из этих объектов в коллекции называется элементом.

Расскажите про иерархию коллекций

Короткий ответ

Collection объединяет List, Set и Queue/Deque; Map стоит отдельно и хранит пары ключ–значение. Реализацию выбирают по требованиям к порядку, уникальности, сортировке, индексному доступу и сложности операций.

Почему Map — это не Collection, в то время как List и Set являются Collection?

Короткий ответ

Коллекция (List и Set) представляет собой совокупность некоторых элементов (обычно экземпляров одного класса).Map -это совокупность пар "ключ"-"значение". У map нет итерабл, не понятно по чему проводить итерацию

В чем разница между java.util.Collection и java.util.Collections?

Короткий ответ

java.util.Collections - Это утилитарный класс, который предоставляет статические методы для работы с коллекциями. Эти методы включают такие операции, как сортировка, поиск, реверсирование и другие манипуляции с коллекциями. java.util.Collection - Это корневой интерфейс для всех коллекций в Java.

Какая разница между итераторами с fail-fast и fail-safe поведением? (С примерами)

Короткий ответ

Итератор fail-safe не вызывает исключений при изменении структуры коллекции, потому что работает с её клоном. Пример fail-safe - CopyOnWriteArrayList и итератор keySet коллекции ConcurrentHashMap.

Чем различаются Enumeration и Iterator?

Короткий ответ

Iterator имеет больше методов работы с коллекциями и был специально введен в java2, вместо Enumeration(interface). Рекоммендуется юзать Iterator.

Как между собой связаны Iterable, Iterator и «for-each»?

Короткий ответ

Интерфейс Iterable содержит всего один метод iterator(), который возвращает объект типа Iterator. • Классы, реализующие интерфейс Iterable, могут быть использованы в циклах foreach (расширенном цикле) и методах, ожидающих итерируемые объекты.

Можно ли итерируясь по ArrayList удалить элемент? Какое вылетит исключение?

Короткий ответ

Можно, но нужно использовать iterator.remove(). Иначе при прохождении по ArrayList в цикле for сразу после удаления элемента будет ConcurrentModificationException.

Как поведёт себя коллекция, если вызвать iterator.remove()?

Короткий ответ

Этот метод удаляет текущий элемент. Важный момент заключается в том, что сначала этот элемент необходимо получить с помощью метода next(), если мы вызовем метод remove() до метода next(), то мы получим IllegalStateException.

Чем Set отличается от List?

Короткий ответ

предоставляют различные структуры данных и имеют различное поведение. List — это упорядоченный список. Объекты хранятся в порядке их добавления в список. Доступ к элементам списка осуществляется по индексу. Set — неупорядоченное множество уникальных (неповторяющихся) объектов, доступ по ключу.

Расскажите про интерфейс Set.

Короткий ответ

Интерфейс Set расширяет интерфейс Collection. Set не добавляет новых методов, только вносит изменения унаследованные. Set - неупорядоченный набор неповторяющихся элементов В частности, метод add() добавляет элемент в коллекцию и возвращает true, если не было такого элемента.

Расскажите про реализации интерфейса Set

Короткий ответ

В HashSet порядок добавления элементов будет непредсказуемым - используется хэширование для ускорения выборки. В TreeSet объекты хранятся отсортированными по возрастанию из-за применения к/ч дерева. LinkedHashSet хранит элементы в порядке добавления.

В чем отличия TreeSet и HashSet?

Короткий ответ

HashSet быстрее, чем TreeSet . В HashSet элементы в случайном порядке, в TreeSet в отсортированном. HashSet обеспечивает постоянную производительность - О(1) - для большинства операций, таких как add () , remove () и contains () , по сравнению с временем log(n), предлагаемым TreeSet.

Чем LinkedHashSet отличается от HashSet?

Короткий ответ

Основное различие в том, что LinkedHashSet сохраняет порядок вставки элементов, а HashSet - нет. В основе LinkedHashSet лежит LinkedHashMap вместо HashMap. Благодаря этому порядок элементов при обходе коллекции является идентичным порядку добавления элементов

Что будет, если добавлять элементы в TreeSet по возрастанию?

Короткий ответ

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

Как устроен HashSet, сложность основных операций.

Короткий ответ

Все классы, реализующие интерфейс Set, внутренне поддерживаются реализациями Map. HashSet в Java — это коллекция, которая использует хэш-таблицу для хранения элементов и обеспечивает уникальность элементов, не допускает дубликатов.

Как устроен LinkedHashSet, сложность основных операций.

Короткий ответ

В его основе лежит LinkedHashMap. Благодаря этому порядок элементов при обходе коллекции является идентичным порядку добавления элементов

Как устроен TreeSet, сложность основных операций.

Короткий ответ

Время для базовых операций - Логарифмическое время. TreeSet предназначен для хранения уникальных элементов (или ключей) Гарантирует порядок элементов - в основе лежит красно-черное дерево, которое умеет само себя балансировать.

Расскажите про интерфейс List

Короткий ответ

Контейнеры List хранит элементы в порядке добавления. Интерфейс List дополняет Collection несколькими методами, обеспечивающими вставку и удаление элементов в середине списка.

Как устроен ArrayList, сложность основных операций.

Короткий ответ

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

Что такое Queue?

Короткий ответ

Queue - Очередь. Этот список, который используется для реализации концепции FIFO (first in, first out) — «первым пришёл — первым ушёл». В Queue элементы обычно добавляются в конец.

Что такое Deque? Чем отличается от Queue?

Короткий ответ

Deque (двусторонняя очередь) в Java представляет собой интерфейс, который расширяет интерфейс Queue и представляет собой коллекцию, в которой элементы могут быть добавлены или удалены как в начале, так и в конце очереди. Он предоставляет методы для добавления, удаления и доступа к элементам с обоих концов очереди.

Приведите пример реализации Deque.

Короткий ответ

Linked list, ArrayDeque

Какая коллекция реализует FIFO?

Короткий ответ

Queue

Какая коллекция реализует LIFO?

Короткий ответ

LIFO в Java обычно реализуют через Deque, чаще ArrayDeque, используя push/pop. Stack и Vector — устаревший выбор; для конкурентного доступа нужна отдельная потокобезопасная структура или синхронизация.

Оцените количество памяти на хранение одного примитива типа byte в LinkedList?

Короткий ответ

Элемент LinkedList (Node): Ссылка на предыдущий элемент: 4 байта Ссылка на следующий элемент: 4 байта Ссылка на данные: 4 байта Заголовок объекта Node: 8 байтов Итого: 20 байтов, округляется до 24 байтов (кратно 8) Хранение значения byte: Примитив byte упаковывается в объект Byte Объект Byte…

Оцените количество памяти на хранение одного примитива типа byte в ArrayList?

Короткий ответ

для хранения одного примитива типа byte в LinkedList требуется приблизительно 40 байт памяти. Основная часть памяти уходит на накладные расходы для управления элементами в LinkedList (хранение ссылок на соседние узлы и заголовки объектов).

Какие существуют реализации Map?

Короткий ответ

TreeMap, HashMap, HashTable, LinkedHashMap

Как устроена HashMap, сложность основных операций? (Расскажите про принцип корзин)

Короткий ответ

HashMap — это одна из наиболее часто используемых коллекций в Java для хранения пар "ключ-значение". Корзины (buckets): Внутренне HashMap представляет собой массив, где каждый элемент называется "корзиной". Корзина используется для хранения всех элементов, хеш-коды которых приводят к одному и тому же индексу массива.

Как итерироваться по мапе?

Короткий ответ

В Java есть несколько способов итерации по Map. Вот основные методы: 1. Итерация по ключам и значениям с использованием entrySet(): java Map<String, Integer> map = new HashMap<>(); for (Map.Entry<String, Integer> entry : map.entrySet()) { String key = entry.getKey(); Integer value =…

Как устроена TreeMap, сложность основных операций?

Короткий ответ

Класс TreeMap<K, V> представляет отображение в виде дерева. Он наследуется от класса AbstractMap и реализует интерфейс NavigableMap, а следовательно, также и интерфейс SortedMap. Поэтому в отличие от коллекции HashMap в TreeMap все объекты автоматически сортируются по возрастанию их ключей.

Как работает HashMap при попытке сохранить в него два элемента по ключам с одинаковым hashCode(), но для которых equals() == false?

Короткий ответ

Если два ключа имеют одинаковый хеш-код (коллизия), HashMap использует метод equals() для различения этих ключей. В случае, если equals() возвращает false, оба элемента будут храниться в одной и той же "ячейке" (или "корзине") хеш-таблицы.

Что будет, если мы кладем в HashMap ключ, у которого equals и hashCode определены некорректно?

Короткий ответ

Объект скорее всего добавится, но обратно мы не сможем получить его.

Возможна ли ситуация, когда HashMap выродится в список даже с ключами имеющими разные hashCode()?

Короткий ответ

Это возможно в случае, если метод, определяющий номер корзины будет возвращать одинаковые значения.

Почему нельзя использовать byte[] в качестве ключа в HashMap?

Короткий ответ

Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Также у массивов не переопределен equals и выполняется сравнение указателей.

Будет ли работать HashMap, если все добавляемые ключи будут иметь одинаковый hashCode()?

Короткий ответ

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

Какое худшее время работы метода get(key) для ключа, которого нет в HashMap?

Короткий ответ

O(N). Худший случай - это поиск ключа в таблице, вырожденной в список, перебор ключей которой занимает линейно пропорциональное время количеству хранимых элементов.

Какое худшее время работы метода get(key) для ключа, который есть в HashMap?

Короткий ответ

O(N) - линейное

Начальная ёмкость коллекций

Короткий ответ

Ёмкость зависит от реализации: HashMap обычно начинает с лениво созданной таблицы на 16 ячеек при load factor 0,75, ArrayList — с лениво созданного массива примерно на 10 элементов; у деревьев и связных списков такой ёмкости нет. Это не контракт интерфейса.

Закрепите вопросы в пробном режиме тренажёра

Без обязательного входа: ответьте, сравните себя с опорными пунктами и оставьте на повторение то, что ещё не готовы принять. В поддерживаемых темах незавершённый прогон останется в браузере.

Запомнить