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