LinkedHashSet/LinkedHashMap

1. Czym są LinkedHashSet i LinkedHashMap?

W standardowej bibliotece Javy istnieje kilka implementacji kolekcji Set i Map. Najbardziej znane — to HashSet i HashMap. Struktury te zapewniają szybki dostęp do elementów dzięki haszowaniu, ale nie gwarantują żadnego porządku podczas iteracji elementów. Gdy ważna jest kolejność przechodzenia — z pomocą przychodzą LinkedHashSet i LinkedHashMap.

• LinkedHashSet — to Set, który pamięta kolejność dodawania elementów.
• LinkedHashMap — to Map, która pamięta kolejność dodawania par klucz–wartość (lub, opcjonalnie, kolejność dostępu).

Są zaimplementowane jak „zwykłe” HashSet/HashMap, ale uzupełnione listą dwukierunkową do przechowywania porządku elementów.

2. Kolejność wstawiania i kolejność dostępu

Kolejność wstawiania

Domyślnie LinkedHashSet i LinkedHashMap gwarantują, że podczas iteracji elementy zwracane są w takiej kolejności, w jakiej zostały dodane (for-each/iterator).

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
for (String s : set) {
    System.out.println(s);
}
// Wypisze: 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));
}
// Wypisze: 1 -> one, 2 -> two, 3 -> three

Kolejność dostępu (tylko dla LinkedHashMap)

U LinkedHashMap jest tryb porządku według ostatniego dostępu (access order). Jeśli przy tworzeniu mapy przekażesz true jako trzeci parametr konstruktora, to przy każdym odwołaniu do elementu (get/put) będzie on przenoszony na koniec listy.

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); // Dostęp do klucza 2

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// Wypisze: 1 3 2 (2 — ostatni, ponieważ uzyskano do niego dostęp)

Cache LRU przez removeEldestEntry

Główny atut LinkedHashMap — prosta implementacja cache’u LRU (Least Recently Used, „najdawniej używany”). Wystarczy nadpisać metodę removeEldestEntry(Map.Entry<K,V> eldest): jeśli zwróci true, najstarszy element zostanie usunięty podczas dodawania nowego.

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

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true — porządek według dostępu
        this.maxSize = maxSize;
    }

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

// Użycie:
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // Robimy 1 najbardziej "świeżym"
cache.put(4, "four"); // Usunięty zostanie 2 (najstarszy)
System.out.println(cache.keySet()); // [3, 1, 4]

3. Koszt pamięci i wydajności: LinkedHashSet/LinkedHashMap vs HashSet/HashMap

Jak to działa

W środku — prawie jak w zwykłych HashSet/HashMap, ale każdy element jest dodatkowo przechowywany w liście dwukierunkowej. Ta dodatkowa struktura „pamięta” kolejność dodawania/dostępu.

Koszt pamięci

Z powodu odwołań prev/next na każdym ogniwie wymagane jest więcej pamięci. Dla milionów elementów jest to zauważalne; dla typowych zadań — uzasadniona cena za deterministyczny porządek.

Koszt wydajności

Podstawowe operacje dodawania/wyszukiwania/usuwania pozostają amortyzacyjnie O(1). Iteracja jest nieco wolniejsza z powodu przechodzenia listy, ale w większości przypadków różnica jest minimalna. Z kolei scenariusz „usuń najstarszy” (LRU) realizuje się bardzo wydajnie, ponieważ „najstarszy” element zawsze znajduje się na początku listy.

Podsumowując: jeśli kolejność jest ważna — wybieraj LinkedHashSet/LinkedHashMap. Jeśli chcesz oszczędzić pamięć i kolejność nie jest potrzebna — wystarczy HashSet/HashMap.

4. Cache, deterministyczny wynik, stabilne testy

Cache (LRU)

LinkedHashMap — idealna podstawa do cache’y z limitem rozmiaru i automatycznym usuwaniem „starych” elementów. Stosowana w bibliotekach/frameworkach, przy pracy z plikami, obrazami, wynikami obliczeń.

Deterministyczny wynik

Do raportów, eksportu, serializacji, gdzie krytyczna jest przewidywalna reprezentacja danych, używaj LinkedHashSet/LinkedHashMap. To szczególnie ważne dla testów — kolejność nie „tańczy” od uruchomienia do uruchomienia.

Stabilne testy

W testach jednostkowych często porównuje się oczekiwane kolekcje z otrzymanymi. Jeśli kolejność nie jest gwarantowana, testy mogą „flapować”. Z „linked”-implementacjami — deterministyczność zapewnia stabilność.

Przykład: porównanie HashMap i 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());   // Kolejność może być dowolna!
System.out.println(linkedMap.keySet()); // Zawsze 1, 2, 3, 4, 5

5. LinkedList vs ArrayDeque dla kolejek

LinkedList

• Implementuje interfejsy List, Deque, Queue.
• Lista dwukierunkowa: szybkie wstawienia/usunięcia na początku i na końcu.
• Można używać jako kolejki (FIFO), stosu (LIFO), kolejki dwukierunkowej.

ArrayDeque

• Implementuje Deque, Queue (ale nie List).
• Opiera się na tablicy, automatycznie się rozszerza.
• Często szybszy od LinkedList dla operacji kolejki/stosu; mniejsze narzuty.
• Nie obsługuje elementu null.

Kiedy czego używać?

• Kolejki i stosy — prawie zawsze ArrayDeque.
• Dużo wstawek/usunięć w środku i potrzebna jest też lista — LinkedList.
• Set/Map z kolejnością — LinkedHashSet/LinkedHashMap.

Przykład: kolejka zadań

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

Przykład: stos

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

Wniosek:
— Dla kolejek i stosów — ArrayDeque.
— Dla listy z częstymi wstawkami w środku — LinkedList.
— Dla Set/Map z kolejnością — LinkedHashSet/LinkedHashMap.

6. Typowe błędy podczas pracy z LinkedHashSet/LinkedHashMap

Błąd nr 1: Oczekiwanie, że HashSet/HashMap zachowują kolejność.
HashSet/HashMap nie gwarantują kolejności. Jeśli jest ważna — użyj LinkedHashSet/LinkedHashMap.

Błąd nr 2: LinkedHashMap jako cache bez nadpisania removeEldestEntry.
Dla LRU trzeba nadpisać removeEldestEntry, inaczej mapa będzie rosła bez ograniczeń.

Błąd nr 3: Używanie LinkedList do kolejek/stosów bez potrzeby.
W większości przypadków ArrayDeque jest szybszy i bardziej oszczędny.

Błąd nr 4: Oczekiwanie sortowania od LinkedHashMap.
LinkedHashMap zachowuje kolejność dodawania/dostępu, ale nie sortuje po kluczu. Do sortowania — TreeMap.

Błąd nr 5: Dodawanie null do ArrayDeque.
ArrayDeque nie obsługuje elementów null — będzie NullPointerException.

Błąd nr 6: Porównywanie kolekcji bez uwzględnienia kolejności.
Porównując LinkedHashSet/LinkedHashMap ze zwykłymi HashSet/HashMap, uwzględnij różnice w kolejności elementów.