🟢 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 элементов в одном bucket]]
• [[22. Как работает HashMap в многопоточной среде]]