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

Интерфейс Map (словарь, ассоциативный массив) представляет собой структуру данных, хранящую пары «ключ — значение» (Key-Value pairs):

🟢 Junior Level

1. Что такое Map

Интерфейс Map<K, V> (словарь, ассоциативный массив) представляет собой структуру данных, хранящую пары «ключ — значение» (Key-Value pairs):

Ключи (K) должны быть строго уникальными. Добавление существующего ключа перезаписывает старое значение.
Значения (V) могут дублироваться.
Каждому ключу соответствует ровно одно значение.

Map<String, Integer> salaries = new HashMap<>();
salaries.put("Алексей", 120_000);
salaries.put("Мария", 150_000);

// Получение значения по ключу:
Integer alexSalary = salaries.get("Алексей"); // 120000

// Проверка наличия:
boolean hasMaria = salaries.containsKey("Мария"); // true

2. Почему `Map` НЕ наследует `Collection`?

Это один из самых частых вопросов на собеседованиях. Map не является частью иерархии Collection по архитектурным соображениям:

Разная семантика элементов: Collection<E> управляет коллекцией одиночных элементов (add(E e), iterator()), в то время как Map<K, V> оперирует парами двух разных сущностей с раздельным доступом к ключам и значениям (put(K, V)).
Представления (Views): вместо прямой итерации Map предоставляет три различных проекции коллекций:
- keySet() $\to$ Set<K> (множество уникальных ключей).
- values() $\to$ Collection<V> (коллекция неуникальных значений).
- entrySet() $\to$ Set<Map.Entry<K, V>> (множество пар «ключ-значение»).

3. Сводная таблица основных реализаций `Map`

Класс	Порядок ключей	Сложность (`get`/`put`)	Допускает `null`	Потокобезопасность	Основное применение
`HashMap`	Не гарантирован	$O(1)$ в среднем	Key: ✅ (один), Val: ✅	❌ Нет	Основная реализация по умолчанию
`LinkedHashMap`	Порядок вставки или доступа	$O(1)$ в среднем	Key: ✅ (один), Val: ✅	❌ Нет	Предсказуемый порядок, построение LRU-кэша
`TreeMap`	Отсортирован (Comparable/Comparator)	$O(\log N)$	Key: ❌ (NPE), Val: ✅	❌ Нет	Навигация по диапазонам, сортировка ключей
`ConcurrentHashMap`	Не гарантирован	$O(1)$ в среднем	Key: ❌, Val: ❌	✅ Да	Высоконагруженная многопоточная среда
`EnumMap`	Порядок объявления enum	$O(1)$ (прямой массив)	Key: ❌, Val: ✅	❌ Нет	Ключи типа `enum` (максимальная скорость)
`WeakHashMap`	Не гарантирован	$O(1)$ в среднем	Key: ✅, Val: ✅	❌ Нет	Вспомогательные метаданные для GC
`IdentityHashMap`	Не гарантирован (сравнение по `==`)	$O(1)$ в среднем	Key: ✅, Val: ✅	❌ Нет	Сериализация, обход графов с циклами

🟡 Middle Level

1. Специализированные реализации: `EnumMap`, `IdentityHashMap`, `WeakHashMap`

`EnumMap`: максимальная производительность

Если ключами являются элементы перечисления (enum), использование HashMap считается антипаттерном. EnumMap устроен внутри как простой массив фиксированного размера:

enum TaskPriority { LOW, MEDIUM, HIGH, URGENT }

Map<TaskPriority, String> tasks = new EnumMap<>(TaskPriority.class);
tasks.put(TaskPriority.HIGH, "Исправить баг в проде");

Почему это быстрее HashMap: Индексом в массиве служит enum.ordinal(). Никакого вычисления hashCode(), никаких коллизий, никаких списков и деревьев. Это прямое обращение к ячейке массива за 1 такт процессора.

`IdentityHashMap`: равенство по ссылке (`==`)

В отличие от всех остальных реализаций, IdentityHashMap полностью игнорирует equals() и hashCode(). Два ключа k1 и k2 считаются одинаковыми только тогда, когда k1 == k2.

Внутри используется открытая адресация в плоском массиве Object[] table, где ключи и значения чередуются (table[i] = key, table[i+1] = value).
Применяется в библиотеках сериализации (Jackson, Kryo) и клонирования объектов для отслеживания уже посещенных узлов и предотвращения зацикливания при циклических ссылках.

`WeakHashMap`: ключи со слабыми ссылками

Ключи оборачиваются в WeakReference. Если на объект-ключ больше нет сильных (StrongReference) ссылок во всем приложении, сборщик мусора удаляет ключ, а запись в WeakHashMap автоматически вычищается при следующем обращении к мапе.

2. Функциональный API в Java 8+

Java 8 кардинально упростила работу с Map, добавив методы, принимающие лямбды:

Map<String, List<String>> userRoles = new HashMap<>();

// computeIfAbsent: создает и кладет список, только если ключа не было:
userRoles.computeIfAbsent("ivan", k -> new ArrayList<>()).add("ROLE_USER");

// merge: идеально подходит для счетчиков и агрегаций:
Map<String, Integer> wordCount = new HashMap<>();
String word = "java";
wordCount.merge(word, 1, Integer::sum); // если нет -> 1, если есть -> старое + 1

// getOrDefault: предотвращает NPE:
int count = wordCount.getOrDefault("unknown", 0);

3. Неизменяемые фабричные методы (Java 9+)

Методы Map.of() и Map.ofEntries() возвращают оптимизированные компактные неизменяемые реализации:

// До 10 пар ключ-значение:
Map<String, String> config = Map.of(
    "env", "production",
    "timeout", "5000"
);

// Более 10 пар:
Map<Integer, String> codes = Map.ofEntries(
    Map.entry(200, "OK"),
    Map.entry(404, "Not Found"),
    Map.entry(500, "Internal Server Error")
);

Критичные свойства:

Запрещают null как для ключей, так и для значений (вызывают NullPointerException).
Занимают в 2–3 раза меньше памяти, чем HashMap, так как не создают тяжеловесных нод Node<K,V>.
Итерационный порядок ключей намеренно рандомизируется при каждом перезапуске JVM, чтобы разработчики не полагались на случайную упорядоченность.

🔴 Senior Level

1. Архитектурная эволюция в Java 21: `SequencedMap`

До Java 21 в стандартной библиотеке не было единого интерфейса для карт с гарантированным порядком обхода. В Java 21 представлен интерфейс SequencedMap<K, V>:

          ┌─────────────────┐
          │   Map<K, V>     │
          └────────┬────────┘
                   │ extends
          ┌────────┴────────┐
          │ SequencedMap    │
          └───┬─────────┬───┘
              │         │
     implements         implements
              │         │
   ┌──────────┴──┐   ┌──┴───────────┐
   │LinkedHashMap│   │ NavigableMap │
   └─────────────┘   └──┬───────────┘
                        │ implements
                     ┌──┴───────────┐
                     │   TreeMap    │
                     └──────────────┘

SequencedMap стандартизирует методы:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putFirst("A", 1);
map.putLast("Z", 26);

Map.Entry<String, Integer> first = map.firstEntry(); // "A" -> 1
Map.Entry<String, Integer> last = map.lastEntry();   // "Z" -> 26

// Реверсивное представление карты без копирования (View) за O(1):
SequencedMap<String, Integer> reversedMap = map.reversed();

HashMap не реализует SequencedMap, так как не гарантирует никакого порядка элементов.

2. Построение LRU-кэша через `LinkedHashMap`

Класс LinkedHashMap имеет встроенную поддержку вытеснения устаревших записей (Least Recently Used Cache) через специальный конструктор и метод removeEldestEntry:

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LruCache(int capacity) {
        // accessOrder = true: порядок элементов перестраивается по ЧТЕНИЮ (get/put)
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // Удаляет самый старый (наименее используемый) элемент при превышении емкости:
        return size() > capacity;
    }
}

Важный нюанс многопоточности: Данный кэш не потокобезопасен. Даже обычный вызов cache.get(key) при accessOrder = true модифицирует структуру двусвязного списка (перемещает ноду в хвост). Одновременные чтения без внешней синхронизации приведут к зацикливанию ссылок before/after. Для production-решений предпочтительнее использовать специализированные библиотеки (например, Caffeine).

3. Скрытые ловушки устаревших классов: `Hashtable` и `Properties`

Hashtable: Класс из Java 1.0. Блокирует всю мапу на каждый метод через synchronized. Запрещает null ключи и значения. В современном коде не используется — заменен на ConcurrentHashMap.
Properties: Наследник Hashtable. Опасность заключается в нарушении типизации: метод setProperty(String, String) принимает строки, но так как Properties наследует Hashtable<Object, Object>, метод put(key, value) позволяет положить любые объекты, что приводит к ClassCastException при последующем вызове getProperty().

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

30-секундный ответ (Elevator Pitch)

«Интерфейс Map<K, V> моделирует структуру пар «ключ-значение» с гарантией уникальности ключей. Он не расширяет Collection, так как имеет иную семантику и предоставляет три представления: keySet(), values() и entrySet(). Основные реализации в Java: HashMap (высокопроизводительный хэш-словарь $O(1)$ по умолчанию), LinkedHashMap (сохраняет порядок вставки или доступа), TreeMap ($O(\log N)$, отсортирован по ключам), ConcurrentHashMap (потокобезопасная масштабируемая альтернатива), а также узкоспециализированные EnumMap (на массивах для enum), IdentityHashMap (сравнение по ==) и WeakHashMap (для сборщика мусора). В Java 21 упорядоченные мапы объединены интерфейсом SequencedMap».

4 каверзных вопроса на интервью с ответами

1. Почему `Map` не наследует интерфейс `Collection`, но `Map.values()` возвращает `Collection`?

Ответ: Collection<E> подразумевает коллекцию одиночных элементов и контракт add(E). В Map базовой единицей является пара Map.Entry<K, V>, поэтому напрямую добавить одиночный элемент нельзя. При этом метод keySet() возвращает Set, так как ключи уникальны, а метод values() возвращает именно Collection, а не Set, потому что разные ключи могут иметь абсолютно одинаковые значения.

2. В чём архитектурное превосходство `EnumMap` над `HashMap`?

Ответ: EnumMap использует массив значений Object[] vals. Индексом в массиве является key.ordinal(). Это исключает вычисление хэш-кодов, устраняет коллизии и необходимость бакетов со связными списками/деревьями, обеспечивает компактное потребление памяти и абсолютную скорость $O(1)$ на чтение и запись.

3. Почему чтение из `LinkedHashMap` может вызвать `ConcurrentModificationException` во время итерации?

Ответ: Если LinkedHashMap сконструирован с параметром accessOrder = true (режим доступа LRU), каждый вызов get(key) переставляет ноду в конец связного списка и инкрементирует счетчик модификаций modCount. Если читать из мапы во время обхода keySet() или entrySet(), Iterator зафиксирует несовпадение modCount и выбросит ConcurrentModificationException.

4. Как `IdentityHashMap` определяет равенство ключей и зачем он нужен?

Ответ: IdentityHashMap сравнивает ключи исключительно по ссылке (k1 == k2) и использует System.identityHashCode(k). Он незаменим в библиотеках сериализации, глубокого копирования и графовых алгоритмах для отслеживания посещенных объектов по их физическому адресу в памяти, даже если у объектов переопределен equals(), возвращающий true.

Типичные ошибки и Red Flags

❌ Утверждение, что Map — это коллекция: Нарушение базовой иерархии JDK.
❌ Использование WeakHashMap в качестве полноценного кэша приложения: Ключи в WeakHashMap удаляются при первой же сборке мусора (Minor GC), если на них нет сильных ссылок. Для кэширования необходимо использовать кэши с алгоритмами LRU/W-TinyLFU (например, Caffeine).
❌ Мутабельные ключи: Изменение полей объекта, по которым рассчитывается hashCode(), приводит к потере элемента в мапе.
❌ Использование Hashtable в новом коде: Hashtable устарел и неэффективен. Всегда используйте ConcurrentHashMap для многопоточности.

🟢 Junior Level

1. Что такое Map

2. Почему Map НЕ наследует Collection?

3. Сводная таблица основных реализаций Map

🟡 Middle Level

1. Специализированные реализации: EnumMap, IdentityHashMap, WeakHashMap

EnumMap: максимальная производительность

IdentityHashMap: равенство по ссылке (==)

WeakHashMap: ключи со слабыми ссылками