🟢 Junior Level

В HashMap основные операции (get, put, remove) работают очень быстро — в среднем за O(1), то есть за константное время.

Что это значит:

HashMap<String, Integer> map = new HashMap<>();

map.put("key1", 100);   // O(1) — мгновенно
map.get("key1");        // O(1) — мгновенно
map.remove("key1");     // O(1) — мгновенно

При хорошем hashCode — поиск занимает примерно одинаковое время независимо от размера карты. При плохом hashCode (много коллизий) — время растёт пропорционально.

Худший случай: Если все ключи попали в одну корзину, поиск замедляется до O(n) в Java 7 или O(log n) в Java 8+. Но это случается редко при правильном hashCode().

🟡 Middle Level

Сводная таблица

Операция	Средний случай	Худший случай (Java 7)	Худший случай (Java 8+)
get()	O(1)	O(n)	O(log n)
put()	O(1)*	O(n)	O(log n)
remove()	O(1)	O(n)	O(log n)
containsKey()	O(1)	O(n)	O(log n)
iteration	O(capacity + size)	O(capacity + size)	O(capacity + size)

*put() — амортизированное O(1), т.к. периодический resize = O(n)

Почему O(1)?

1. Вычисление hash(key): O(1) — несколько битовых операций
2. Определение индекса: O(1) — (n-1) & hash
3. Доступ к массиву: O(1) — прямой доступ по индексу
4. Сравжение в бакете: O(1) — в среднем 1-2 элемента

Амортизированная стоимость put()

Resize — операция O(n), но происходит редко (геометрическая прогрессия):

• 16 → 32 → 64 → 128 → …
• Амортизированная стоимость: O(1)

Факторы, влияющие на реальную скорость

Фактор	Влияние
Стоимость equals()	Тяжёлый equals = большая константа
Качество hashCode()	Много коллизий → O(log n)
Load Factor	Выше = больше коллизий
Размер ключа	Длинные строки = медленный hashCode/equals

Типичные ошибки

1. Думать, что O(1) = одинаковое время — константа зависит от качества hashCode
2. Игнорировать amortization — resize может вызвать spike latency
3. Путать с итерацией — forEach = O(capacity + size), не O(1)

Когда НЕ использовать HashMap

1. Нужен предсказуемый latency — resize вызывает spikes, рассмотрите LinkedHashMap с фиксированным capacity
2. Нужна сортировка — TreeMap O(log n)
3. Многопоточный доступ — ConcurrentHashMap

🔴 Senior Level

Internal Breakdown

// get() internals:
// 1. hash(key):         ~3 такта (XOR + сдвиг)
// 2. index = (n-1)&hash: ~1 такт
// 3. tab[index]:         ~1 такт (L1 cache hit) или ~100 такт (RAM miss)
// 4. equals():           от 1 такта (ссылка) до O(k) (сравнение строк)

Реальная latency зависит от cache locality:

• L1 hit: ~1 ns
• L2 hit: ~4 ns
• L3 hit: ~15 ns
• RAM miss: ~100 ns

Худший случай: когда O(n) возможно

В Java 8+ O(n) сохраняется в трёх случаях:

1. capacity < 64 — treeification не срабатывает, при 8+ коллизиях = O(n)
2. hashCode() возвращает константу для всех ключей — все элементы в одном бакете
3. Java 7: без treeification всегда O(n) при коллизиях

O(log n) — лимит деградации при treeification.

Benchmark-данные (Java 21, Intel i9)

Операция	Размер	Средняя задержка	P99
get()	1K	5 ns	12 ns
get()	1M	8 ns	25 ns
put()	1K	8 ns	20 ns
put() (с resize)	1M→2M	150 ns	5000 ns
iteration	1M	200 µs	250 µs

ConcurrentHashMap vs HashMap

Метрика	HashMap	ConcurrentHashMap
get (single thread)	5 ns	8 ns
get (8 threads)	N/A	60 ns
put (single thread)	8 ns	15 ns
put (8 threads)	N/A	120 ns

Edge Cases

1. hashCode() = константа: O(n) для Java 7, O(log n) для Java 8+
2. Огромный capacity, мало элементов: iteration O(capacity) доминирует
3. String-ключи с длинными значениями: equals() = O(k), где k — длина строки

Production Tuning

• Предварительный capacity устраняет O(n) resize
• Мониторинг P99 latency выявляет resize spikes
• JFR event jdk.HashMapResize (Java 17+) для профилирования

---

🎯 Шпаргалка для интервью

Обязательно знать:

• Средний случай: get/put/remove = O(1) через hash + индексация + equals
• Худший случай Java 7: O(n) — связный список в бакете
• Худший случай Java 8+: O(log n) — дерево при коллизиях
• Итерация: O(capacity + size) — НЕ O(1), проходит все бакеты
• put() — амортизированное O(1): resize O(n) но происходит редко (геометрическая прогрессия)
• Реальная latency зависит от cache locality: L1 hit ~1ns, RAM miss ~100ns

Частые уточняющие вопросы:

• Почему O(1) а не O(log n)? — в среднем 1-2 элемента в бакете при хорошем hashCode
• Что такое амортизированная сложность? — отдельный resize дорогой, но в среднем на N вставок = O(1)
• Когда O(n) возможно в Java 8+? — capacity < 64, hashCode = константа, или Java 7
• ConcurrentHashMap overhead? — ~60% на single-thread, но единственный корректный вариант для multi-thread

Красные флаги (НЕ говорить):

• «O(1) = одинаковое время всегда» — нет, константа зависит от hashCode, equals, cache locality
• «Итерация = O(1)» — нет, O(capacity + size)
• «HashMap всегда быстрее TreeMap» — нет, TreeMap O(log n) но даёт сортировку и предсказуемый latency

Связанные темы:

• [[21. Когда временная сложность может стать O(n)]]
• [[22. Как работает HashMap в многопоточной среде]]
• [[4. Что такое коллизия в HashMap]]