Коли часова складність може стати O(n)

Хоча у штатному режимі HashMap виконує базові операції (get, put, remove) за константний час $O(1)$, за несприятливих умов часова складність може деградувати до лінійної — $O(N)...

🟢 Junior Level

Короткий опис для співбесіди (30 секунд)

Хоча у штатному режимі HashMap виконує базові операції (get, put, remove) за константний час $O(1)$, за несприятливих умов часова складність може деградувати до лінійної — $O(N)$. Це означає, що час виконання операції зростатиме прямо пропорційно кількості збережених записів.

Основні сценарії деградації до $O(N)$:

Неякісна геш-функція: Якщо метод hashCode() у ключів реалізований некоректно (наприклад, повертає одне й те саме число для всіх об’єктів), усі елементи потрапляють в один-єдиний бакет.
Малий розмір таблиці (capacity < 64): Навіть якщо в одному бакеті накопичилося 8 колізій, червоно-чорне дерево не створюється, доки загальна місткість таблиці менша за 64. Елементи залишаються у зв’язному списку, пошук за яким триває $O(N)$.
Ключі без інтерфейсу Comparable (у дереві колізій): Якщо при збігу гешів ключі не реалізують Comparable, пошук у червоно-чорному дереві змушений рекурсивно обходити обидві гілки, що вироджується в $O(N)$.
Ітерація по розрідженій таблиці: Повний обхід елементів (forEach, entrySet) завжди потребує часу $O(\text{capacity} + N)$, що при надлишковій місткості призводить до мільйонів порожніх перевірок.

// Катастрофічний приклад: геш-код завжди повертає константу
class BrokenKey {
    private final String id;

    public BrokenKey(String id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return 42; // Усі ключі потраплять в один і той самий бакет!
    }

    @Override
    public boolean equals(Object obj) {
        return (obj instanceof BrokenKey other) && this.id.equals(other.id);
    }
}

[!NOTE] Аналогія: Уявіть картотеку на 100 шухляд. Якщо архіваріус помиляється і складає всі документи в одну єдину папку, то для пошуку потрібного документа доведеться перебрати весь стос паперів аркуш за аркушем ($O(N)$), тоді як решта 99 шухляд безглуздо порожнітимуть.

🟡 Middle Level

Порівняльний аналіз сценаріїв деградації

Сценарій	Причина деградації	Часова складність `get`/`put`	Спосіб усунення
Java 7 (застарілий JDK)	Відсутність дерев; колізії розв’язуються суто списками	$O(N)$	Оновлення до актуальної Java (Java 17/21)
`capacity < 64` при колізіях	Таблиця віддає перевагу `resize()` замість трифікації	$O(N)$ (на етапі зростання)	Якісний `hashCode()`, початковий `capacity >= 64`
Колізії ключів без `Comparable`	Пошук у `TreeNode` не знає напрямку обходу (left/right)	$O(N)$ при однакових гешах	Реалізація `Comparable<T>` у класі ключа
Hash Flooding DoS	Зловмисник цілеспрямовано генерує колізії	$O(N)$ (Java 7) / $O(\log N)$ (Java 8+)	Використання `String` (реалізує `Comparable`)
Ітерація по `entrySet()`	Сканування всіх незаповнених слотів масиву	$O(\text{capacity} + N)$	Задавати `capacity` суворо під очікуваний розмір

Детальний розбір: бар’єр `MIN_TREEIFY_CAPACITY = 64`

У Java 8+ для захисту від деградації до $O(N)$ зв’язний список бакета перетворюється на червоно-чорне дерево (TreeNode) при накопиченні 8 елементів (TREEIFY_THRESHOLD = 8).

Проте трифікація відбувається лише за умови виконання додаткового критерію: $\text{table.length} \ge 64$

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // Замість створення дерева подвоюємо таблицю!
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // Створення червоно-чорного дерева (TreeNode)
    }
}

Якщо створено стандартну new HashMap<>() (початкова місткість 16) із поганими ключами:

8-й елемент в одному бакеті $\to$ ресайз до 32 (список зберігається, $O(N)$).
9-й елемент у тому ж бакеті $\to$ ресайз до 64 (список зберігається, $O(N)$).
Лише після досягнення місткості 64 наступний виклик treeifyBin конвертує бакет у дерево зі складністю пошуку $O(\log N)$.

🔴 Senior Level

Головний міф Java 8+: чому `TreeNode` може деградувати до $O(N)$

Багато розробників упевнені, що починаючи з Java 8 найгірший випадок у HashMap гарантовано становить $O(\log N)$. Це небезпечна омана.

Дослідимо метод пошуку find у класі HashMap.TreeNode:

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> q, pl = p.left, pr = p.right;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr; // Спрямований спуск O(log N)
        else if ((q = pr.find(h, k, kc)) != null) // Увага сюди!
            return q;
        else
            p = pl; // Рекурсивний пошук по обох гілках!
    } while (p != null);
    return null;
}

Механізм деградації:

Якщо в усіх ключів геш-код збігається (ph == h), бінарне дерево не може розгалужуватися за значенням гешу.
HashMap намагається отримати клас порівняння: comparableClassFor(k).
Якщо ключ НЕ реалізує Comparable<K>:
- Метод не може визначити напрямок спуску (dir невідомий).
- Алгоритм запускає рекурсивний пошук у правому піддереві: pr.find(h, k, kc).
- Якщо шуканий елемент там не знайдено, він спускається лівим піддеревом: p = pl.
- Результат: Відбувається повний рекурсивний обхід усіх вершин бінарного дерева пошуку (Full Tree Traversal). Пошук відсутнього ключа обходить кожен вузол, деградуючи рівно до $O(N)$!

Атака Hash Flooding (DoS) та вразливість CVE-2011-4858

Наприкінці 2011 року інженери з кібербезпеки продемонстрували практичну атаку на веб-сервери (Tomcat, Jetty, PHP, Node.js).
Зловмисник надсилав один спеціально скомпільований HTTP POST-запит із десятками тисяч параметрів форми, чиї рядкові назви генерували однаковий hashCode() (наприклад, "AaAa", "BBBB", "AaBB").

У Java 7:

Сервер поміщав параметри в HashMap<String, String>.
Усі $N$ параметрів потрапляли в один бакет у вигляді однозв’язного списку.
Для вставки кожного нового параметра метод put сканував увесь ланцюжок наявних елементів для перевірки equals().
Сумарна складність збереження $N$ параметрів становила: $\sum_{i=1}^{N} i = \frac{N(N-1)}{2} = O(N^2)$
Запит із 50 000 параметрів на 100% навантажував ядро процесора на 5–10 хвилин, блокуючи сервер (Denial of Service).

У Java 8+ клас String реалізує Comparable<String>. При колізіях бакет перетворюється на збалансоване дерево, а пошук та вставка виконуються за $O(N \log N)$ замість $O(N^2)$, що повністю нейтралізує катастрофічний ефект атаки.

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

1. 30-секундний есенс (Elevator Pitch)

Складність операцій у HashMap стає $O(N)$ у таких випадках: при патологічній реалізації hashCode() (усі ключі потрапляють в один бакет) за умови, що ключі не реалізують інтерфейс Comparable (дерево вироджується в рекурсивний перебір обох гілок); при малій місткості таблиці (capacity < 64), де замість дерева викликається resize(); у застарілій Java 7, де дерев не було взагалі; а також під час разової вставки при спрацьовуванні ресайзу.

2. 4 каверзні питання з глибокими відповідями

Питання 1: Якщо розробник написав клас ключа з фіксованим `hashCode() { return 1; }`, але забув реалізувати `Comparable`, якою буде часова складність `map.get()` при 1 000 000 елементів у Java 21?

Відповідь: Складність буде суворо $O(N)$.
Оскільки геш-коди ідентичні, всі елементи потраплять в один бакет. Таблиця перевищить поріг 64 і перетвориться на TreeNode. Проте під час виклику get() метод TreeNode.find не зможе викликати compareTo(). Йому доведеться рекурсивно обходити і ліве, і праве піддерево кожного вузла. У найгіршому сценарії (пошук відсутнього ключа) JVM перевірить усі 1 000 000 вузлів, що триватиме лінійний час $O(N)$.

Питання 2: Чому операція `put()` у `HashMap` без колізій може раптово виконатися за $O(N)$ часу?

Відповідь: Це трапляється в момент спрацьовування процедури resize().
Коли поточна кількість елементів size перевищує threshold (наприклад, при вставці 13-го елемента в таблицю місткістю 16), HashMap алокує новий масив подвоєного розміру і переносить туди всі $N$ наявних елементів. Хоча амортизована складність послідовності операцій дорівнює $O(1)$, поодинокий конкретний виклик put() у момент ресайзу займає лінійний час $O(N)$.

Питання 3: Чи є складність ітерації `map.keySet()` на рівні $O(N)$ деградацією?

Відповідь: Ні, це штатна поведінка структури даних.
Складність ітератора HashMap описується як $O(\text{capacity} + N)$. Ітератор змушений послідовно перебирати весь внутрішній масив table. Якщо в таблиці місткістю 1 000 000 зберігається лише 5 елементів, ітератор виконає 1 000 000 перевірок на null, що пропорційно розміру масиву ($O(C)$), а не кількості елементів. Для сценаріїв із частою ітерацією по розріджених даних слід використовувати LinkedHashMap, де підтримується неперервний двозв’язний список елементів зі складністю обходу строго $O(N)$.

Питання 4: Навіщо в методі `treeifyBin` при колізії з 8 елементів перевіряється умова `tab.length < 64` замість негайного створення дерева?

Відповідь: Створення червоно-чорного дерева — дорога операція:

TreeNode займає 56–64 байти пам’яті (замість 32 байтів у стандартного Node).
Побудова дерева вимагає алокації нових об’єктів та ребалансування (обертання, перефарбовування).
Якщо загальний розмір таблиці малий ($< 64$), поява 8 елементів в одному бакеті зазвичай спричинена випадковим збігом при малій кількості комірок. Виклик resize() подвоює місткість і додає 1 біт до маски індексування (n - 1) & hash, що з імовірністю $\approx 50\%$ розділяє накопичені елементи по двох різних бакетах без зайвих витрат пам’яті на TreeNode.

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

❌ «У Java 8+ складність ніколи не деградує до $O(N)$, оскільки є червоно-чорні дерева.»
Правильно: Якщо ключі не реалізують Comparable, пошук у дереві перетворюється на повний рекурсивний перебір обох піддерев зі складністю $O(N)$.

❌ «Ітерація keySet() завжди виконується за $O(N)$.»
Правильно: Вона виконується за $O(\text{capacity} + N)$, оскільки сканує весь масив бакетів.

❌ «Поява 8 елементів у бакеті гарантовано перетворює його на дерево.»
Правильно: Якщо загальний розмір таблиці менший за 64, замість дерева викликається resize().