Коллекции и generics в Java: вопросы на собеседовании с подвохом

Серия подготовки: к обзору тем Java-собеседования.

Коллекции Java помогают хранить несколько значений и находить нужное: список товаров, уникальные метки, остатки по коду склада. На собеседовании важно объяснить, какую задачу решает выбранная коллекция и что произойдёт при изменении данных. Восемнадцать вопросов ниже идут от простого выбора списка к поиску по ключу, копированию и ограничениям типов.

Здесь достаточно знать базовые переменные и методы. Коллекцию иногда называют контейнером: это объект, который хранит элементы или связи между ними. Переменная хранит ссылку на объект, то есть даёт доступ к нему; присваивание ссылки не копирует сам объект. Запись List<String> означает «список строк». Часть в угловых скобках задаёт тип элемента, а зачем нужны более сложные записи типов, разберём постепенно.

Примеры подходят для Java 17 и 21. Условия и данные учебные. Под контрактом будем понимать документированные обещания: например, разрешены ли повторы, можно ли менять список и как определяется совпадение ключей. Контракт интерфейса задаёт общее поведение, а конкретный класс выбирает способ его выполнения.

Выбор структуры данных

1. Чем различаются List, Set и Map?

List — список с позициями: можно получить первый, второй и следующий элемент. Позиции, или индексы, отсчитываются от нуля. Одинаковые элементы обычно допустимы. Set — множество: совпадающий по его правилам элемент не появляется второй раз. Map — отображение, которое часто называют картой: оно связывает ключ со значением. Одному ключу соответствует не больше одного значения.

Например, список хранит товары в порядке добавления в корзину, множество — уникальные выбранные метки, карта — остаток товара по коду. У карты код является ключом, а остаток — значением. Добавление нового значения под уже существующим ключом заменяет прежнее, а не создаёт второй такой же ключ.

Эти имена обозначают интерфейсы — общие правила для нескольких классов. Map не наследует интерфейс Collection, объединяющий обычные коллекции элементов. Но из карты можно получить представления ключей, значений и пар «ключ — значение». Представление даёт доступ к данным исходного объекта; оно не обязательно создаёт независимую копию. Порядок и правило совпадения зависят от конкретного класса, поэтому одного названия интерфейса для выбора недостаточно.

2. Когда выбирать ArrayList, а когда LinkedList?

ArrayList хранит ссылки на элементы в массиве — последовательности ячеек, к которым можно обратиться по индексу. Поэтому получение элемента по индексу не требует проходить предыдущие. При вставке в середину последующие ссылки приходится сдвигать. Если свободных ячеек в массиве не хватает, создаётся более вместительное хранилище и данные переносятся.

LinkedList хранит узлы: каждый узел содержит элемент и связи с соседями. Поменять связи около уже найденного узла можно быстро. Но чтобы дойти до элемента по индексу, приходится пройти цепочку узлов. Поэтому add(index, value) в середине не становится автоматически быстрее: сначала нужно найти место.

Для сравнения роста работы используют обозначения сложности. O(1) означает, что число действий не растёт вместе с размером списка, O(n) — что оно может расти пропорционально числу элементов n. Добавление в конец ArrayList называют амортизированно постоянным: редкие дорогие расширения распределяются на много дешёвых добавлений. Это оценка работы, а не обещание времени в миллисекундах.

Готовый итератор — объект для последовательного обхода — может уже стоять у нужного узла LinkedList. Тогда повторный поиск не нужен. Но для очереди, где добавляют и удаляют на концах, стоит также рассмотреть ArrayDeque. Выбирайте по операциям задачи, учитывая память для узлов и фактическую скорость обхода.

HashMap, ключи и порядок

3. Как HashMap ищет значение?

HashMap использует хеш-таблицу. Хеш — целое число, получаемое методом hashCode() ключа. Оно помогает выбрать корзину, по-английски bucket: небольшую область внутренней таблицы с записями-кандидатами. После выбора области карта проверяет, совпадает ли ключ с нужным; для смыслового равенства используется equals.

Вызов put(key, value) добавляет пару. Если равный ключ уже есть, карта заменяет значение. Вызов get(key) повторяет поиск и возвращает связанное значение. Два разных ключа могут иметь один хеш: это коллизия. Они могут храниться вместе в одной корзине, поскольку проверка равенства отличает их друг от друга.

Представьте остатки товаров по коду. Сначала хеш кода направляет поиск в часть таблицы, затем сравнение кода выбирает запись внутри неё. При хорошем распределении хешей обычно не приходится проверять все товары. Поэтому документация связывает ожидаемое O(1) для get/put именно с хорошим распределением. Все реализации Map не обязаны иметь корзины: это способ работы HashMap, а не определение карты вообще.

4. Почему изменяемый ключ может «потеряться»?

Карта размещает запись исходя из данных ключа в момент добавления. Если затем изменить поле, от которого зависят equals и hashCode, новый поиск может пойти в другую корзину. Сама ссылка на ключ осталась прежней, но правила его поиска изменились. Поэтому значимые для равенства данные ключа должны оставаться стабильными, пока он хранится в карте.

В примере поле id служит и номером ключа, и его хешем. Конструктор Key(int id) задаёт номер новому объекту; this.id означает поле именно этого объекта. Пометка @Override подтверждает замену стандартных методов. Проверка instanceof Key проверяет вид объекта, а запись (Key) other позволяет обратиться к нему как к Key. Знак && означает «и»: правая проверка выполняется, только если левая успешна.

final class Key {
    int id;
    Key(int id) { this.id = id; }
    @Override public int hashCode() { return id; }
    @Override public boolean equals(Object other) {
        return other instanceof Key && id == ((Key) other).id;
    }
}

Map<Key, String> stock = new HashMap<>();
Key key = new Key(1);
stock.put(key, "available");
key.id = 2;
System.out.println(stock.get(key)); // null в этом примере HashMap

1. new Key(1) создаёт ключ с номером 1. В Map<Key, String> тип ключа — Key, тип значения — строка.
2. put сохраняет значение available, используя тогдашний хеш 1.
3. Строка key.id = 2 меняет поле уже сохранённого объекта. Теперь его метод hashCode возвращает 2.
4. В показанном примере HashMap поиск через get идёт по новому хешу и не находит старую запись. Печатается null, обозначение отсутствующего результата.

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

5. Что происходит при коллизиях и расширении таблицы?

Если несколько ключей попали в одну корзину, карта должна различить записи внутри неё. Чем больше там кандидатов, тем больше может потребоваться работы. Хеши, одинаковые для почти всех ключей, лишают таблицу преимущества быстрого выбора небольшой области поиска.

При росте данных HashMap увеличивает внутреннюю таблицу и распределяет записи по новым корзинам. Размер карты — число сохранённых пар, вместимость — число корзин, а коэффициент заполнения задаёт условие, когда таблицу пора расширить. Они не равны: запас на 100 записей не означает, что в карте уже лежат 100 пар. При переносе записей отдельная операция добавления может потребовать заметно больше работы.

В реализациях современных JDK, то есть комплектов Java, перегруженная корзина при определённых условиях может храниться как дерево. Это помогает ограничить последствия некоторых коллизий. Но конкретные пороги зависят от реализации, а дерево не даёт права обещать любой HashMap сложность O(log n) при любых ключах. Это обозначение означает медленный рост числа шагов при росте данных; обязательные гарантии нужно проверять у выбранной структуры.

6. Чем TreeMap отличается от HashMap?

TreeMap хранит ключи в порядке сравнения. Например, при числовых ключах можно получить их по возрастанию или найти ближайший ключ не меньше заданного. Для поиска, добавления и удаления документация обещает логарифмическую сложность: при увеличении данных вдвое путь поиска не увеличивается вдвое. HashMap ищет по хешу и не обещает порядок при обходе.

TreeMap использует естественное сравнение самих ключей либо переданный Comparator — отдельное правило сравнения двух значений. Если оно вернуло ноль, карта считает ключи одним ключом. Сравнение клиентов только по длине фамилии поэтому опасно: две разные фамилии одной длины получат ноль, и значение для одного клиента заменит другое.

Для соблюдения общего договора Map совпадение по сравнению должно быть согласовано с equals. Наличие правильного equals не заставляет TreeMap дополнительно исправлять ошибочное правило сравнения. Выбирайте дерево, когда нужен порядок или поиск диапазона, и отдельно определяйте, когда два ключа действительно обозначают одну запись.

7. Как написать Comparator и не потерять данные?

Comparator отвечает на вопрос, какое из двух значений должно идти раньше. Отрицательный результат означает «первое раньше второго», положительный — «позже», ноль — «они равны в этом порядке». Правило должно быть последовательным: если A раньше B, а B раньше C, то A должен быть раньше C. Иначе сортировка не сможет опереться на сравнение.

В короткой записи (a, b) -> ... слева перечислены два входных значения, справа — способ вычислить результат. Это лямбда, то есть передаваемое правило действия. Вычитать числа через a.score - b.score опасно: int имеет ограниченный диапазон, и при переполнении знак результата может стать неверным. Для чисел используйте Integer.compare или готовые средства построения компараторов.

Например, задачи сначала сравнивают по приоритету, а при его совпадении — по уникальному номеру. Добавление второго сравнения через thenComparing сохраняет различие разных задач. Для сортировки списка ноль не удаляет элементы. Но TreeSet и TreeMap используют ноль для определения совпадения, поэтому тот же Comparator может объединить записи. Отдельно задайте направление порядка и разрешены ли отсутствующие значения null.

8. Почему get вернул null: ключа нет или значение пустое?

У HashMap оба варианта возможны. В карте может вообще не быть записи под ключом, а может быть запись, которой явно назначили значение null. В обоих случаях get(key) возвращает null. Метод containsKey(key) отдельно отвечает, существует ли сам ключ.

Например, отсутствие кода заказа и заказ с ещё не назначенным курьером — разные ситуации. Если неназначенного курьера записывают как null, одного get недостаточно. Выбирайте явный способ различать эти состояния, чтобы вызывающий код не угадывал смысл пустого результата.

Это разрешение относится не ко всем картам. ConcurrentHashMap, рассчитанная на согласованную работу нескольких потоков выполнения, запрещает null и для ключей, и для значений. TreeMap с естественным порядком не умеет сравнивать null-ключ; специально переданный Comparator может поддерживать его. Сначала определите конкретный класс, затем рассуждайте о пустых значениях.

Изменения, обход и копии

9. Всегда ли изменение коллекции вызывает ConcurrentModificationException?

Нет. Итератор хранит положение текущего обхода. Когда другой вызов меняет устройство списка, этот обход может стать неправильным: например, позиции элементов сдвинутся после удаления. Итераторы ряда обычных коллекций пытаются обнаружить такое изменение и выбросить ConcurrentModificationException. Такое раннее сообщение об ошибке называют fail-fast.

Оно возможно и в одном потоке выполнения: обычный for-each использует итератор, а удаление через сам список происходит в обход него. Если итератор поддерживает удаление, его remove() позволяет удалить полученный элемент с учётом обхода. Метод списка removeIf тоже выражает удаление по условию без ручной несогласованной правки внутри цикла.

Структурное изменение меняет состав или размер; у ArrayList замена элемента через set к нему не относится. Fail-fast старается обнаружить ошибку, но не даёт гарантии обнаружить все несогласованные изменения нескольких потоков. Другие коллекции могут обходить снимок данных или допускать часть одновременных изменений по своим правилам. Отсутствие исключения не доказывает безопасность: для общей изменяемой коллекции нужны отдельные правила согласования доступа.

10. Чем отличается неизменяемое представление от копии?

Collections.unmodifiableList(source) даёт доступ к исходному списку с запретом изменений через этот доступ. Это представление: другой код всё ещё может изменить source, и изменение станет видно читателю. List.copyOf(source) сохраняет состав на момент вызова и запрещает менять полученный список. Последующее добавление в исходный список на этот состав не влияет.

В примере List.of("sales") подготавливает список из одной строки, а new ArrayList создаёт из него изменяемый список. var означает, что тип переменной выводит компилятор из значения справа. Затем создаются представление view и копия состава copy.

var source = new ArrayList<>(List.of("sales"));
var view = Collections.unmodifiableList(source);
var copy = List.copyOf(source);
source.add("support");
System.out.println(view); // [sales, support]
System.out.println(copy); // [sales]

После source.add("support") в исходном списке два отдела. Представление view смотрит на этот же источник и печатает [sales, support]. Список copy сохранил только одну строку и печатает [sales]. Если попытаться добавить отдел через view или copy, запрет изменения не исчезнет: работать можно было именно с source.

Оба результата хранят ссылки на элементы. Если вместо строк там были бы изменяемые объекты отделов, смена адреса одного отдела могла бы быть видна в обоих результатах. Отдельный состав списка и отдельные копии всех данных — разные требования; такое копирование ссылок называют поверхностным.

11. Что неожиданного в Arrays.asList, List.of и Set.of?

Arrays.asList показывает массив как список фиксированного размера. В существующей позиции можно заменить элемент, но добавление или удаление позиции не поддерживается. Список связан с исходным массивом: замена через одну сторону видна через другую. Ошибка UnsupportedOperationException означает, что выбранная операция изменения не поддерживается.

List.of создаёт список, в котором запрещены добавление, удаление и замена; null-элементы тоже запрещены, а одинаковые значения разрешены. Set.of создаёт множество без изменений и дополнительно отвергает повторы. Это методы-фабрики: они предоставляют объект, но не обещают каждый раз создавать отдельный экземпляр. Поэтому их результат оценивают по данным, а не по совпадению ссылок.

Примитивный массив требует внимания. В Arrays.asList(new int[]{1, 2}) один переданный объект — целый массив int. Результат содержит этот массив как один элемент, а не два объекта Integer. Если нужны отдельные целые в списке, можно построить числовой поток из массива и упаковать каждое число в Integer. Упаковка — превращение примитивного значения в объект-оболочку.

12. Что удалит List<Integer>.remove(1)?

Удалится элемент по индексу 1, то есть второй. У List существуют два метода с именем remove: remove(int index) и remove(Object value). Несколько методов с одним именем и разными параметрами называют перегрузкой. Число 1 прямо в коде имеет примитивный тип int, поэтому компилятор выбирает версию с индексом.

Чтобы удалить значение 1, передают объект-оболочку Integer.valueOf(1). В примере сначала удаляется стоящая на второй позиции семёрка, а затем первая найденная единица.

var codes = new ArrayList<>(List.of(1, 7, 1));
codes.remove(1);
System.out.println(codes); // [1, 1]
codes.remove(Integer.valueOf(1));
System.out.println(codes); // [1]

Исходный список — [1, 7, 1]; его индексы 0, 1 и 2. Первый remove убирает позицию 1, поэтому остаётся [1, 1]. Второй получает объект Integer и выбирает удаление по равному значению. Удаляется только первое совпадение, вывод — [1].

Перед ответом полезно назвать тип аргумента и выбранный метод. Если список допускает null, null-элемент удаляют по значению. А попытка извлечь примитивный индекс из отсутствующего Integer даст другое исключение — NullPointerException. Выбор перегрузки и допустимость значения нужно проверять отдельно.

13. subList создаёт отдельный список?

Нет: subList(from, to) возвращает представление участка исходного списка. Начальная позиция включается, конечная не включается. Например, диапазон от 0 до 3 охватывает позиции 0, 1 и 2. Изменение через поддерживаемые методы представления отражается в исходном списке.

Если у списка задач нужна отдельная изменяемая тройка, её можно создать через new ArrayList<>(tasks.subList(0, 3)). Конструктор ArrayList переносит элементы диапазона в собственную структуру. Добавление или удаление в этой новой структуре не меняет состав исходного списка. Но объекты задач остаются общими, поскольку копируются ссылки на них.

Если сохранить subList, а затем изменить размер исходного списка в обход этого представления, дальнейшее поведение представления уже не определено его обычным контрактом. Оно не обязано оставаться прежним «окном» с теми же позициями. Поэтому нужно согласовать, кто и как долго может менять исходный список, или сразу сохранить отдельный состав.

Generics: какие гарантии даёт компилятор

14. Почему List<Integer> не является List<Number>?

Generics, или обобщённые типы, позволяют явно указать, с какими типами работает класс или метод. В List<Integer> аргумент типа — Integer, то есть список обещает принимать целочисленные оболочки. Number — общий родитель для Integer и, например, Double, оболочки дробного числа.

Предположим, Java разрешила присвоить List<Integer> переменной типа List<Number>. Тогда через вторую переменную можно было бы добавить Double: для списка Number это допустимое число. Но обе переменные указывали бы на один список. Первая по-прежнему обещала бы получать Integer, хотя внутри уже лежит Double. Чтобы такого несоответствия не возникало, присваивание запрещено.

Правило называют инвариантностью: отношение «Integer является подтипом Number» не переносится автоматически на List с этими аргументами. Если нужен метод, читающий разные виды числовых списков, используют специальное ограничение типов, разобранное дальше. У массивов есть другое правило: массив строк можно рассматривать как массив объектов. Это ковариантность; её безопасность дополнительно проверяется во время записи. Различие ещё раз увидим в последнем примере.

15. Что означает PECS и как применять extends и super?

Знак ? в типе называется wildcard: он обозначает неизвестный конкретный тип. Запись ? extends Number означает «Number или какой-то его подтип», а ? super Integer — «Integer или какой-то его родительский тип». Это ограничения неизвестного типа, а не команды создавать новые классы.

PECS расшифровывают как Producer Extends, Consumer Super. Источник, из которого ваш метод получает значения, удобно описывать через extends. Приёмник, куда метод добавляет значения, — через super. Например, метод читает целые оценки из одного списка и добавляет их в другой: источником может быть список Integer, приёмником — список Integer, Number или Object.

Когда один метод должен переносить не только целые, вводят параметр типа T: это имя типа, который уточнится при вызове. Пара List<? extends T> и List<? super T> связывает чтение и запись одним T. При T = Integer источник даёт целые, а приёмник согласен их принимать. Источник ? extends Number без такого уточнения мог бы содержать Double; его значения нельзя безопасно отправлять в приёмник только целых.

Сначала определите направление данных, затем выбирайте запись типа. Если метод и читает, и записывает значения одного точного типа, может понадобиться обычный List<T>. PECS помогает выразить нужные возможности, а не требует расставлять вопросительные знаки везде.

16. Правда ли extends означает «только чтение», а super — «только запись»?

Это сокращённая подсказка, у которой есть границы. Из List<? extends Number> можно читать Number: какой бы числовой подтип там ни был, он остаётся Number. Но добавить произвольный Integer нельзя. За неизвестным типом может скрываться Double, и добавление Integer нарушило бы обещание исходного списка.

При этом удаление или очистка не добавляют элемент неверного типа и могут быть разрешены у изменяемого списка. Значит, extends не превращает объект в неизменяемый. Из List<? super Integer> тоже можно читать, но гарантирован только результат типа Object — общего родителя объектов. Ведь переданным списком может быть List<Object>, где уже лежат строки, либо List<Number> с дробными числами.

Generics отвечают за допустимые типы операций. Поддерживает ли конкретная коллекция изменение вообще — отдельный вопрос. Даже типобезопасное добавление закончится UnsupportedOperationException, если передали список с запретом добавления. Не смешивайте разрешение компилятора и возможности самого объекта во время работы.

17. Что стирается при type erasure?

Type erasure переводится как «стирание типов». Компилятор использует параметры generics для проверок, но не создаёт отдельный класс ArrayList для строк и другой класс ArrayList для целых. При подготовке выполняемого кода параметр T заменяется его границей, а без неё — Object. Где необходимо, добавляются приведения: проверки и указания, как обращаться к полученному объекту.

Например, компилятор позволяет читать String из правильно заполненного List<String>. Во время выполнения используется общий механизм списка, а подготовленный компилятором код обеспечивает нужное приведение результата. Для сохранения вызовов переопределённых обобщённых методов могут добавляться bridge methods — небольшие служебные методы, связывающие варианты с разными типами.

Поэтому нельзя проверить value instanceof List<String>: обычный объект списка не хранит свой аргумент String так, как массив хранит тип элементов. Но отдельные описания объявлений generics сохраняются в метаданных — служебных сведениях о классах. Reflection, средство исследования этих объявлений во время работы, может их читать. Это не превращает любой список в проверяемый список строк.

Сырой тип List без угловых скобок ослабляет проверки. Если через него добавить неподходящий объект, ошибка приведения может появиться позднее при чтении как String. Предупреждение unchecked сообщает, что компилятор не может подтвердить безопасность операции; его нужно разобрать, а не просто скрыть.

18. Почему нельзя создать new T[] и чем массивы опаснее списка?

Массив помнит тип своих элементов во время выполнения. Если это массив String, он не разрешит записать число даже через более общую ссылку. Для произвольного T после стирания нет достаточной информации, чтобы создать массив с нужной такой проверкой. Поэтому выражение new T[10] напрямую не разрешено.

Если массив действительно нужен, метод может получить описание типа элементов или фабрику — правило создания нужного массива. Для обычного накопления данных часто достаточно списка. Следующий пример показывает, на каком этапе массив и список останавливают недопустимую операцию.

Object[] values = new String[2];
values[0] = "route";
// values[1] = 42; // ArrayStoreException

List<String> names = new ArrayList<>();
// List<Object> objects = names; // ошибка компиляции

new String[2] создаёт массив на две строки; незаполненные позиции содержат null. Переменная values объявлена как массив Object, поэтому строка с числом 42 выглядела бы допустимой для компилятора. Но фактический массив остаётся массивом String. Если раскомментировать запись 42, при запуске возникнет ArrayStoreException — исключение о неподходящем типе записываемого элемента. Запись строки route допустима.

У списка ситуация останавливается раньше: закомментированное присваивание List<String> в List<Object> не пройдёт компиляцию. Именно этот запрет не позволяет позднее добавить число через более общий тип. В примере опасные строки закомментированы, поэтому сами по себе исключения не выбрасываются: комментарии показывают, что изменится при включении строк.

Как проверить готовность

Возьмите задачу хранения товаров по коду. Сначала объясните, почему нужен поиск по ключу, какие два кода считаются одинаковыми и может ли код меняться. Затем добавьте условия: показывать товары в порядке добавления и выдавать другим частям программы список без права изменения. Для каждого условия отдельно выберите структуру и решите, нужно ли сохранить независимый состав данных.

Для generics проговорите перенос целых из одного списка в другой. Назовите тип, который гарантирован при чтении, и тип, который разрешено добавлять. Затем замените целые дробными числами и проверьте, какое обещание перестало выполняться. Такой разбор помогает объяснять запреты компилятора через возможную ошибку в данных, а не через заученную формулу.