Java Interview Questions

Главная / Все ответы / Коллекции

Вопрос 2 · Раздел 4

В чём разница между List, Set и Queue?

Кэш-локальность = элементы расположены рядом в памяти. CPU загружает 64-байтную линию кэша за один раз, получая сразу 8-16 ссылок. Это ускоряет итерацию в 10-100 раз по сравнени...

Russian Коллекции Исходный Markdown
Версии по языкам: English Russian Ukrainian

🟢 Junior Level

List, Set и Queue — три основных типа коллекций в Java.

Главная разница:

Тип Порядок Дубликаты Доступ Аналогия
List Сохраняет порядок ✅ Можно По индексу list.get(0) Список покупок
Set Не гарантирует (кроме LinkedHashSet) ❌ Нельзя Только перебор Набор ключей
Queue FIFO (First-In-First-Out — первый добавленный элемент будет первым извлечён) ✅ Можно Только голову Очередь в магазине

Пример:

// List: порядок и дубликаты
List<String> list = new ArrayList<>();
list.add("B");
list.add("A");
list.add("B");  // OK
// → [B, A, B]

// Set: только уникальные
Set<String> set = new HashSet<>();
set.add("B");
set.add("A");
set.add("B");  // НЕ добавится
// → [A, B] (порядок не гарантирован)

// Queue: FIFO
Queue<String> queue = new ArrayDeque<>();
queue.offer("B");
queue.offer("A");
queue.poll();  // → "B" (первый пришёл, первый ушёл)

🟡 Middle Level

List (Последовательность)

// Реализации:
ArrayList    // Динамический массив → O(1) чтение
LinkedList   // Двусвязный список → O(n) чтение

// Операции:
list.get(0)       // O(1) для ArrayList, O(n) для LinkedList
list.add(e)       // O(1)* амортизированное
list.contains(e)  // O(n) линейный поиск
list.remove(0)    // O(n) сдвиг массива

Set (Множество)

// Реализации:
HashSet         // На базе HashMap → O(1) поиск
LinkedHashSet   // + порядок добавления
TreeSet         // Красно-черное дерево → O(log n), отсортированный

// Внутри HashSet:
// HashMap<E, Object> где value = static final Object PRESENT
// → Несмотря на один общий объект PRESENT, HashSet расходует больше памяти, чем ArrayList, из-за обёртки в HashMap.Node (ключ + value + hash + next pointer).

// Операции:
set.add(e)       // O(1) для HashSet, O(log n) для TreeSet
set.contains(e)  // O(1) для HashSet, O(log n) для TreeSet
set.remove(e)    // O(1) для HashSet

Queue (Очередь)

// Реализации:
ArrayDeque        // Кольцевой массив → O(1) вставка/удаление
PriorityQueue     // Binary Heap → O(log n), извлечение по приоритету
LinkedList        // Можно как Queue, но медленнее ArrayDeque

// Методы:
queue.offer(e)    // true/false (не бросает exception)
queue.add(e)      // бросает exception при ошибке
queue.poll()      // null если пуста
queue.remove()    // бросает exception если пуста
queue.peek()      // null если пуста
queue.element()   // бросает exception если пуста

Сравнение производительности

Операция ArrayList HashSet TreeSet ArrayDeque
Добавление O(1)* O(1) O(log n) O(1)
Поиск O(n) O(1) O(log n) O(n)
Удаление O(n) O(1) O(log n) O(1)
Доступ по индексу O(1) Н/Д Н/Д Н/Д

Когда что использовать

Сценарий Что выбрать Почему
Хранение с порядком List Сохраняет порядок
Проверка уникальности Set Быстрый contains
Обработка по порядку Queue FIFO
Сортировка TreeSet Автоматическая сортировка
Частые чтения ArrayList Кэш-локальность

Кэш-локальность = элементы расположены рядом в памяти. CPU загружает 64-байтную линию кэша за один раз, получая сразу 8-16 ссылок. Это ускоряет итерацию в 10-100 раз по сравнению с разбросанными элементами LinkedList.

Когда НЕ использовать

  • List (ArrayList): Не используйте для проверки уникальности — contains() = O(n)
  • HashSet: Не используйте если важен порядок вставки — возьмите LinkedHashSet
  • TreeSet: Не используйте если не нужна сортировка — O(log n) медленнее O(1)
  • Queue: Не используйте для произвольного доступа — возьмите List

🔴 Senior Level

Memory Footprint

ArrayList:
  → Object[] array (4-8 байт на ссылку)
  → Минимальный оверхед

HashSet:
  → HashMap внутри
  → Node<K,V> для каждого элемента
  → + static final Object PRESENT (один на все)
  → ~2x больше памяти, чем ArrayList!

TreeSet:
  → TreeMap (красно-черное дерево)
  → Entry<K,V> + left + right + parent + color
  → ~4x больше памяти, чем ArrayList

Concurrency

// List
CopyOnWriteArrayList      // Много чтений, мало записей
Collections.synchronizedList  // Универсальный, но медленный

// Set
ConcurrentHashMap.newKeySet()  // Лучший выбор!
Collections.synchronizedSet()

// Queue
ConcurrentLinkedQueue     // Lock-free, wait-free
LinkedBlockingQueue       // Producer-Consumer
ArrayBlockingQueue        // Bounded, один лок
SynchronousQueue          // Нулевая емкость

Cache Locality

ArrayList: элементы рядом в памяти
  → CPU prefetching → L1/L2 cache hits
  → Итерация: очень быстро

HashSet: элементы разбросаны
  → Cache misses при итерации
  → Но O(1) contains компенсирует

LinkedList: узлы в разных концах кучи
  → Cache miss на КАЖДОМ элементе
  → Антипаттерн для современных CPU!

Java 21: SequencedCollection

// Теперь List и Deque наследуют SequencedCollection
SequencedCollection<String> seq = new ArrayList<>();
seq.addFirst("A");   // Новый метод!
seq.addLast("B");    // Новый метод!
seq.getFirst();      // Новый метод!
seq.reversed();      // Отображение в обратном порядке

// Для Set:
SequencedSet<String> seqSet = new LinkedHashSet<>();
// TreeSet тоже поддерживает через NavigableSet

Bloom Filter для огромных Set

// Когда элементов миллиарды, HashSet не влезает в RAM
// Решение: Bloom Filter (сторонняя структура данных, не входит в JCF)
// «False positive» = фильтр может сказать «элемент возможно есть» когда его на самом деле нет.
// Но «false negative» невозможен: если фильтр говорит «элемента нет» — он точно отсутствует.

BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(),
    expectedInsertions,
    falsePositiveRate
);

// O(1) поиск, минимальная память
// Но: возможны false positives (нет false negatives)

Production Experience

Реальный сценарий: HashSet vs ArrayList для contains

// ❌ O(n) поиск в списке из 1 млн элементов
List<String> blacklist = List.of("bad1", "bad2", ...);
if (blacklist.contains(input)) { ... }  // Медленно!

// ✅ O(1) поиск
Set<String> blacklist = Set.of("bad1", "bad2", ...);
if (blacklist.contains(input)) { ... }  // Быстро!

Best Practices

  1. List → ArrayList по умолчанию
  2. Set → HashSet для уникальности, TreeSet для сортировки
  3. Queue → ArrayDeque для стека/очереди
  4. Concurrency → ConcurrentHashMap.newKeySet() для Set
  5. Память → ArrayList компактнее Set
  6. Cache Locality → ArrayList > LinkedList
  7. Java 21 → SequencedCollection для общего интерфейса

Резюме для Senior

  • List = индексация, порядок, кэш-локальность
  • Set = уникальность, O(1) contains (HashSet)
  • Queue = FIFO/LIFO, backpressure (Bounded)
  • Память: ArrayList < HashSet < TreeSet
  • Cache Locality: ArrayList » LinkedList
  • Concurrency: CopyOnWriteArrayList, ConcurrentHashMap.newKeySet()
  • Bloom Filter для огромных множеств
  • Java 21 → SequencedCollection унифицирует API

🎯 Шпаргалка для интервью

Обязательно знать:

  • List = порядок + дубликаты + доступ по индексу (ArrayList O(1) чтение, LinkedList O(n))
  • Set = уникальность через equals()/hashCode(), HashSet = O(1) поиск, TreeSet = O(log n) сортировка
  • Queue = FIFO, методы offer/poll/peek безопаснее add/remove/element
  • HashSet внутри = HashMap<E, Object> с общим PRESENT, ~2x больше памяти чем ArrayList
  • Кэш-локальность: ArrayList » LinkedList — элементы рядом в памяти, CPU prefetching
  • Для concurrency: CopyOnWriteArrayList (много чтений), ConcurrentHashMap.newKeySet() для Set
  • Bloom Filter — для огромных множеств (миллиарды элементов), O(1) поиск, возможны false positives

Частые уточняющие вопросы:

  • Почему HashSet потребляет больше памяти чем ArrayList? — Внутри HashMap.Node (ключ + value + hash + next pointer)
  • Когда использовать TreeSet вместо HashSet? — Когда нужна сортировка, но O(log n) медленнее O(1)
  • Чем offer/poll отличаются от add/remove? — offer/poll возвращают false/null вместо exception
  • Как обеспечить thread-safety для Set? — ConcurrentHashMap.newKeySet() — лучший выбор

Красные флаги (НЕ говорить):

  • ❌ “LinkedList быстрее ArrayList для итерации” — наоборот, кэш-локальность ArrayList даёт преимущество в 10-100 раз
  • ❌ “HashSet гарантирует порядок вставки” — это LinkedHashSet, обычный HashSet не гарантирует порядок
  • ❌ “Для thread-safe Set нужен Collections.synchronizedSet” — ConcurrentHashMap.newKeySet() эффективнее
  • ❌ “Queue и List взаимозаменяемы” — Queue не поддерживает произвольный доступ по индексу

Связанные темы:

  • [[Какие основные интерфейсы Collection Framework]]
  • [[В чём разница между ArrayList и LinkedList]]
  • [[Какова временная сложность операций в ArrayList]]
  • [[Что такое Queue и какие реализации существуют]]