Що таке Map і які реалізації існують?
4. TreeMap — сортування/діапазони 5. ConcurrentHashMap — багатопотоковість 6. Map.of() — для статичних довідників 7. Immutable ключі — обов'язково! 8. computeIfAbsent/merge — ат...
🟢 Junior Level
Map (Словник) — колекція пар ключ-значення.
Аналогія: Map — як паперовий словник: за словом (ключем) ви знаходите визначення (значення). Ключ унікальний (одне слово у словнику лише один раз), значення може повторюватися (у різних слів одне визначення).
Map<String, Integer> ages = new HashMap<>();
ages.put("Ivan", 25); // Покласти
ages.put("Maria", 30);
int age = ages.get("Ivan"); // Отримати → 25
boolean has = ages.containsKey("Ivan"); // → true
Основні реалізації:
| Реалізація | Коли використовувати |
|---|---|
| HashMap | За замовчуванням (швидка) |
| LinkedHashMap | Потрібен порядок |
| TreeMap | Потрібне сортування |
| ConcurrentHashMap | Багатопотоковість |
Map ≠ Collection!
- Map працює з ПАРАМИ (ключ-значення)
- Collection працює з ОДИНОЧНИМИ елементами
🟡 Middle Level
Основні реалізації
HashMap:
Map<String, Integer> map = new HashMap<>();
map.put("A", 1); // O(1)
map.get("A"); // O(1)
// → Швидка, без порядку
LinkedHashMap:
Map<String, Integer> map = new LinkedHashMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);
// → Порядок: C, A, B (як додали)
TreeMap:
Map<String, Integer> map = new TreeMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);
// → Порядок: A, B, C (відсортовано)
// → floorKey, ceilingKey, subMap
Спеціалізовані Map
EnumMap:
// Для Enum ключів — найшвидший! Всередині масив — індекс = enum.ordinal(), без хешування та колізій. Пряма індексація = O(1) без накладних витрат.
enum Status { ACTIVE, INACTIVE }
Map<Status, String> map = new EnumMap<>(Status.class);
// → Всередині: масив! O(1), мінімум пам'яті
WeakHashMap:
// Ключі = слабкі посилання
// Видаляється, коли на ключ немає сильних посилань
Map<Object, String> map = new WeakHashMap<>();
// → Для кешів та метаданих
IdentityHashMap:
// Порівняння за == (адресою), не equals
Map<String, String> map = new IdentityHashMap<>();
map.put(new String("A"), "1");
map.put(new String("A"), "2"); // Два різних ключа!
// → Для серіалізації, пошуку циклів
Java 9+ незмінювані Map
// Фабричні методи
Map<String, Integer> map = Map.of(
"A", 1,
"B", 2,
"C", 3
);
// → Не можна змінити!
// → Компактна пам'ять
// → Порядок рандомізований!
// Обмеження Map.of(): максимум 10 пар, null ключі/значення заборонені. При > 10 пар — використовуйте Map.ofEntries().
Java 8+ корисні методи
map.computeIfAbsent(key, k -> new ArrayList<>())
.add(value);
map.merge(key, 1, Integer::sum); // Лічильник
map.putIfAbsent(key, value);
🔴 Senior Level
Java 21: SequencedMap
// LinkedHashMap та TreeMap → SequencedMap
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.putFirst("A", 1); // Новий метод!
map.putLast("Z", 26); // Новий метод!
map.firstEntry(); // Новий метод!
map.reversed(); // Зворотний порядок (view)
// HashMap НЕ SequencedMap (немає порядку)
Memory Footprint
HashMap Entry: ~32-48 байт
→ Node: hash, key, value, next
LinkedHashMap: ~48 байт
→ + before, after посилання
TreeMap: ~40-56 байт
→ Entry: key, value, left, right, parent, color
→ Для мільйонів записів → гігабайти!
Load Factor trade-off
Load Factor (коефіцієнт заповнення) = відношення числа елементів до числа корзин. При load factor 0.75 та мапі на 100 елементів — 133 корзини. При заповненні > 75% — resize (перестворення таблиці).
За замовчуванням: 0.75
0.75 = баланс між:
→ Пам'ять (менше → більше заповнення)
→ Колізії (більше → повільніший пошук)
Збільшити (0.9):
→ -20% пам'яті
→ +колізії
Зменшити (0.5):
→ +50% пам'яті
→ -колізії
IdentityHashMap use cases
// 1. Пошук циклів у графі об'єктів
IdentityHashMap<Object, Boolean> visited = new IdentityHashMap<>();
// 2. Серіалізація (облік вже серіалізованих)
IdentityHashMap<Object, Integer> serialized = new IdentityHashMap<>();
// 3. Коли equals перевизначений, але потрібен identity
EnumMap: чому найшвидший?
// Всередині: Object[] array
// Індекс = ordinal() enum
// put(key, value):
array[key.ordinal()] = value; // O(1), пряма індексація!
// get(key):
return array[key.ordinal()]; // O(1), без хешування!
→ Швидший за HashMap, менше пам'яті
Highload аспекти
HashMap:
→ Treeification при колізіях (> 8)
→ Resize: O(n), сплеск latency
→ Memory: ~32 байти на entry
ConcurrentHashMap:
→ Lock-free читання
→ CAS + synchronized на корзину
→ Нульові затримки для читань
Production Experience
Реальний сценарій: HashMap → EnumMap
// Було: HashMap<Status, Counter>
// 100,000 запитів/сек → GC pressure
// Стало: EnumMap<Status, Counter>
// → -40% пам'яті
// → +25% throughput
Best Practices
- HashMap — за замовчуванням
- EnumMap — для Enum ключів
- LinkedHashMap — порядок або LRU
- TreeMap — сортування/діапазони
- ConcurrentHashMap — багатопотоковість
- Map.of() — для статичних довідників
- Immutable ключі — обов’язково!
- computeIfAbsent/merge — атомарні операції
Резюме для Senior
- Map ≠ Collection (пари vs одиночні)
- SequencedMap (Java 21) → putFirst/reversed
- EnumMap = масив → найшвидший
- IdentityHashMap = порівняння за ==
- Load Factor = пам’ять vs колізії trade-off
- computeIfAbsent/merge — атомарні Java 8+
- Immutable ключі — критично!
- Map.of() → компактні незмінювані
🎯 Шпаргалка для інтерв’ю
Обов’язково знати:
- Map — колекція пар ключ-значення, ключі унікальні, Map ≠ Collection
- HashMap = O(1), за замовчуванням; LinkedHashMap = O(1) + порядок вставки; TreeMap = O(log n) + сортування; ConcurrentHashMap = thread-safe
- EnumMap — найшвидший Map (всередині масив, індекс = ordinal), для enum-ключів
- WeakHashMap — ключі видаляються автоматично за відсутності сильних посилань (для метаданих, НЕ для кешів)
- IdentityHashMap — порівняння за == замість equals (для серіалізації, пошуку циклів)
- Load factor 0.75 — баланс між пам’яттю та колізіями
- Java 21: SequencedMap API (putFirst, putLast, reversed) для LinkedHashMap та TreeMap
- Java 8+: computeIfAbsent, merge, putIfAbsent — атомарні операції
- Map.of() — незмінювані Map, максимум 10 пар, null заборонені
Часті уточнюючі запитання:
- Чому EnumMap найшвидший? — Всередині масив, пряма індексація за ordinal(), без хешування та колізій — O(1) з мінімальним оверхедом.
- Чим WeakHashMap відрізняється від звичайного Map для кешу? — WeakHashMap видаляє записи при КОЖНОМУ Minor GC — кеш може зникнути через мілісекунди. Для кешів краще Caffeine або SoftReference.
- Коли використовувати IdentityHashMap? — Коли потрібне порівняння за посиланням (==), а не за equals: серіалізація, пошук циклів у графі об’єктів.
- Що таке SequencedMap? — Java 21 інтерфейс для упорядкованих Map: putFirst, putLast, firstEntry, reversed.
Червоні прапорці (НЕ говорити):
- ❌ «Map — це Collection» — Map НЕ розширює Collection, працює з парами ключ-значення
- ❌ «WeakHashMap — хороший вибір для кешу» — надто агресивне очищення, використовуйте Caffeine
- ❌ «IdentityHashMap те саме, що HashMap» — IdentityHashMap порівнює ключі за ==, а не equals
- ❌ «Map.of() можна змінювати» — це незмінювана колекція, UnsupportedOperationException при модифікації
Пов’язані теми:
- [[15. В чому різниця між HashMap, LinkedHashMap та TreeMap]]
- [[17. Що таке WeakHashMap]]
- [[18. Що таке ConcurrentHashMap]]
- [[16. Коли використовувати TreeMap]]