LinkedHashSet/LinkedHashMap

1. Що таке LinkedHashSet і LinkedHashMap?

У стандартній бібліотеці Java є кілька реалізацій колекцій Set і Map. Найвідоміші — HashSet і HashMap. Ці структури забезпечують швидкий доступ до елементів за хешем, але не гарантують жодного порядку під час перебирання елементів. Коли важливий порядок перебирання, на допомогу приходять LinkedHashSet і LinkedHashMap.

• LinkedHashSet — це Set, який памʼятає порядок додавання елементів.
• LinkedHashMap — це Map, яка памʼятає порядок додавання пар ключ–значення (або, за бажанням, порядок доступу).

Вони реалізовані як «звичайні» HashSet/HashMap, але доповнені двозвʼязним списком для збереження порядку елементів.

2. Порядок додавання і порядок доступу

Порядок додавання

За замовчуванням LinkedHashSet і LinkedHashMap гарантують, що під час перебирання елементи повертаються у тому порядку, в якому їх було додано (for-each/ітератор).

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
for (String s : set) {
    System.out.println(s);
}
// Виведе: A B C

Map<Integer, String> map = new LinkedHashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
for (Integer key : map.keySet()) {
    System.out.println(key + " -> " + map.get(key));
}
// Виведе: 1 -> one, 2 -> two, 3 -> three

Порядок доступу (лише для LinkedHashMap)

У LinkedHashMap є режим упорядкування за останнім доступом (access order). Якщо під час створення мапи передати true третім параметром конструктора, то під час кожного звернення до елемента (get/put) він переміщується в кінець списку.

Map<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);
lruMap.put(1, "one");
lruMap.put(2, "two");
lruMap.put(3, "three");

lruMap.get(2); // Доступ до ключа 2

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// Виведе: 1 3 2 (2 — останній, оскільки до нього звернулися)

LRU‑кеш через removeEldestEntry

Ключова перевага LinkedHashMap — проста реалізація LRU‑кеша (Least Recently Used, «той, що найдовше не використовувався»). Достатньо перевизначити метод removeEldestEntry(Map.Entry<K,V> eldest). Якщо він повертає true, найстаріший елемент видаляється під час додавання нового.

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true — порядок доступу
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// Використання:
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // Робимо 1 найсвіжішим
cache.put(4, "four"); // Буде видалено 2 (найстаріший)
System.out.println(cache.keySet()); // [3, 1, 4]

3. Вартість за памʼяттю і швидкодією: LinkedHashSet/LinkedHashMap vs HashSet/HashMap

Як це влаштовано

Усередині — майже як у звичайних HashSet/HashMap, але кожен елемент зберігається ще й у двозвʼязному списку. Ця додаткова структура «памʼятає» порядок додавання/доступу.

Витрати памʼяті

Через посилання prev/next на кожній ланці потрібно більше памʼяті. Для мільйонів елементів це помітно; для типових завдань — виправдана плата за детермінований порядок.

Швидкодія

Базові операції додавання/пошуку/видалення залишаються амортизовано O(1). Перебирання відбувається дещо повільніше через обхід списку, але в більшості випадків різниця мінімальна. А сценарій «видалити найстаріший» (LRU) реалізується дуже ефективно, адже «найстаріший» елемент завжди на початку списку.

Підсумок: якщо порядок важливий — обирайте LinkedHashSet/LinkedHashMap. Якщо потрібно заощадити памʼять і порядок не потрібен — достатньо HashSet/HashMap.

4. Кешування, детерміноване виведення, стабільні тести

Кешування (LRU)

LinkedHashMap — ідеальна основа для кешів із обмеженням розміру та автоматичним видаленням «старих» елементів. Використовується в бібліотеках/фреймворках, під час роботи з файлами, зображеннями, результатами обчислень.

Детерміноване виведення

Для звітів, експорту, серіалізації, де критично важливе передбачуване подання даних, використовуйте LinkedHashSet/LinkedHashMap. Це особливо важливо для тестів — порядок не «стрибає» від запуску до запуску.

Стабільні тести

У юніт‑тестах часто порівнюють очікувані колекції з отриманими. Якщо порядок не гарантовано, тести можуть бути нестабільними. Із «linked»-реалізаціями детермінованість забезпечує стабільність.

Приклад: порівняння HashMap і LinkedHashMap

Map<Integer, String> hashMap = new HashMap<>();
Map<Integer, String> linkedMap = new LinkedHashMap<>();

for (int i = 1; i <= 5; i++) {
    hashMap.put(i, "val" + i);
    linkedMap.put(i, "val" + i);
}

System.out.println(hashMap.keySet());   // Порядок може бути довільним!
System.out.println(linkedMap.keySet()); // Завжди 1, 2, 3, 4, 5

5. LinkedList vs ArrayDeque для черг

LinkedList

• Реалізує інтерфейси List, Deque, Queue.
• Двозвʼязний список: швидкі вставки/видалення на початку та в кінці.
• Можна використовувати як чергу (FIFO), стек (LIFO), двосторонню чергу.

ArrayDeque

• Реалізує Deque, Queue (але не List).
• Побудований на масиві, автоматично розширюється.
• Часто швидший за LinkedList для операцій черги/стека; менші накладні витрати.
• Не підтримує елемент null.

Коли що використовувати?

• Черги та стеки — майже завжди ArrayDeque.
• Багато вставок/видалень у середині і водночас потрібен список — LinkedList.
• Set/Map із порядком — LinkedHashSet/LinkedHashMap.

Приклад: черга завдань

Queue<String> queue = new ArrayDeque<>();
queue.add("task1");
queue.add("task2");
System.out.println(queue.poll()); // task1

Приклад: стек

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop()); // second

Висновок:
— Для черг і стеків — ArrayDeque.
— Для списку з частими вставками в середині — LinkedList.
— Для Set/Map із порядком — LinkedHashSet/LinkedHashMap.

6. Типові помилки під час роботи з LinkedHashSet/LinkedHashMap

Помилка № 1: Очікування, що HashSet/HashMap зберігають порядок.
HashSet/HashMap не гарантують порядок. Якщо він важливий — використовуйте LinkedHashSet/LinkedHashMap.

Помилка № 2: LinkedHashMap для кешу без перевизначення removeEldestEntry.
Для LRU потрібно перевизначити removeEldestEntry, інакше мапа зростатиме без обмежень.

Помилка № 3: Використання LinkedList для черг/стеків без потреби.
У більшості випадків ArrayDeque швидший і економніший.

Помилка № 4: Очікування сортування від LinkedHashMap.
LinkedHashMap зберігає порядок додавання/доступу, але не сортує за ключем. Для сортування — TreeMap.

Помилка № 5: Додавання null до ArrayDeque.
ArrayDeque не підтримує елементи null — буде NullPointerException.

Помилка № 6: Порівняння колекцій без урахування порядку.
Порівнюючи LinkedHashSet/LinkedHashMap зі звичайними HashSet/HashMap, ураховуйте відмінності в порядку елементів.