Що таке Map і які реалізації існують

Інтерфейс Map (словник, асоціативний масив) представляє структуру даних, яка зберігає пари «ключ — значення» (Key-Value pairs):

🟢 Junior Level

1. Що таке Map

Інтерфейс Map<K, V> (словник, асоціативний масив) представляє структуру даних, яка зберігає пари «ключ — значення» (Key-Value pairs):

Ключі (K) мають бути строго унікальними. Спроба додати вже наявний ключ перезаписує попереднє значення.
Значення (V) можуть повторюватися і дублюватися.
Кожному ключу відповідає рівно одне значення.

Map<String, Integer> salaries = new HashMap<>();
salaries.put("Олексій", 120_000);
salaries.put("Марія", 150_000);

// Отримання значення за ключем:
Integer alexSalary = salaries.get("Олексій"); // 120000

// Перевірка наявності:
boolean hasMaria = salaries.containsKey("Марія"); // true

2. Чому `Map` НЕ успадковує `Collection`?

Це одне з найпоширеніших запитань на співбесідах. Map не є частиною ієрархії Collection через принципові архітектурні відмінності:

Різна семантика елементів: Collection<E> керує колекцією одиночних сутностей (add(E e), iterator()), тоді як Map<K, V> оперує парами двох різних типів із роздільним доступом до ключів та значень (put(K, V)).
Проєкції (Views): замість прямої ітерації Map надає три різні колекційні представлення:
- keySet() $\to$ Set<K> (множина унікальних ключів).
- values() $\to$ Collection<V> (колекція неунікальних значень).
- entrySet() $\to$ Set<Map.Entry<K, V>> (множина пар «ключ-значення»).

3. Зведена таблиця основних реалізацій `Map`

Клас	Порядок ключів	Складність (`get`/`put`)	Підтримка `null`	Потокобезпечність	Основне призначення
`HashMap`	Не гарантований	$O(1)$ у середньому	Key: ✅ (один), Val: ✅	❌ Ні	Базова реалізація за замовчуванням
`LinkedHashMap`	Порядок вставки або доступу	$O(1)$ у середньому	Key: ✅ (один), Val: ✅	❌ Ні	Передбачуваний порядок, побудова LRU-кешу
`TreeMap`	Відсортований (Comparable/Comparator)	$O(\log N)$	Key: ❌ (NPE), Val: ✅	❌ Ні	Навігація діапазонами, сортування ключів
`ConcurrentHashMap`	Не гарантований	$O(1)$ у середньому	Key: ❌, Val: ❌	✅ Так	Високонавантажене багатопотокове середовище
`EnumMap`	Порядок оголошення enum	$O(1)$ (прямий масив)	Key: ❌, Val: ✅	❌ Ні	Ключі типу `enum` (максимальна швидкодія)
`WeakHashMap`	Не гарантований	$O(1)$ у середньому	Key: ✅, Val: ✅	❌ Ні	Допоміжні метадані для GC
`IdentityHashMap`	Не гарантований (порівняння за `==`)	$O(1)$ у середньому	Key: ✅, Val: ✅	❌ Ні	Серіалізація, обхід графів із циклами

🟡 Middle Level

1. Спеціалізовані реалізації: `EnumMap`, `IdentityHashMap`, `WeakHashMap`

`EnumMap`: максимальна продуктивність

Якщо ключами виступають елементи перерахування (enum), використання HashMap вважається антипатерном. EnumMap всередині влаштований як звичайний масив фіксованого розміру:

enum TaskPriority { LOW, MEDIUM, HIGH, URGENT }

Map<TaskPriority, String> tasks = new EnumMap<>(TaskPriority.class);
tasks.put(TaskPriority.HIGH, "Виправити баг у проді");

Чому це швидше за HashMap: Індексом у масиві слугує числовий порядковий номер enum.ordinal(). Жодного обчислення hashCode(), жодних колізій, зв’язних списків чи дерев. Це прямий доступ до комірки масиву за 1 машинний такт.

`IdentityHashMap`: рівність за посиланням (`==`)

На відміну від усіх інших мап, IdentityHashMap повністю ігнорує equals() та hashCode(). Два ключі k1 та k2 вважаються однаковими виключно тоді, коли k1 == k2.

Всередині використовується відкрита адресація в пласкому масиві Object[] table, де ключі та значення чергуються (table[i] = key, table[i+1] = value).
Застосовується в бібліотеках серіалізації (Jackson, Kryo) та глибокого копіювання для обліку вже оброблених об’єктів та уникнення зациклення при циклічних графах.

`WeakHashMap`: ключі зі слабкими посиланнями

Ключі огортаються у WeakReference. Якщо на об’єкт-ключ більше немає сильних посилань (StrongReference) у всьому застосунку, збирач сміття видаляє ключ, а запис у WeakHashMap автоматично вичищається при наступних зверненнях до мапи.

2. Функціональний API в Java 8+

Java 8 суттєво спростила роботу з Map, додавши декларативні методи на основі лямбда-виразів:

Map<String, List<String>> userRoles = new HashMap<>();

// computeIfAbsent: створює та вставляє список, лише якщо ключ відсутній:
userRoles.computeIfAbsent("ivan", k -> new ArrayList<>()).add("ROLE_USER");

// merge: ідеально для лічильників та агрегацій:
Map<String, Integer> wordCount = new HashMap<>();
String word = "java";
wordCount.merge(word, 1, Integer::sum); // якщо немає -> 1, якщо є -> старе + 1

// getOrDefault: надійне запобігання NPE:
int count = wordCount.getOrDefault("unknown", 0);

3. Незмінні фабричні методи (Java 9+)

Методи Map.of() та Map.ofEntries() повертають оптимізовані компактні незмінні реалізації:

// До 10 пар ключ-значення:
Map<String, String> config = Map.of(
    "env", "production",
    "timeout", "5000"
);

// Більше 10 пар:
Map<Integer, String> codes = Map.ofEntries(
    Map.entry(200, "OK"),
    Map.entry(404, "Not Found"),
    Map.entry(500, "Internal Server Error")
);

Критичні властивості:

Суворо забороняють null як для ключів, так і для значень (викидають NullPointerException).
Споживають у 2–3 рази менше пам’яті, ніж HashMap, оскільки позбавлені важких об’єктів-вузлів Node<K,V>.
Ітераційний порядок ключів навмисно рандомізується при кожному запуску JVM, щоб розробники не покладалися на випадкову впорядкованість.

🔴 Senior Level

1. Архітектурна еволюція в Java 21: `SequencedMap`

До Java 21 у стандартній бібліотеці був відсутній спільний інтерфейс для карт із гарантованим порядком ітерації. У Java 21 представлено інтерфейс SequencedMap<K, V>:

          ┌─────────────────┐
          │   Map<K, V>     │
          └────────┬────────┘
                   │ extends
          ┌────────┴────────┐
          │ SequencedMap    │
          └───┬─────────┬───┘
              │         │
     implements         implements
              │         │
    ┌──────────┴──┐   ┌──┴───────────┐
    │LinkedHashMap│   │ NavigableMap │
    └─────────────┘   └──┬───────────┘
                         │ implements
                      ┌──┴───────────┐
                      │   TreeMap    │
                      └──────────────┘

SequencedMap стандартизує методи:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putFirst("A", 1);
map.putLast("Z", 26);

Map.Entry<String, Integer> first = map.firstEntry(); // "A" -> 1
Map.Entry<String, Integer> last = map.lastEntry();   // "Z" -> 26

// Реверсивне представлення карти без копіювання (View) за O(1):
SequencedMap<String, Integer> reversedMap = map.reversed();

HashMap не реалізує SequencedMap, оскільки не гарантує жодного порядку обходу елементів.

2. Побудова LRU-кешу через `LinkedHashMap`

Клас LinkedHashMap містить убудовану підтримку витіснення застарілих записів (Least Recently Used Cache) через спеціальний конструктор та метод removeEldestEntry:

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LruCache(int capacity) {
        // accessOrder = true: порядок елементів перебудовується при ЧИТАННІ (get/put)
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // Видаляє найстаріший (найменш використовуваний) елемент при перевищенні ліміту:
        return size() > capacity;
    }
}

Важливий нюанс багатопотоковості: Цей кеш не є потокобезпечним. Навіть звичайний виклик cache.get(key) при accessOrder = true модифікує структуру двозв’язного списку (переміщує вузол у хвіст). Одночасні операції читання без зовнішньої синхронізації призведуть до зациклення посилань before/after. Для надійних рішень у production слід використовувати спеціалізовані бібліотеки (наприклад, Caffeine).

3. Приховані пастки застарілих класів: `Hashtable` та `Properties`

Hashtable: Клас із Java 1.0. Блокує всю мапу на кожен виклик методу через synchronized. Забороняє null для ключів і значень. У сучасному коді не використовується — замінений на ConcurrentHashMap.
Properties: Прямий спадкоємець Hashtable. Небезпека криється в порушенні типізації: метод setProperty(String, String) приймає рядки, проте оскільки Properties успадковує Hashtable<Object, Object>, метод put(key, value) дозволяє зберегти довільні об’єкти, що призводить до несподіваного ClassCastException при подальшому виклику getProperty().

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

30-секундна відповідь (Elevator Pitch)

«Інтерфейс Map<K, V> моделює структуру пар «ключ-значення» з гарантією унікальності ключів. Він не розширює Collection, оскільки має іншу семантику та надає три колекційні проєкції: keySet(), values() та entrySet(). Основні реалізації в Java: HashMap (високопродуктивний хеш-словник $O(1)$ за замовчуванням), LinkedHashMap (зберігає порядок вставки або доступу), TreeMap ($O(\log N)$, відсортований за ключами), ConcurrentHashMap (потокобезпечна масштабована альтернатива), а також спеціалізовані EnumMap (на масивах для enum), IdentityHashMap (порівняння за ==) та WeakHashMap (для збирача сміття). У Java 21 упорядковані мапи об’єднані інтерфейсом SequencedMap».

4 каверзних питання на інтерв’ю з відповідями

1. Чому `Map` не успадковує інтерфейс `Collection`, але `Map.values()` повертає `Collection`?

Відповідь: Collection<E> передбачає роботу з колекцією одиночних сутностей і контракт add(E). У Map базовою одиницею є пара Map.Entry<K, V>, тому напряму додати одиночний елемент неможливо. При цьому метод keySet() повертає Set, оскільки ключі строго унікальні, а метод values() повертає саме Collection, а не Set, оскільки різні ключі можуть мати абсолютно однакові значення.

2. У чому полягає архітектурна перевага `EnumMap` над `HashMap`?

Відповідь: EnumMap використовує внутрішній масив значень Object[] vals. Індексом у масиві слугує числовий key.ordinal(). Це виключає розрахунок хеш-кодів, усуває колізії та необхідність бакетів зі зв’язними списками/деревами, забезпечує компактне споживання пам’яті та абсолютну швидкість $O(1)$ на читання і запис.

3. Чому читання з `LinkedHashMap` може викликати `ConcurrentModificationException` під час ітерації?

Відповідь: Якщо LinkedHashMap сконструйовано з прапорцем accessOrder = true (режим доступу LRU), кожен виклик get(key) переставляє вузол у кінець зв’язного списку та інкрементує лічильник модифікацій modCount. Якщо читати з мапи під час обходу keySet() або entrySet(), Iterator зафіксує незбіг modCount і викине ConcurrentModificationException.

4. Як `IdentityHashMap` визначає рівність ключів і навіщо він потрібен?

Відповідь: IdentityHashMap порівнює ключі виключно за посиланням (k1 == k2) і використовує System.identityHashCode(k). Він незамінний у бібліотеках серіалізації, глибокого клонування та графових алгоритмах для відстеження відвіданих об’єктів за їхньою фізичною адресою в пам’яті, навіть якщо в об’єктів перевизначено equals(), що повертає true.

Типові помилки та Red Flags

❌ Твердження, що Map — це різновид Collection: Грубе незнання базової ієрархії JDK.
❌ Використання WeakHashMap як повноцінного кешу застосунку: Ключі у WeakHashMap видаляються при першій же збірці сміття (Minor GC), якщо на них немає сильних посилань. Для кешування слід використовувати спеціалізовані рішення (наприклад, Caffeine).
❌ Мутабельні ключі: Зміна полів об’єкта, за якими розраховується hashCode(), призводить до втрати елемента в мапі.
❌ Використання Hashtable у новому коді: Hashtable застарів і неефективний. Завжди слід використовувати ConcurrentHashMap для багатопотоковості.

🟢 Junior Level

1. Що таке Map

2. Чому Map НЕ успадковує Collection?

3. Зведена таблиця основних реалізацій Map

🟡 Middle Level

1. Спеціалізовані реалізації: EnumMap, IdentityHashMap, WeakHashMap

EnumMap: максимальна продуктивність

IdentityHashMap: рівність за посиланням (==)

WeakHashMap: ключі зі слабкими посиланнями