🟢 Junior Level

В Java є багато видів Map. Ось проста шпаргалка:

Map	Коли використовувати
HashMap	За замовчуванням. Швидка, проста
LinkedHashMap	Коли потрібен порядок вставки (або LRU-кеш)
TreeMap	Коли потрібні відсортовані ключі
ConcurrentHashMap	Коли працюють кілька потоків
WeakHashMap	Для тимчасових даних, прив’язаних до об’єктів
EnumMap	Коли ключі — це enum

Приклад:

// Звичайний випадок:
Map<String, Integer> map = new HashMap<>();

// Потокобезпечна:
Map<String, Integer> concurrent = new ConcurrentHashMap<>();

// Відсортована:
Map<String, Integer> sorted = new TreeMap<>();

Головне правило: Якщо не знаєте, що обрати — беріть HashMap.

🟡 Middle Level

Порівняльна таблиця

Реалізація	Порядок	Потокобезпечність	Null-ключи	Складність	Коли використовувати
HashMap	Ні	Ні	Так	O(1)	За замовчуванням
LinkedHashMap	Порядок вставки	Ні	Так	O(1)	LRU-кеш, порядок
TreeMap	Сортування	Ні	Ні	O(log n)	Навігація, діапазони
ConcurrentHashMap	Ні	Так	Ні	O(1)	Багатопотоковість
WeakHashMap	Ні	Ні	Так	O(1)	Метадані, кеш
EnumMap	Порядок enum	Ні	Ні	O(1)	Enum-ключі
IdentityHashMap	Ні	Ні	Так	O(1)	Порівняння за посиланням

LinkedHashMap: LRU Cache

Map<K, V> lruCache = new LinkedHashMap<>(capacity, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_SIZE;
    }
};

Параметр accessOrder = true — порядок за останнім доступом.

TreeMap: Навігація

TreeMap<String, Integer> tree = new TreeMap<>();
tree.put("a", 1);
tree.put("c", 3);
tree.put("b", 2);

tree.subMap("a", "c");    // {"a"=1, "b"=2}
tree.headMap("b");        // {"a"=1}
tree.tailMap("b");        // {"b"=2, "c"=3}
tree.firstKey();          // "a"
tree.lastKey();           // "c"

EnumMap: Максимальна швидкість

enum Status { ACTIVE, INACTIVE, PENDING }
Map<Status, Integer> counts = new EnumMap<>(Status.class);
// Всередині: масив Status.values().length — максимально швидко

ConcurrentHashMap: Атомарні операції

ConcurrentMap<String, Integer> map = new ConcurrentHashMap<>();
map.putIfAbsent("key", 0);
map.computeIfAbsent("key", k -> computeExpensive());
map.merge("key", 1, Integer::sum);

Immutable Maps (Java 10+)

Map<K, V> immutable = Map.of("a", 1, "b", 2);
// Або:
Map<K, V> copy = Map.copyOf(originalMap);
// Оптимізовані за пам'яттю, UnsupportedOperationException при модифікації

IdentityHashMap

IdentityHashMap — використовує == замість equals() для порівняння ключів. Два різних об’єкти з однаковими полями вважаються різними ключами. Рідкісний кейс: коли важлива саме ідентичність посилання, а не вміст.

🔴 Senior Level

Internal Implementations

HashMap: Масив + зв’язані списки/дерева. O(1) через хешування. LinkedHashMap: HashMap + двозв’язний список для порядку. overhead ~2 посилання на entry. TreeMap: Червоно-чорне дерево. O(log n), немає хешування, вимагає Comparable/Comparator. ConcurrentHashMap: CAS + synchronized на бакеті. volatile поля, multi-threaded resize. EnumMap: Звичайний масив Object[enum.length]. Доступ за ordinal(). IdentityHashMap: Open addressing (не chaining). Використовує == і System.identityHashCode().

Performance Comparison

Операція	HashMap	LinkedHashMap	TreeMap	ConcurrentHashMap	EnumMap
get()	O(1)	O(1)	O(log n)	O(1)	O(1)
put()	O(1)	O(1)	O(log n)	O(1)	O(1)
iteration	O(cap+n)	O(n)	O(n)	O(cap+n)	O(n)
Memory	Base	Base+16B	~48B/node	Base+volatile	~array
get 1M (ns)	5	6	50	8	1

Memory Footprint (на 1M entries)

Map	Approx. Memory
HashMap	~48MB
LinkedHashMap	~64MB (+2 refs/entry)
TreeMap	~80MB (червоно-чорне дерево: 4 посилання на entry — parent, left, right, next + колір)
ConcurrentHashMap	~56MB (volatile + header)
EnumMap (10 keys)	~100 bytes (лише масив)

Edge Cases

1. TreeMap і null-ключі: new TreeMap<>() кидає NPE при null. З Comparator.nullsFirst() — працює.
2. LinkedHashMap accessOrder: При true — кожен get() змінює порядок (для LRU). Це мутація!
3. ConcurrentHashMap size(): O(n) — рахує всі елементи. Не використовуйте в hot path.
4. EnumMap: Тільки enum-ключі. Спроба іншого типу = ClassCastException на етапі створення.

When to Use What

Default path:

Потрібна Map?
├── Багатопотоковий доступ? → ConcurrentHashMap
├── Ключі = Enum? → EnumMap
├── Потрібне сортування? → TreeMap
├── Потрібен порядок вставки / LRU? → LinkedHashMap
├── Кеш з автоочищенням по GC? → WeakHashMap
└── Все інше → HashMap

Specialized Libraries

Для production кешування:

• Caffeine — заміна Guava Cache, найкраща продуктивність
• Ehcache — distributed caching
• Redis/Memcached — external cache

Ці бібліотеки дають:

• TTL, LRU, LFU eviction
• Statistics (hit/miss rate)
• Async loading
• Distributed support

Production Decision Matrix

Вимога	Вибір
Read-heavy, single-thread	HashMap
Read-heavy, multi-thread	ConcurrentHashMap
Write-heavy, multi-thread	ConcurrentHashMap
Ordered iteration	LinkedHashMap
Range queries	TreeMap
Minimal memory (enum keys)	EnumMap
Cache з GC cleanup	WeakHashMap або Caffeine
Immutable config	Map.of()
Identity semantics	IdentityHashMap

---

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

Обов’язково знати:

• HashMap — default вибір, O(1), без порядку, допускає null
• LinkedHashMap — порядок вставки, LRU-кеш через accessOrder + removeEldestEntry
• TreeMap — сортування, O(log n), навігація (subMap, headMap, tailMap), немає null-ключів
• ConcurrentHashMap — багатопотоковість, CAS + synchronized на бакеті, немає null
• EnumMap — enum-ключі, всередині масив, O(1), максимально швидкий і компактний
• WeakHashMap — автоочищення по GC, для метаданих, не для production caching
• IdentityHashMap — порівняння за == замість equals, open addressing (не chaining)

Часті уточнюючі запитання:

• Як зробити LRU-кеш? — LinkedHashMap з accessOrder=true і override removeEldestEntry
• Чому IdentityHashMap використовує open addressing? — для identity-семантики chaining не потрібен
• Коли TreeMap кращий за HashMap? — потрібні range queries або сортування ключів
• Чим EnumMap швидший за HashMap? — масив з ordinal() як індекс, немає hashCode, немає колізій

Червоні прапорці (НЕ говорити):

• «TreeMap = O(1)» — ні, O(log n)
• «WeakHashMap = production cache» — ні, немає TTL/LRU/лімітів; використовуйте Caffeine
• «IdentityHashMap = те саме що HashMap» — ні, використовує == замість equals

Пов’язані теми:

• [[1. Як влаштований HashMap всередині]]
• [[23. Що таке ConcurrentHashMap і чим він відрізняється від HashMap]]
• [[27. Що таке WeakHashMap]]