🟢 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 (array only)

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