Які операції підтримує інтерфейс Collection

Інтерфейс java.util.Collection є кореневим інтерфейсом для більшості структур даних стандартної бібліотеки Java (розширює java.lang.Iterable). Від нього походять три основ...

🟢 Junior Level

1. Архітектурна роль `Collection`

Інтерфейс java.util.Collection<E> є кореневим інтерфейсом для більшості структур даних стандартної бібліотеки Java (розширює java.lang.Iterable<E>). Від нього походять три основні гілки колекцій: List, Set та Queue (а починаючи з Java 21 — також інтерфейс SequencedCollection).

[!NOTE] Не плутайте інтерфейс Collection (без літери s наприкінці) та утилітарний клас Collections (містить статичні допоміжні методи sort(), synchronizedList(), unmodifiableList()).

                     Iterable<E>
                          │
                    Collection<E>
         ┌────────────────┼────────────────┐
         ▼                ▼                ▼
      List<E>          Set<E>           Queue<E>

2. Базові групи операцій

Усі операції інтерфейсу Collection поділяються на 5 логічних категорій:

Collection<String> coll = new ArrayList<>();

// 1. Одиночна модифікація
coll.add("Alpha");               // true, якщо колекція зазнала змін
coll.remove("Alpha");            // true, якщо елемент було знайдено та видалено

// 2. Запити стану
int count = coll.size();         // Загальна кількість елементів
boolean empty = coll.isEmpty();  // true, якщо size() == 0
boolean has = coll.contains("A");// true, якщо елемент присутній (за equals)

// 3. Пакетні (Bulk) операції
coll.addAll(List.of("A", "B"));  // Об'єднання: додає всі елементи переданої колекції
coll.containsAll(List.of("A"));  // Перевірка: чи містяться ВСІ вказані елементи
coll.removeAll(List.of("A"));    // Різниця: видаляє всі елементи, що входять в аргумент
coll.retainAll(List.of("B"));    // Перетин: залишає ТІЛЬКИ ті елементи, що входять в аргумент
coll.clear();                    // Повне очищення колекції

// 4. Перетворення на масив
Object[] raw = coll.toArray();
String[] typed = coll.toArray(String[]::new); // Java 11+ функціональний стиль

// 5. Функціональні операції (Java 8+)
coll.removeIf(s -> s.length() < 3); // Предикатне лінійне видалення
Stream<String> stream = coll.stream();

🟡 Middle Level

1. Семантика значень мутуючих методів

Усі методи модифікації (add, addAll, remove, removeAll, retainAll) повертають примітивне значення boolean:

Вони повертають true, якщо внаслідок виконання виклику стан або склад колекції змінився.
Вони повертають false, якщо колекція залишилася незмінною (наприклад, при спробі додати дублікат у HashSet: set.add("dup") поверне false, або при спробі видалити елемент, якого не було в колекції).

2. Алгоритмічна катастрофа пакетних операцій: `containsAll` та `removeAll`

Пакетні операції над колекціями (Bulk Operations) часто стають причиною прихованої катастрофічної деградації швидкодії сервісів:

List<String> listA = getMillionItems();     // 1 000 000 елементів
List<String> listB = getTenThousandItems(); // 10 000 елементів

// ❌ КАТАСТРОФА: Складність O(N * M) = 10 000 000 000 операцій порівняння!
listA.removeAll(listB);

Чому це призводить до зависання: В ArrayList реалізація методу removeAll(c) перевіряє кожен елемент listA викликом listB.contains(item). Оскільки в listB (який є ArrayList) метод contains виконує лінійний перебір за $O(M)$, сумарна складність становить $O(N \cdot M)$! Застосунок зависає на хвилини зі 100% завантаженням процесора.

Оптимальне рішення:

// ✅ ПРИСКОРЕННЯ В ТИСЯЧІ РАЗІВ: O(N + M)
Set<String> setB = new HashSet<>(listB); // O(M) хешування
listA.removeAll(setB);                   // O(N) прохід, оскільки contains() у HashSet виконується за O(1)

3. Конвертація в масив: `toArray(new String[0])` проти `toArray(new String[size])`

Класична дискусія серед Java-інженерів: чи передавати масив нульової довжини, чи заздалегідь виділеного точного розміру?

// Варіант 1 (Java 11+): Найбільш чистий та рекомендований
String[] arr = coll.toArray(String[]::new);

// Варіант 2: Передача порожнього масиву
String[] arr = coll.toArray(new String[0]);

// Варіант 3: Заздалегідь алокований масив
String[] arr = coll.toArray(new String[coll.size()]);

[!TIP] Згідно з дослідженнями продуктивності інженерів JVM (зокрема Олексія Шипільова), варіант new String[0] у сучасних версіях HotSpot JVM працює швидше або так само швидко, як попередньо алокований new String[size].

Причина: При створенні new String[size] віртуальна машина зобов’язана спочатку примусово заповнити пам’ять нулями (zero-fill), а потім перезаписати її реальними даними списку. У варіанті new String[0] виділення кінцевого масиву відбувається всередині вбудованого машинного коду (C++ HotSpot intrinsics) одразу потрібного розміру без подвійної ініціалізації пам’яті.

🔴 Senior Level

1. Архітектура Stream API та метадані `Spliterator`

У Java 8 інтерфейс Collection отримав default-методи stream() та parallelStream(), побудовані на базі Spliterator (сплітератора — ітератора з підтримкою паралельного розбиття діапазонів):

Spliterator<E> spliterator = collection.spliterator();

Spliterator передає ядру Stream API бітові прапорці характеристик конкретної колекції:

SIZED: точний розмір колекції заздалегідь відомий (size()). Дозволяє виклику Stream.count() виконатися миттєво за $O(1)$ без повного проходу.
DISTINCT: колекція містить виключно унікальні елементи (наприклад, Set). Операція stream.distinct() стає «безкоштовною» (No-Op).
SORTED: елементи відсортовані за компаратором або natural order (TreeSet). Операція stream.sorted() автоматично оминається.
CONCURRENT: колекція підтримує безпечну конкурентну модифікацію без блокувань (ConcurrentHashMap.keySet()).

2. Чому в інтерфейсі `Collection` немає методу `get(int index)`?

Класичне архітектурне питання: чому метод get(int index) визначений в List, але відсутній у базовому Collection?

Причина — принцип розділення інтерфейсів (ISP) та принцип підстановки Лісков (LSP): Collection узагальнює як індексовані списки (List), так і невпорядковані множини (Set), і черги з доступом виключно до першого елемента (Queue).

У хеш-таблицях (HashSet) або деревах (TreeSet) концепція числового індексу не має фізичного змісту.
Якби Collection оголошував метод get(int), реалізаціям типу HashSet довелося б або емулювати його за катастрофічні $O(N)$ (крокуючи ітератором $i$ разів), або викидати UnsupportedOperationException, що було б прямим порушенням контракту підтипу.

🎯 Шпаргалка для інтерв’ю

30-секундна відповідь (Elevator Pitch)

«Інтерфейс Collection<E> — це фундамент і кореневий контракт Java Collections Framework для List, Set та Queue. Він декларує базові операції додавання й видалення (add, remove), фільтрацію за предикатом (removeIf), пакетні операції над наборами (addAll, removeAll, retainAll), перевірку стану (contains, isEmpty, size), експорт у масив (toArray(T[]::new)) та формування потоків даних (stream(), spliterator()). Метод індексного доступу get(int) навмисно винесено в List, щоб не порушувати принципи ISP та LSP для невпорядкованих множин і черг».

3 каверзних запитання з інтерв’ю та відповіді

1. Що повертає метод `retainAll(Collection<?> c)` і який його математичний сенс?

Відповідь: Метод retainAll(c) реалізує операцію перетину множин ($A \cap B$): він видаляє з поточної колекції всі ті елементи, які НЕ містяться в переданій колекції c. Метод повертає true, якщо внаслідок виклику з поточної колекції було видалено хоча б один елемент (тобто її внутрішній стан змінився), і false, якщо колекція залишилася абсолютно ідентичною.

2. Чому виклик `list.removeAll(otherList)` може спричинити збій сервісу в Production і як цьому запобігти?

Відповідь: Якщо обидві колекції є списками на основі масиву (ArrayList), складність операції removeAll становить $O(N \cdot M)$, оскільки для кожного з $N$ елементів базового списку викликається лінійний пошук $O(M)$ методом contains() у переданому списку. За розмірів $N = 100\,000$ і $M = 100\,000$ це потребуватиме 10 мільярдів порівнянь. Вирішення: перед викликом перетворити другий аргумент у HashSet: list.removeAll(new HashSet<>(otherList)), що знижує обчислювальну складність до лінійної $O(N + M)$.

3. Як влаштований метод `Collection.removeIf(Predicate)` за замовчуванням в інтерфейсі `Collection`?

Відповідь: В інтерфейсі Collection метод removeIf має базову default-реалізацію на основі стандартного ітератора:

default boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while (each.hasNext()) {
        if (filter.test(each.next())) {
            each.remove();
            removed = true;
        }
    }
    return removed;
}

Проте конкретні класи (зокрема ArrayList) повністю перевизначають його на високоефективний однопрохідний алгоритм компактифікації масиву з мінімальною кількістю записів у пам’ять.

Типові помилки та Red Flags

❌ Плутанина між Collection та Collections: Collection — це інтерфейс, а Collections — утилітарний клас зі статичними методами.
❌ Використання пакетних операцій (removeAll, containsAll) з двома ArrayList на великих обсягах даних: Призводить до прихованої квадратичної деградації швидкодії $O(N \cdot M)$.
❌ Твердження, що toArray(new String[coll.size()]) завжди швидший за toArray(new String[0]): На сучасних версіях JVM new String[0] працює швидше завдяки відсутності обов’язкового zero-fill заповнення пам’яті.
❌ Очікування наявності методу get(index) у кореневому Collection: Індексація існує лише в інтерфейсі List.

🟢 Junior Level

1. Архітектурна роль Collection

2. Базові групи операцій

🟡 Middle Level

1. Семантика значень мутуючих методів

2. Алгоритмічна катастрофа пакетних операцій: containsAll та removeAll

3. Конвертація в масив: toArray(new String[0]) проти toArray(new String[size])

🔴 Senior Level

1. Архітектура Stream API та метадані Spliterator

2. Чому в інтерфейсі Collection немає методу get(int index)?