В чём разница между HashMap, LinkedHashMap и TreeMap

Классы HashMap, LinkedHashMap и TreeMap — три фундаментальные реализации интерфейса Map в Java. Их ключевые отличия заключаются во внутреннем устройстве, порядке обхода элементо...

🟢 Junior Level

1. Сравнительная таблица характеристик

Классы HashMap, LinkedHashMap и TreeMap — три фундаментальные реализации интерфейса Map в Java. Их ключевые отличия заключаются во внутреннем устройстве, порядке обхода элементов и скорости работы:

Характеристика	`HashMap`	`LinkedHashMap`	`TreeMap`
Порядок элементов	Хаотичный (зависит от хэш-кодов)	Порядок вставки (или порядок доступа)	Отсортированный (Natural или Comparator)
Внутренняя структура	Хэш-таблица (массив + списки/деревья)	Хэш-таблица + двусвязный список	Красно-чёрное дерево поиска
Сложность `get` / `put`	$O(1)$ в среднем	$O(1)$ в среднем	$O(\log N)$
Сложность итерации	$O(\text{capacity} + N)$	$O(N)$	$O(N)$
Ключ `null`	✅ Разрешен (один)	✅ Разрешен (один)	❌ Запрещен (`NullPointerException`)
Интерфейсы	`Map`	`Map`, `SequencedMap` (Java 21+)	`Map`, `NavigableMap`, `SequencedMap`
Основное назначение	Универсальный быстрый словарь	Порядок вставки, LRU-кэширование	Сортировка по ключам, поиск диапазонов

2. Разница в порядке обхода (Code Demo)

// 1. HashMap: порядок не гарантирован и может меняться при ресайзе
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Z", 1); hashMap.put("A", 2); hashMap.put("M", 3);
System.out.println(hashMap.keySet()); // Например: [A, Z, M] (зависит от хэша)

// 2. LinkedHashMap: строгий порядок вставки
Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("Z", 1); linkedMap.put("A", 2); linkedMap.put("M", 3);
System.out.println(linkedMap.keySet()); // ВСЕГДА: [Z, A, M]

// 3. TreeMap: естественный алфавитный порядок
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Z", 1); treeMap.put("A", 2); treeMap.put("M", 3);
System.out.println(treeMap.keySet()); // ВСЕГДА: [A, M, Z]

🟡 Middle Level

1. Архитектура структур данных под капотом

HashMap:
  table[] ──► [0] ──► Node(k,v) ──► Node(k,v) (связный список или TreeNode)
              [1] ──► null
              [2] ──► Node(k,v)

LinkedHashMap:
  table[] ──► [0] ──► Entry(k,v) ──► Entry(k,v)  (хэш-таблица для поиска за O(1))
                        │   ▲
                        ▼   │ before / after указатели
  head ─────────────► [Entry1] ◄────► [Entry2] ◄────► [Entry3] ◄─── tail (двусвязный список)

TreeMap:
              [ Root: Entry(k,v) ]
                 /            \
       [ Left: Entry ]     [ Right: Entry ]  (Красно-черное дерево, O(log N))

HashMap рассчитывает индекс бакета через (capacity - 1) & hash(key). При коллизиях организует односвязный список, трансформирующийся в красно-черное дерево при $\ge 8$ элементах в бакете и емкости $\ge 64$.
LinkedHashMap наследует HashMap, но расширяет класс ноды: LinkedHashMap.Entry<K,V> содержит ссылки before и after. При любой вставке элемент связывается в общий сквозной двусвязный список.
TreeMap не использует хэширование. Узлы связываются через указатели left, right, parent и балансируются по правилам красно-чёрного дерева.

2. Парадокс скорости итерации: `HashMap` против `LinkedHashMap`

Хотя LinkedHashMap тратит чуть больше времени на put() из-за поддержки ссылок двусвязного списка, итерация по LinkedHashMap часто быстрее, чем по HashMap:

В HashMap итератор обязан последовательно обойти все ячейки массива table[] размером capacity. Если вы создали мапу с capacity = 1_000_000 и положили всего 50 элементов, HashMap будет проверять 1 миллион пустых ячеек памяти ($O(\text{capacity} + N)$).
В LinkedHashMap итератор идет напрямую от head к tail по указателям after, выполняя ровно $N$ шагов ($O(N)$), игнорируя размер массива бакетов.

3. Режимы упорядочивания `LinkedHashMap` и LRU-кэш

LinkedHashMap имеет конструктор с флагом accessOrder:

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

accessOrder = false (по умолчанию): элементы обходятся в порядке добавления (insertion-order).
accessOrder = true: элементы перестраиваются в порядке последнего обращения (access-order). Вызовы get() и put() перемещают затронутую ноду в самый конец (хвост) списка.

Это позволяет легко реализовать LRU (Least Recently Used) кэш в 5 строк:

Map<String, byte[]> lruCache = new LinkedHashMap<String, byte[]>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, byte[]> eldest) {
        return size() > 1000; // Удаляет самый неиспользуемый элемент при > 1000 записей
    }
};

🔴 Senior Level

1. Детальное сравнение расхода памяти (Memory Footprint)

На 64-битной JVM с Compressed OOPs (-XX:+UseCompressedOops):

HashMap$Node<K,V>:
- Заголовок (12 байт) + hash (4 байта) + 3 ссылки (key, value, next по 4 байта = 12 байт) + padding (4 байта) = 32 байта.
LinkedHashMap$Entry<K,V>:
- Расширяет HashMap$Node, добавляя 2 ссылки (before, after по 4 байта = 8 байт).
- $32 + 8 =$ 40 байт.
TreeMap$Entry<K,V>:
- Заголовок (12 байт) + 5 ссылок (key, value, left, right, parent по 4 байта = 20 байт) + boolean color (1 байт) + padding (7 байт) = 40 байт.

Метрика	`HashMap`	`LinkedHashMap`	`TreeMap`
Размер ноды (Compressed OOPs)	32 байта	40 байт	40 байт
Массив бакетов (`table[]`)	Да (4 байта на слот)	Да (4 байта на слот)	Нет (только корень)
Локальность кэша процессора	Средняя	Низкая (двусвязный список)	Очень низкая (дерево по всей куче)
Оверхед на 1 000 000 записей	$\approx 36$ МБ	$\approx 44$ МБ	$\approx 40$ МБ

2. Специфика Java 21: `SequencedMap`

Интерфейс SequencedMap объединил коллекции с определенным порядком обхода:

SequencedMap<String, Integer> seqMap = new LinkedHashMap<>();
seqMap.putFirst("FIRST", 1);
seqMap.putLast("LAST", 99);

// Бесплатный разворот обхода за O(1) (Live View):
SequencedMap<String, Integer> reversed = seqMap.reversed();

Критическая разница между LinkedHashMap и TreeMap в SequencedMap:

В LinkedHashMap методы putFirst() и putLast() разрешены и перемещают элемент в начало или конец списка.
В TreeMap методы putFirst() и putLast() всегда выбрасывают UnsupportedOperationException, так как позиция ноды в дереве строго продиктована результатом компаратора!

3. Ловушка равенства: `hashCode`/`equals` против `compareTo`

HashMap и LinkedHashMap определяют равенство ключей через k1.hashCode() == k2.hashCode() && (k1 == k2 || k1.equals(k2)).
TreeMap вообще не вызывает hashCode() и equals(). Он опирается строго на compare(k1, k2) == 0.

Если у ваших объектов compareTo не согласован с equals (как у BigDecimal("1.0") и BigDecimal("1.00")), поведение мап будет принципиально различаться:

В HashMap сохранятся обе записи.
В TreeMap вторая запись перезапишет значение первой, так как для дерева ключи идентичны.

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

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

«HashMap — это хэш-таблица с амортизированным временем $O(1)$ для поиска и вставки, не гарантирующая порядок обхода. LinkedHashMap расширяет HashMap, добавляя сквозной двусвязный список между нодами, что сохраняет порядок вставки или порядок доступа ($O(1)$) и позволяет реализовать LRU-кэш. TreeMap базируется на красно-чёрном дереве, гарантирует сортировку ключей с логарифмической сложностью $O(\log N)$ и реализует NavigableMap, но не поддерживает null-ключи и определяет равенство ключей строго по compareTo() == 0, игнорируя equals()».

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

1. Почему в многопоточном коде чтение `cache.get(key)` из `LinkedHashMap` с `accessOrder = true` может вызвать повреждение данных или зацикливание?

Ответ: При accessOrder = true операция get() не является «чистым» чтением: она перелинковывает ноду в хвост двусвязного списка (before и after ссылки), изменяя внутреннее состояние структуры и инкрементируя modCount. При параллельных вызовах get() без блокировок указатели списка могут закольцеваться, приводя к бесконечному циклу ядра процессора (100% CPU) или ConcurrentModificationException.

2. В каком случае обход `LinkedHashMap` будет работать в разы быстрее обхода `HashMap` при одинаковом количестве элементов?

Ответ: В случае так называемой «разреженной» мапы (sparse map), когда начальная емкость (capacity) была инициализирована значительно больше числа реально сохраненных элементов (например, capacity 1 000 000, а элементов всего 1 000). Итератор HashMap вынужден последовательно проверить все 1 000 000 ячеек массива бакетов ($O(\text{capacity} + N)$), вызывая огромное количество Cache Misses, тогда как LinkedHashMap просто пройдет по цепочке нод ровно за 1 000 шагов ($O(N)$).

3. Почему `TreeMap` не позволяет вставить ключ `null`, а `HashMap` позволяет?

Ответ: HashMap обрабатывает null особым образом: если ключ null, хэш принудительно приравнивается к 0, и запись всегда помещается в бакет с индексом 0. В TreeMap при вставке каждого ключа вызывается метод compareTo(k) или comparator.compare(k1, k2). Поскольку у null невозможно вызвать метод compareTo(), JVM выбрасывает NullPointerException. (Единственное исключение — использование кастомного компаратора, явно поддерживающего null, например Comparator.nullsFirst(...)).

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

❌ Утверждение, что TreeMap быстрее HashMap: TreeMap работает за $O(\log N)$ и имеет худшую локальность кэша; HashMap работает за $O(1)$ и в среднем значительно быстрее.
❌ Попытка использовать LinkedHashMap для сортировки ключей: LinkedHashMap сохраняет порядок вставки или доступа, но не умеет сортировать по алфавиту/значению ключей — для этого нужен TreeMap.
❌ Забывать, что TreeMap игнорирует equals(): Несогласованность compareTo и equals ведет к перезаписи или исчезновению бизнес-объектов.
❌ Использование TreeMap.putFirst() в Java 21: Выбросит UnsupportedOperationException, так как порядок в дереве определяется исключительно ключами.

🟢 Junior Level

1. Сравнительная таблица характеристик

2. Разница в порядке обхода (Code Demo)

🟡 Middle Level

1. Архитектура структур данных под капотом

2. Парадокс скорости итерации: HashMap против LinkedHashMap

3. Режимы упорядочивания LinkedHashMap и LRU-кэш

🔴 Senior Level

1. Детальное сравнение расхода памяти (Memory Footprint)

2. Специфика Java 21: SequencedMap

3. Ловушка равенства: hashCode/equals против compareTo