Java Interview Questions

Главная / Все ответы / Коллекции

Вопрос 14 · Раздел 4

Что такое Map и какие реализации существуют?

4. TreeMap — сортировка/диапазоны 5. ConcurrentHashMap — многопоточность 6. Map.of() — для статических справочников 7. Immutable ключи — обязательно! 8. computeIfAbsent/merge —...

Russian Коллекции Исходный Markdown
Версии по языкам: English Russian Ukrainian

🟢 Junior Level

Map (Словарь) — коллекция пар ключ-значение.

Аналогия: Map — как бумажный словарь: по слову (ключу) вы находите определение (значение). Ключ уникален (одно слово в словаре только один раз), значение может повторяться (у разных слов одно определение).

Map<String, Integer> ages = new HashMap<>();
ages.put("Ivan", 25);    // Положить
ages.put("Maria", 30);

int age = ages.get("Ivan");  // Получить → 25
boolean has = ages.containsKey("Ivan");  // → true

Основные реализации:

Реализация Когда использовать
HashMap По умолчанию (быстрая)
LinkedHashMap Нужен порядок
TreeMap Нужна сортировка
ConcurrentHashMap Многопоточность

Map ≠ Collection!

  • Map работает с ПАРАМИ (ключ-значение)
  • Collection работает с ОДИНОЧНЫМИ элементами

🟡 Middle Level

Основные реализации

HashMap:

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);  // O(1)
map.get("A");     // O(1)
// → Быстрая, без порядка

LinkedHashMap:

Map<String, Integer> map = new LinkedHashMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);
// → Порядок: C, A, B (как добавили)

TreeMap:

Map<String, Integer> map = new TreeMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);
// → Порядок: A, B, C (отсортировано)
// → floorKey, ceilingKey, subMap

Специализированные Map

EnumMap:

// Для Enum ключей — самая быстрая! Внутри массив — индекс = enum.ordinal(), без хеширования и коллизий. Прямая индексация = O(1) без накладных расходов.
enum Status { ACTIVE, INACTIVE }
Map<Status, String> map = new EnumMap<>(Status.class);
// → Внутри: массив! O(1), минимум памяти

WeakHashMap:

// Ключи = слабые ссылки
// Удаляется, когда на ключ нет сильных ссылок
Map<Object, String> map = new WeakHashMap<>();
// → Для кэшей и метаданных

IdentityHashMap:

// Сравнение по == (адрес), не equals
Map<String, String> map = new IdentityHashMap<>();
map.put(new String("A"), "1");
map.put(new String("A"), "2");  // Два разных ключа!
// → Для сериализации, поиска циклов

Java 9+ неизменяемые Map

// Фабричные методы
Map<String, Integer> map = Map.of(
    "A", 1,
    "B", 2,
    "C", 3
);
// → Нельзя изменить!
// → Компактная память
// → Порядок рандомизирован!
// Ограничения Map.of(): максимум 10 пар, null ключи/значения запрещены. При > 10 пар — используйте Map.ofEntries().

Java 8+ полезные методы

map.computeIfAbsent(key, k -> new ArrayList<>())
   .add(value);

map.merge(key, 1, Integer::sum);  // Счётчик

map.putIfAbsent(key, value);

🔴 Senior Level

Java 21: SequencedMap

// LinkedHashMap и TreeMap → SequencedMap
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.putFirst("A", 1);   // Новый метод!
map.putLast("Z", 26);   // Новый метод!
map.firstEntry();       // Новый метод!
map.reversed();         // Обратный порядок (view)

// HashMap НЕ SequencedMap (нет порядка)

Memory Footprint

HashMap Entry: ~32-48 байт
  → Node: hash, key, value, next
  
LinkedHashMap: ~48 байт
  → + before, after ссылки
  
TreeMap: ~40-56 байт
  → Entry: key, value, left, right, parent, color
  
→ Для миллионов записей → гигабайты!

Load Factor trade-off

Load Factor (коэффициент заполнения) = отношение числа элементов к числу корзин. При load factor 0.75 и мапе на 100 элементов — 133 корзины. При заполнении > 75% — resize (пересоздание таблицы).

По умолчанию: 0.75

0.75 = баланс между:
  → Память (меньше → больше заполнение)
  → Коллизии (больше → медленнее поиск)

Увеличить (0.9):
  → -20% памяти
  → +коллизии
  
Уменьшить (0.5):
  → +50% памяти
  → -коллизии

IdentityHashMap use cases

// 1. Поиск циклов в графе объектов
IdentityHashMap<Object, Boolean> visited = new IdentityHashMap<>();

// 2. Сериализация (учёт уже сериализованных)
IdentityHashMap<Object, Integer> serialized = new IdentityHashMap<>();

// 3. Когда equals переопределён, но нужен identity

EnumMap: почему самый быстрый?

// Внутри: Object[] array
// Индекс = ordinal()_enum

// put(key, value):
array[key.ordinal()] = value;  // O(1), прямая индексация!

// get(key):
return array[key.ordinal()];   // O(1), без хеширования!

→ Быстрее HashMap, меньше памяти

Highload аспекты

HashMap:
  → Treeification при коллизиях (> 8)
  → Resize: O(n), всплеск latency
  → Memory: ~32 байта на entry
  
ConcurrentHashMap:
  → Lock-free чтение
  → CAS + synchronized на корзину
  → Нулевые задержки для чтений

Production Experience

Реальный сценарий: HashMap → EnumMap

// Было: HashMap<Status, Counter>
// 100,000 запросов/сек → GC pressure

// Стало: EnumMap<Status, Counter>
// → -40% памяти
// → +25% throughput

Best Practices

  1. HashMap — по умолчанию
  2. EnumMap — для Enum ключей
  3. LinkedHashMap — порядок или LRU
  4. TreeMap — сортировка/диапазоны
  5. ConcurrentHashMap — многопоточность
  6. Map.of() — для статических справочников
  7. Immutable ключи — обязательно!
  8. computeIfAbsent/merge — атомарные операции

Резюме для Senior

  • Map ≠ Collection (пары vs одиночные)
  • SequencedMap (Java 21) → putFirst/reversed
  • EnumMap = массив → самый быстрый
  • IdentityHashMap = сравнение по ==
  • Load Factor = память vs коллизии trade-off
  • computeIfAbsent/merge — атомарные Java 8+
  • Immutable ключи — критично!
  • Map.of() → компактные неизменяемые

🎯 Шпаргалка для интервью

Обязательно знать:

  • Map — коллекция пар ключ-значение, ключи уникальны, Map ≠ Collection
  • HashMap = O(1), по умолчанию; LinkedHashMap = O(1) + порядок вставки; TreeMap = O(log n) + сортировка; ConcurrentHashMap = thread-safe
  • EnumMap — самый быстрый Map (внутри массив, индекс = ordinal), для enum-ключей
  • WeakHashMap — ключи удаляются автоматически при отсутствии сильных ссылок (для метаданных, НЕ для кэшей)
  • IdentityHashMap — сравнение по == вместо equals (для сериализации, поиска циклов)
  • Load factor 0.75 — баланс между памятью и коллизиями
  • Java 21: SequencedMap API (putFirst, putLast, reversed) для LinkedHashMap и TreeMap
  • Java 8+: computeIfAbsent, merge, putIfAbsent — атомарные операции
  • Map.of() — неизменяемые Map, максимум 10 пар, null запрещены

Частые уточняющие вопросы:

  • Почему EnumMap самый быстрый? — Внутри массив, прямая индексация по ordinal(), без хеширования и коллизий — O(1) с минимальным оверхедом.
  • Чем WeakHashMap отличается от обычного Map для кэша? — WeakHashMap удаляет записи при КАЖДОМ Minor GC — кэш может исчезнуть через миллисекунды. Для кэшей лучше Caffeine или SoftReference.
  • Когда использовать IdentityHashMap? — Когда нужно сравнение по ссылке (==), а не по equals: сериализация, поиск циклов в графе объектов.
  • Что такое SequencedMap? — Java 21 интерфейс для упорядоченных Map: putFirst, putLast, firstEntry, reversed.

Красные флаги (НЕ говорить):

  • ❌ «Map — это Collection» — Map НЕ расширяет Collection, работает с парами ключ-значение
  • ❌ «WeakHashMap — хороший выбор для кэша» — слишком агрессивная очистка, используйте Caffeine
  • ❌ «IdentityHashMap то же самое, что HashMap» — IdentityHashMap сравнивает ключи по ==, а не equals
  • ❌ «Map.of() можно изменять» — это неизменяемая коллекция, UnsupportedOperationException при модификации

Связанные темы:

  • [[15. В чём разница между HashMap, LinkedHashMap и TreeMap]]
  • [[17. Что такое WeakHashMap]]
  • [[18. Что такое ConcurrentHashMap]]
  • [[16. Когда использовать TreeMap]]