🔑 Розділ 10 · Питання #20

Яка часова складність операцій get() та put() в HashMap

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

🔑 HashMap equals hashCode 📄 Вихідний Markdown

🟢 Junior Level

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

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

Чому це працює так швидко:

  1. Миттєвий розрахунок індексу: Числовий геш-код ключа вказує номер бакета (індекс масиву) за 1–2 машинні такти процесора.
  2. Прямий доступ до комірки: Доступ до елемента масиву за індексом table[index] здійснюється миттєво за $O(1)$.
  3. Мінімум порівнянь: При якісному розподілі гешів у бакеті зазвичай знаходиться лише 1 вузол. Значення повертається одразу після швидкої перевірки.
import java.util.HashMap;
import java.util.Map;

public class ComplexityDemo {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();

        // Вставка: O(1) в середньому
        map.put("user_101", "Slava");

        // Пошук: O(1) в середньому
        String name = map.get("user_101");

        // Видалення: O(1) в середньому
        map.remove("user_101");
    }
}

[!NOTE] Аналогія: Уявіть гардероб із пронумерованими номерками від 1 до 1 000 000. Щоб повернути пальто, гардеробник не оглядає всі мільйон вішалок поспіль ($O(N)$) — він одразу йде безпосередньо до вішалки з номером вашого номерка ($O(1)$).

🟡 Middle Level

Зведена таблиця часової складності

Операція Найкращий випадок Середній випадок Найгірший випадок (Java 7) Найгірший випадок (Java 8+)
get() $O(1)$ $O(1)$ $O(N)$ (однозв’язний список) $O(\log N)$ (RB-Tree)*
put() $O(1)$ $O(1)$ амортизоване $O(N)$ $O(\log N)$ (RB-Tree)*
remove() $O(1)$ $O(1)$ $O(N)$ $O(\log N)$ (RB-Tree)*
containsKey() $O(1)$ $O(1)$ $O(N)$ $O(\log N)$ (RB-Tree)*
Ітерація (keySet/entrySet) $O(C + N)$ $O(C + N)$ $O(C + N)$ $O(C + N)$

*Примітка: Найгірший випадок у Java 8+ дорівнює $O(\log N)$ лише за умови, що ключі реалізують інтерфейс Comparable. Якщо ключі не порівнювані, пошук усередині дерева при однакових гешах деградує до $O(N)$.

Амортизована вартість операції put()

Операція put() має амортизовану складність $O(1)$, незважаючи на те, що періодично запускається процедура ресайзу (resize()), яка потребує виділення нового масиву та перенесення всіх елементів ($O(N)$).

Агрегатний аналіз амортизації:

Місткість масиву зростає як геометрична прогресія: $16 \to 32 \to 64 \to \dots \to N$.
При додаванні $N$ елементів сумарна кількість операцій копіювання при всіх проміжних ресайзах становить: \(1 + 2 + 4 + 8 + \dots + \frac{N}{2} = N - 1 \text{ операцій}\) Сумарна вартість виконання серії з $N$ операцій вставки: \(\text{Cost} = N \text{ (базові вставки)} + (N - 1) \text{ (копіювання при resize)} < 2N\) Ділимо загальні витрати на кількість операцій: \(\text{Amortized Cost} = \frac{2N}{N} = O(1)\)

Часова складність ітерації: $O(\text{capacity} + \text{size})$

Час повного обходу колекції (for (Map.Entry<K, V> entry : map.entrySet())) залежить не лише від кількості записів $N$, але й від фізичного розміру масиву бакетів $C$.
Ітератор зобов’язаний послідовно просканувати всі комірки масиву table від $0$ до capacity - 1. Якщо створити new HashMap<>(1_000_000) і покласти туди лише 2 елементи, ітерація буде повільною ($O(1\,000_000)$), оскільки ітератор перевірятиме мільйон порожніх комірок null.

🔴 Senior Level

Потактовий розбір операції get(key) на рівні процесора

Реальна затримка (latency) операції get() складається з таких мікроархітектурних етапів:

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) { // 1 & 2
        if (first.hash == hash && // 3
            ((k = first.key) == key || (key != null && key.equals(k)))) // 4 & 5
            return first;
        // ... обхід ланцюжка / дерева ...
    }
    return null;
}
  1. Гешування ключа (hash(key)): (h = key.hashCode()) ^ (h >>> 16) — 2-3 машинних такти CPU (побітовий зсув та XOR у регістрах за частки наносекунди).
  2. Розрахунок індексу: (n - 1) & hash — 1 машинний такт CPU.
  3. Читання з масиву (tab[index]):
    • L1/L2 Cache Hit: 1–4 нс (якщо комірка знаходиться в кеші процесора).
    • RAM Cache Miss: 60–100 нс (якщо таблиця велика і витіснена з кешу).
  4. Порівняння 32-бітного гешу: first.hash == hash — 1 такт CPU. Миттєво відсікає чужі об’єкти без виклику методу порівняння.
  5. Порівняння за посиланням (first.key == key): 1 такт CPU. Якщо посилання збіглися (наприклад, той самий екземпляр або інтернований рядок), метод equals() не викликається.
  6. Виклик key.equals(k): Для простих класів — 2–5 нс. Для довгих рядків String час залежить від довжини рядка $L$ ($O(L)$), але прискорюється SIMD-інтринсиками процесора (ArraysSupport.mismatch).

Вплив локальності кешу (CPU Cache Locality)

Теоретична асимптотика $O(\log N)$ для червоно-чорного дерева на практиці може працювати відчутно повільніше за теоретичне $O(1)$:

  • Вузли TreeNode створюються в різні моменти часу і хаотично розпорошені по купі (Heap).
  • При переході за вказівниками node.left та node.right кожне розіменування посилання з високою ймовірністю спричиняє апаратний промах кешу процесора (Cache Miss).
  • Пошук в ідеально збалансованому дереві з 15 елементів (4 переходи за посиланнями) може забрати до $4 \times 80 = 320$ нс, тоді як лінійне сканування компактного неперервного масиву з тих самих 15 елементів завдяки апаратному Prefetcher процесора вкладається в 10–15 нс.

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

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

У середньому get, put, remove, containsKey у HashMap виконуються за константний час $O(1)$. У найгіршому випадку (масові колізії) складність становила $O(N)$ у Java 7, але в Java 8+ знижена до $O(\log N)$ завдяки трансформації бакетів у червоно-чорні дерева (якщо ключі реалізують Comparable). Операція put() є амортизованим $O(1)$, оскільки дорогий ресайз ($O(N)$) відбувається геометрично рідко. Ітерація по мапі займає $O(\text{capacity} + \text{size})$.

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

Питання 1: Чи може складність get() у HashMap на Java 8+ стати $O(N)$, незважаючи на впровадження червоно-чорних дерев?

Відповідь: Так, може.
Червоно-чорне дерево гарантує час $O(\log N)$ тільки тоді, коли вузли можна однозначно впорядкувати в бінарному дереві пошуку (BST).
HashMap порівнює ключі з однаковим гешем за допомогою інтерфейсу Comparable<K>. Якщо ключі мають однаковий hashCode() (наприклад, константу 42) і НЕ реалізують інтерфейс Comparable<K> (або метод compareTo повертає 0 для різних об’єктів), алгоритм TreeNode.find() не знає, куди розгалужуватися (ліворуч чи праворуч). Алгоритм змушений рекурсивно сканувати обидві гілки піддерева. Повний обхід усіх вузлів повертає складність до найгіршого випадку $O(N)$.

Питання 2: Чому операція put() класифікується як $O(1)$, якщо окремий виклик під час ресайзу триває $O(N)$?

Відповідь: В алгоритмічному аналізі чітко розрізняють час найгіршого випадку для одиничної операції (Worst-case) та амортизований час послідовності операцій (Amortized time).
Для put() найгірший час однієї операції дійсно $O(N)$ (у момент виділення нового масиву). Проте завдяки подвоєнню місткості ($2 \times$) ресайзи відбуваються експоненційно рідше зі зростанням таблиці. Додавання $N$ елементів сумарно вимагає не більше $2N$ операцій копіювання. Тому середня вартість однієї вставки у довгій послідовності обмежена константою: $\frac{2N}{N} = O(1)$.

Питання 3: Яка часова складність викликів map.size() та map.isEmpty()?

Відповідь: Суворо $O(1)$.
У HashMap поточна кількість елементів зберігається в явному примітивному полі transient int size;.
Метод size() просто повертає значення цього поля за 1 такт процесора, а метод isEmpty() виконує пряму перевірку size == 0. Жодного сканування бакетів чи підрахунку вузлів не відбувається.

Питання 4: Чому ітерація по HashMap може працювати відчутно повільніше, ніж ітерація по ArrayList із тією ж кількістю елементів?

Відповідь: Складність ітерації по ArrayList становить $O(N)$, а елементи розташовані в неперервному блоці пам’яті, що ідеально утилізує кеш-лінії L1/L2 (64 байти за 1 такт).
Складність ітерації по HashMap становить $O(\text{capacity} + N)$:

  1. Пропуск порожніх комірок: Ітератор зобов’язаний послідовно обійти весь масив table.length. Якщо таблиця містить 1 000 елементів у масиві на 65 536 комірок, ітератор виконає 64 536 перевірок на null.
  2. Розпорошеність у пам’яті (Pointer Chasing): Кожен вузол Node — це окремий об’єкт у купі. Перехід за посиланнями next призводить до постійних промахів кешу процесора.

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

❌ «Складність put() завжди строго $O(1)$ без винятків.»
Правильно: Вона є амортизованою $O(1)$, оскільки окремий виклик під час ресайзу триває $O(N)$.

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

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

4. Пов’язані питання