🟢 Junior Level

Хоча HashMap зазвичай працює за O(1) (миттєво), в деяких випадках вона може сповільнитися до O(n) (пропорційно кількості елементів).

Коли це відбувається:

1. Стара Java (до 8-ї версії): Всі колізії зберігаються в списку → O(n)
2. Маленька таблиця (capacity < 64): Навіть при 8 колізіях дерево не створюється
3. Дуже поганий hashCode(): Якщо завжди повертає одне число — все в одному бакеті
4. Перебір всієї мапи: forEach проходить по всіх бакетах, включаючи порожні

Ітерація (forEach) ЗАВЖДИ O(capacity + size) — це не деградація, а штатна поведінка. Окремо: деградація get/put від O(1) до O(n) або O(log n).

Приклад:

// Поганий hashCode — ЗАВЖДИ повертає 1
class BadKey {
    @Override public int hashCode() { return 1; }
}
// Всі елементи в одному бакеті → пошук як у списку → O(n)

🟡 Middle Level

Сценарії O(n) деградації

Сценарій	Опис	Рішення
Java 7	Немає treeification, всі колізії — список	Оновити Java
capacity < 64 + поганий hashCode	Treeification не спрацьовує	Виправити hashCode() ключа
hashCode = константа	Всі елементи в одному бакеті	Виправити hashCode()
Ітерація	Прохід по всіх бакетах	Не створювати величезний capacity
Hash Flooding Attack	Зловмисник підбирає ключі	Java 8+ захищає

Детальний розбір: capacity < 64

HashMap<BadKey, String> map = new HashMap<>(); // capacity = 16, threshold = 12
// 8 елементів < threshold(12) → resize НЕ відбувається
// Treeification не спрацьовує: capacity(16) < 64
// При 13-му елементі → resize до 32 → все ще < 64 → дерево НЕ створюється
// При 25-му елементі → resize до 64 → тепер >= 64 → treeification спрацьовує

Ітерація: O(capacity + size)

HashMap<String, Integer> map = new HashMap<>(1_000_000);
map.put("one", 1);
// Ітерація: проходить 1,000,000 бакетів, з яких 1 заповнений
// Складність: O(1,000,001) ≈ O(n)!

Рішення: Не завищуйте capacity без необхідності.

Hash Flooding Attack

Зловмисник підбирає ключі з однаковим хешем:

• Java 7: O(n²) при вставці n елементів → DoS
• Java 8+: O(n log n) — пом’якшено, але overhead залишається

Типові помилки

1. Не оновлювати Java — Java 7 уразлива до DoS через HashMap
2. Завищений capacity — повільна ітерація
3. Ігнорувати hashCode — ключі-об’єкти з поганим розподілом

🔴 Senior Level

Internal Mechanics: MIN_TREEIFY_CAPACITY

static final int MIN_TREEIFY_CAPACITY = 64;

Цей поріг означає, що для capacity < 64 HashMap воліє resize замість treeification. В цей момент переповнений бакет залишається списком → O(n).

Чому Java 7 була уразлива

В Java 7 при Hash Flooding:

// Зловмисник надсилає POST з 10,000 параметрів з однаковим хешем
// Tomcat створює HashMap для параметрів
// Вставка 10,000 елементів в один бакет: 10,000² = 100,000,000 порівнянь
// CPU: 100% → сервер не відповідає = DoS

CVE-2012-2743 — відома уразливість.

Edge Case: Comparable і treeification

Якщо ключі не реалізують Comparable:

// HashMap використовує tieBreakOrder():
static int tieBreakOrder(Object a, Object b) {
    return (System.identityHashCode(a) <= System.identityHashCode(b)) ? -1 : 1;
}

Це створює дерево, але з overhead — балансування менш ефективне.

O(n) при ітерації: глибокий аналіз

for (Map.Entry<K, V> entry : map.entrySet()) { ... }

Ітератор проходить:

for (int i = index; i < table.length; ++i) {
    // Пропускає порожні бакети
}

Кожен порожній бакет — це одна перевірка. При capacity=1M і size=10 — 999,990 “порожніх” ітерацій.

Production Impact

В API-gateway з мільйонними capacity і малим size:

• Ітерація для логування: 5-10ms замість очікуваних 0.1ms
• В aggregate: значний overhead при частих викликах

Mitigation Strategies

1. Актуальна Java (17+) — treeification + security fixes
2. Правильний hashCode — unit-тести на розподіл
3. Адекватний capacity — формула (expected / 0.75) + 1
4. ConcurrentHashMap — для багатопотокового середовища, також захищений

Benchmark: O(n) vs O(log n)

При 1024 колізіях в одному бакеті:

• O(n) = 1024 порівняння ≈ 5 µs
• O(log n) = 10 порівнянь ≈ 0.1 µs
• Різниця: 50x

---

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

Обов’язково знати:

• Ітерація (forEach) ЗАВЖДИ O(capacity + size) — це штатна поведінка, НЕ деградація
• Деградація get/put: O(1) → O(n) при capacity < 64 + поганий hashCode (дерево не створюється)
• Деградація get/put: O(1) → O(log n) при treeification (Java 8+, capacity >= 64)
• Java 7: O(n) при колізіях, уразлива до Hash Flooding DoS (CVE-2012-2743)
• При 1024 колізіях: O(n) = 1024 порівняння vs O(log n) = 10 — різниця 50x
• Hash Flooding Attack: зловмисник підбирає ключі → DoS; Java 8+ пом’якшила через treeification

Часті уточнюючі запитання:

• Чому capacity < 64 блокує treeification? — HashMap воліє resize: він рознесе елементи
• Коли O(n) можливе в Java 8+? — при capacity < 64 + 8+ колізій, або hashCode = константа
• Що таке tieBreakOrder? — fallback для дерева коли ключі не Comparable, використовує System.identityHashCode
• Як захиститися від Hash Flooding? — Java 8+ автоматично через treeification; слідкуйте за якістю hashCode

Червоні прапорці (НЕ говорити):

• «forEach деградує до O(n)» — ні, це штатна складність O(capacity + size)
• «Збільшення capacity вирішує колізії» — ні, вирішує виправлення hashCode
• «Java 8 повністю захищена від DoS» — ні, overhead від treeification залишається

Пов’язані теми:

• [[20. Яка часова складність операцій get() та put() в HashMap]]
• [[4. Що таке колізія в HashMap]]
• [[6. Що відбувається при досягненні 8 елементів в одному бакеті]]
• [[22. Як HashMap працює в багатопотоковому середовищі]]