сеньорчикОткрыть в Telegram
← вся теориятеория к собесу · Коллекции Java

Выбор структуры и сложность операций

Выбор коллекции: тест на инженерное мышление

Сорок тысяч проверок принадлежности. Через список - 609 миллисекунд. Через множество - 11,5. Пятидесятикратная разница, а в коде это одна строка: перегнать список в HashSet перед циклом.

«Какую коллекцию возьмёшь под задачу?» - вопрос, где зубрёжка не помогает. Проверяют, умеешь ли ты рассуждать от операций. Слабый ответ звучит как «HashMap, она быстрая». Сильный называет доминирующую операцию, потом структуру, потом худший случай и цену памяти.

// Формулировки: «чем проверять принадлежность миллиона идентификаторов?», «почему код простой, а работает медленно?», «какая коллекция под очередь задач?»

Карта выбора: от операции к структуре

Дефолты по доминирующей операции короткие. Доступ по индексу - ArrayList. Проверка принадлежности и уникальность - HashSet. Ключ и значение - HashMap. Нужна сортированность или запросы по диапазону - TreeMap и TreeSet. Очередь и стек - ArrayDeque. Нужен минимум - PriorityQueue.

Стоимости: у ArrayList доступ по индексу постоянный, вставка в середину линейная. Hash-структуры в среднем постоянные, в худшем случае логарифмические. Древовидные - логарифмические на всём. У PriorityQueue заглянуть в минимум стоит копейки, а добавить или извлечь - логарифм.

// Про PriorityQueue есть отдельная ловушка, я её проверил. Это двоичная куча, и упорядочен в ней только корень. Обход очереди из чисел 5, 1, 4, 2, 3, 9, 7 выдал [1, 2, 4, 5, 3, 9, 7] - почти отсортировано, но не отсортировано. По порядку элементы отдаёт только извлечение: [1, 2, 3, 4, 5, 7, 9].

PriorityQueue
двоичная куча: упорядочен только корень
худший случай
деградация на коллизиях и расширениях, её надо называть

Скрытые квадраты и цена обёрток

Самый частый тормоз на код-ревью - проверка принадлежности списку внутри цикла по другому списку. Линейная операция внутри линейного цикла даёт квадрат: миллион на миллион это триллион сравнений. Мой замер на сорока тысячах уже даёт 609 мс против 11,5 - а объём растёт квадратично.

Память - вторая скрытая цена. Замерил пять миллионов чисел: ArrayList<Integer> занял 98 мегабайт, обычный массив int - 21 мегабайт. Почти впятеро, потому что каждое число за пределами кэша обёрток это отдельный объект с заголовком плюс ссылка на него в массиве.

// На собеседовании это звучит как «код простой, а работает медленно и жрёт память - что смотришь первым». Ответ: проверку принадлежности внутри цикла и упаковку чисел в объекты.

// квадрат: contains бежит по списку
for (var id : requests) if (allowedList.contains(id)) ...

// линейно: множество решает
var allowed = new HashSet<>(allowedList);
скрытый квадрат
линейная операция внутри линейного цикла
цена упаковки
Integer это объект с заголовком, а не четыре байта

Конкурентные аналоги и неизменяемые фабрики

Многопоточные дефолты: вместо HashMap - ConcurrentHashMap, для схемы «производитель и потребитель» - блокирующая очередь с ожиданием. А вот CopyOnWriteArrayList надо брать осознанно: каждая запись копирует ВЕСЬ массив.

Замерил цену: 20 000 добавлений в CopyOnWriteArrayList заняли 447 миллисекунд, в обычный синхронизированный список - 1,8. Разница в 248 раз. Список слушателей событий, который меняется раз в час, - да. Горячий журнал записей - категорически нет.

Обёртки вида synchronizedList и synchronizedMap - наследие: они вешают один общий замок, поэтому все операции выстраиваются в очередь, а обход всё равно требует ручной синхронизации. ConcurrentHashMap масштабируется несравнимо лучше, у неё замки на уровне отдельных ящиков.

// Неизменяемые фабрики List.of, Map.of и Set.of - хороший дефолт для констант и возвращаемых значений: их безопасно делить между потоками и невозможно случайно испортить.

CopyOnWriteArrayList
копия всего массива на каждую запись
блокирующая очередь
очередь с ожиданием для производителя и потребителя

Как отвечать: «Нужно проверять принадлежность миллиона идентификаторов - какую структуру возьмёшь?»

HashSet. Доминирующая операция здесь - проверка принадлежности, у множества она в среднем за постоянное время, у списка линейная, и внутри цикла это превращается в квадрат. Я мерил на сорока тысячах: списком 609 миллисекунд, множеством 11,5, и разрыв растёт квадратично. Худший случай оговорю сразу: при плохом hashCode ящики вырождаются, но с Java 8 длинные цепочки перестраиваются в дерево, так что деградация логарифмическая, а не линейная. Дальше посмотрю на ограничения. Если идентификаторы это примитивные числа и память критична, подумаю про отсортированный массив с двоичным поиском: логарифм вместо константы, зато без упаковки - я замерял, пять миллионов чисел в списке обёрток занимают 98 мегабайт против 21 у примитивного массива. А если множество только читают из многих потоков, просто сделаю Set.copyOf: неизменяемый, безопасный и без всякой синхронизации.

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

На чём валят

  • −Проверяют принадлежность списку внутри цикла. На сорока тысячах это уже 609 мс против 11,5 у множества.
  • −Ждут от обхода PriorityQueue отсортированного порядка. Упорядочен только корень, по порядку отдаёт лишь извлечение.
  • −Берут CopyOnWriteArrayList под частую запись. У меня 20 000 добавлений заняли 447 мс против 1,8 у обычного списка.
  • −Хранят миллионы чисел в списке обёрток. Пять миллионов заняли 98 мегабайт вместо 21 у примитивного массива.
  • −Ставят TreeMap «на всякий случай» и платят логарифм там, где хватало константы.

Проверьте себя

Пять вопросов из банка по этой подтеме. Всего их 18, остальные разбираются в тренажёре.

  1. #choosing_complexity1 / 5
    Нужно всегда быстро доставать минимальный элемент из меняющегося набора. Что взять?
    A)Отсортированный ArrayList: держать список отсортированным и брать нулевой элемент как минимум
    B)HashSet: он хранит элементы так, что минимальный оказывается первым при обходе множества
    C)PriorityQueue (бинарная куча)
    D)TreeSet и полный обход всех элементов при каждом запросе, чтобы найти среди них наименьший
    показать ответ и разбор
    +C)PriorityQueue (бинарная куча)

    // разбор: PriorityQueue — бинарная куча: минимум (или максимум по компаратору) доступен на вершине за O(1) (peek), а offer/poll — O(log n). Идеально для «всегда доставать самый приоритетный»: планировщики, алгоритм Дейкстры, top-K. Важно: обход/toString кучи НЕ отсортирован — упорядочен только путь извлечения через poll. TreeSet тоже даёт минимум, но не хранит дубликаты и дороже на вставке.

  2. #choosing_complexity2 / 5
    Часто вставляем/удаляем по индексу в СЕРЕДИНЕ большого списка. ArrayList или LinkedList?
    A)LinkedList однозначно: вставка в середину у него O(1) независимо от размера и позиции
    B)ArrayList однозначно: вставка по индексу в него не сдвигает элементы и потому стоит O(1)
    C)Разницы нет: у обоих вставка в середину по индексу стоит строго O(log n) за счёт бинарного поиска
    D)Оба слабы: ArrayList — сдвиг O(n), LinkedList — поиск позиции O(n)
    показать ответ и разбор
    +D)Оба слабы: ArrayList — сдвиг O(n), LinkedList — поиск позиции O(n)

    // разбор: Хитрый случай: у ArrayList вставка/удаление по индексу в середине — O(n) из-за сдвига хвоста. У LinkedList сама операция в узле O(1), НО чтобы дойти до i-й позиции по индексу, нужен проход O(n) — выгода теряется. LinkedList выигрывает лишь когда позиция уже известна через ListIterator (идём и правим по ходу). Если по-настоящему нужны частые вставки в середину — часто лучше другая структура (дерево, gap buffer).

  3. #choosing_complexity3 / 5
    Когда предпочесть LinkedHashMap обычному HashMap?
    A)Когда нужен предсказуемый порядок обхода (вставки или доступа)
    B)Когда карта очень большая: LinkedHashMap заметно экономнее HashMap по памяти на тех же данных
    C)Когда нужен максимально быстрый get: LinkedHashMap работает за O(1), а HashMap — за O(log n)
    D)Когда ключи должны сортироваться по возрастанию: LinkedHashMap автоматически упорядочивает их
    показать ответ и разбор
    +A)Когда нужен предсказуемый порядок обхода (вставки или доступа)

    // разбор: LinkedHashMap = HashMap + двусвязный список поверх записей, поэтому обход идёт в предсказуемом порядке ВСТАВКИ (а в access-order режиме — в порядке обращений, что даёт готовую основу для LRU-кэша через removeEldestEntry). Скорость операций как у HashMap (O(1)), но памяти чуть больше. Берут, когда важен стабильный порядок обхода, но сортировка (TreeMap) избыточна.

  4. #choosing_complexity4 / 5
    Нужен неизменяемый снимок данных для передачи наружу. Что использовать?
    A)Collections.synchronizedList — он делает список неизменяемым и заодно потокобезопасным сразу
    B)List.copyOf(...) или List.of(...) — immutable-коллекция
    C)Обычный ArrayList, просто помеченный ключевым словом final при объявлении переменной-поля
    D)Отдать наружу ссылку на внутренний изменяемый список — вызывающий всё равно не сможет его менять
    показать ответ и разбор
    +B)List.copyOf(...) или List.of(...) — immutable-коллекция

    // разбор: Чтобы отдать данные наружу без риска, что их изменят, возвращают неизменяемую коллекцию: List.copyOf(src) (делает независимую immutable-копию) или List.of(...). Тогда любые add/remove у получателя бросают UnsupportedOperationException. final у переменной фиксирует лишь ссылку, а не содержимое; synchronizedList — про потоки, не про неизменяемость; отдавать ссылку на внутренний изменяемый список — утечка инкапсуляции.

  5. #choosing_complexity5 / 5
    Нужны уникальные элементы С сохранением порядка их добавления. Что взять?
    A)TreeSet: он хранит уникальные элементы и заодно сохраняет тот порядок, в котором их добавляли
    B)ArrayList с ручной проверкой contains перед каждым добавлением — простой и эффективный способ
    C)LinkedHashSet
    D)HashSet: он и обеспечивает уникальность, и обходит элементы ровно в порядке их вставки в множество
    показать ответ и разбор
    +C)LinkedHashSet

    // разбор: LinkedHashSet сочетает уникальность (как HashSet) с сохранением порядка ВСТАВКИ (связный список поверх). Это ровно «уникальные в порядке добавления» за амортизированное O(1). TreeSet тоже уникален, но упорядочивает по сортировке, не по вставке. ArrayList с проверкой contains даёт порядок, но каждая вставка — O(n) на поиск дубля. Частый практичный выбор для дедупликации с сохранением очередности.

дальше

Теорию прочитали. Навык ставится повторением

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

Открыть тренажёрВся тема: Коллекции Java
читать дальше