🟢 Junior Level

HashMap, LinkedHashMap та TreeMap — три основні реалізації Map.

Головна різниця:

	HashMap	LinkedHashMap	TreeMap
Порядок	Немає	Порядок додавання	Сортування
Швидкість	Швидка O(1)	Трохи повільніша O(1) + оверхед DLL	Повільніша O(log n) дерево
null ключ	✅ Один	✅ Один	❌ Не можна
Складність	O(1)	O(1)	O(log n)

// HashMap: без порядку
Map<String, Integer> hm = new HashMap<>();
hm.put("C", 3); hm.put("A", 1); hm.put("B", 2);
// → {A=1, C=3, B=2} (порядок не гарантований)

// LinkedHashMap: порядок вставки
Map<String, Integer> lh = new LinkedHashMap<>();
lh.put("C", 3); lh.put("A", 1); lh.put("B", 2);
// → {C=3, A=1, B=2} (як додали)

// TreeMap: сортування за ключами
Map<String, Integer> tm = new TreeMap<>();
tm.put("C", 3); tm.put("A", 1); tm.put("B", 2);
// → {A=1, B=2, C=3} (відсортовано!)

---

🟡 Middle Level

HashMap: швидкість

// Всередині: масив корзин + списки/дерева
// O(1) для get/put
// → Найкращий вибір за замовчуванням

// Treeification (Java 8+):
// > 8 елементів у корзині → дерево
// → Захист від поганих hashCode()

// Resize: × 2 при заповненні
→ → Дорога операція (копіювання всіх елементів)

LinkedHashMap: порядок + LRU

// Всередині: HashMap + двозв'язний список
// O(1) для get/put
// + порядок вставки

// LRU кеш:
Map<K, V> cache = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX;
    }
};
// accessOrder = true → get() переміщує в кінець

TreeMap: сортування

// Всередині: червоно-чорне дерево
// O(log n) для get/put
// → Сортування за ключами
// → floorKey, ceilingKey, subMap

// Не приймає null (без custom Comparator)
// compareTo визначає унікальність!

Коли що використовувати

Сценарій	Що обрати
Словник, кеш	HashMap
Порядок вставки	LinkedHashMap
LRU кеш	LinkedHashMap (accessOrder)
Сортування ключів	TreeMap
Діапазонний пошук	TreeMap

Cache Locality

Cache Locality: HashMap — масив корзин, елементи поруч у пам’яті (краща кеш-локальність). LinkedHashMap — вузли пов’язані посиланнями, розкидані по купі (більше cache miss при ітерації).

---

🔴 Senior Level

Memory Comparison

HashMap entry: ~32 байти
LinkedHashMap entry: ~48 байт (+ before/after)
TreeMap entry: ~40-56 байт (left/right/parent/color)

→ 1 млн записів:
  HashMap: ~36 МБ
  LinkedHashMap: ~52 МБ
  TreeMap: ~44 МБ

Java 21: SequencedMap

// LinkedHashMap та TreeMap → SequencedMap (SequencedMap — Java 21+, недоступно на старіших версіях.)
map.putFirst("A", 1);    // Новий метод!
map.putLast("Z", 26);    // Новий метод!
map.firstEntry();        // Новий метод!
map.reversed();          // Зворотний порядок (view)

// HashMap НЕ SequencedMap

False Sharing у багатопотоковості

synchronizedMap(new HashMap<>())
  → Конкуренція за cache lines
  → False sharing на багатоядерних CPU

ConcurrentHashMap → рішення!

compareTo vs equals

// TreeMap використовує compareTo!
// Якщо compareTo = 0 → елемент вже є
// Навіть якщо equals = false!

class Key implements Comparable<Key> {
    String name;
    public int compareTo(Key o) {
        return name.compareTo(o.name);
    }
    public boolean equals(Object o) {
        return false; // Інша логіка!
    }
}

// → Втрата даних якщо не узгоджені!

Production Experience

Реальний сценарій: LRU кеш

// 10,000 елементів, часті читання
// HashMap + ручне видалення старих → складно

// LinkedHashMap з accessOrder + removeEldestEntry
// → 5 рядків коду → готовий кеш!

Best Practices

1. HashMap — вибір за замовчуванням, якщо не потрібен порядок або сортування
2. LinkedHashMap — порядок або LRU
3. TreeMap — сортування/діапазони
4. initialCapacity → уникайте resize
5. Immutable ключі — обов’язково
6. Java 21 → SequencedMap API
7. compareTo = equals для TreeMap
8. Memory → HashMap компактніший

Резюме для Senior

• HashMap = O(1), немає порядку, treeification
• LinkedHashMap = O(1), порядок, LRU кеш
• TreeMap = O(log n), сортування, навігація
• Memory: HashMap < TreeMap < LinkedHashMap
• SequencedMap (Java 21) → putFirst/reversed
• CPU Cache: HashMap > TreeMap
• compareTo ≠ equals → втрата даних
• LRU = LinkedHashMap(accessOrder=true)

---

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

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

• HashMap = O(1), немає порядку, всередині масив корзин + списки/дерева, treeification при > 8 колізій
• LinkedHashMap = O(1) + двозв’язний список для порядку вставки, підтримка LRU кешу (accessOrder=true)
• TreeMap = O(log n), червоно-чорне дерево, сортування за ключами, навігація (floorKey, ceilingKey, subMap)
• HashMap допускає один null-ключ, TreeMap — ні (без custom Comparator)
• TreeMap використовує compareTo для унікальності, а не equals — неузгодженість = втрата даних
• Memory: HashMap (~32 байти/entry) < TreeMap (~40-56 байт) < LinkedHashMap (~48 байт)
• Java 21: SequencedMap API (putFirst, putLast, reversed) для LinkedHashMap та TreeMap
• LRU кеш = LinkedHashMap(16, 0.75f, true) + перевизначений removeEldestEntry

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

• Як працює LRU кеш на LinkedHashMap? — accessOrder=true переміщує елемент у кінець при кожному get(). removeEldestEntry() видаляє найстаріший при перевищенні ліміту.
• Чому TreeMap не приймає null? — Тому що потрібно викликати compareTo для сортування, а у null немає методу compareTo. Обхід: Comparator.nullsFirst().
• Що таке treeification у HashMap? — При > 8 елементів в одній корзині зв’язний список перетворюється у червоно-чорне дерево — захист від O(n) при колізіях.
• Коли HashMap кращий за LinkedHashMap? — Завжди за замовчуванням, якщо не потрібен порядок ітерації. LinkedHashMap витрачає +50% пам’яті на зв’язний список.

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

• ❌ «TreeMap використовує equals для перевірки ключів» — використовує compareTo!
• ❌ «HashMap зберігає порядок вставки» — ні, порядок не гарантований
• ❌ «LinkedHashMap повільніший для get/put» — складність та сама O(1), тільки більше пам’яті
• ❌ «TreeMap потрібен для порядку вставки» — для цього є LinkedHashMap, TreeMap сортує за ключами

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

• [[14. Що таке Map і які реалізації існують]]
• [[16. Коли використовувати TreeMap]]
• [[11. В чому різниця між HashSet, LinkedHashSet та TreeSet]]
• [[18. Що таке ConcurrentHashMap]]