📦 Розділ 4 · Питання #15

В чому різниця між HashMap, LinkedHashMap та TreeMap

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

📦 Колекції 📄 Вихідний Markdown

🟢 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) кеш у кілька рядків:

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):

  1. HashMap$Node<K,V>:
    • Заголовок (12 байтів) + hash (4 байти) + 3 посилання (key, value, next по 4 байти = 12 байтів) + padding (4 байти) = 32 байти.
  2. LinkedHashMap$Entry<K,V>:
    • Розширює HashMap$Node, додаючи 2 посилання (before, after по 4 байти = 8 байтів).
    • $32 + 8 =$ 40 байтів.
  3. 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, і запис завжди потрапляє в нульовий бакет. У 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, оскільки порядок у дереві визначається виключно самими ключами.

Пов’язані теми