🟢 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]]