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 элементов; у деревьев и связных списков такой ёмкости нет. Это не контракт интерфейса.
Закрепите вопросы в пробном режиме тренажёра
Без обязательного входа: ответьте, сравните себя с опорными пунктами и оставьте на повторение то, что ещё не готовы принять. В поддерживаемых темах незавершённый прогон останется в браузере.