LinkedHashSet/LinkedHashMap

1. Was sind LinkedHashSet und LinkedHashMap?

In der Java-Standardbibliothek gibt es mehrere Implementierungen von Set- und Map-Collections. Die bekanntesten sind HashSet und HashMap. Diese Strukturen bieten schnellen Zugriff per Hash, garantieren aber keine bestimmte Reihenfolge beim Iterieren. Wenn die Iterationsreihenfolge wichtig ist, helfen LinkedHashSet und LinkedHashMap.

• LinkedHashSet ist ein Set, das sich die Einfügereihenfolge der Elemente merkt.
• LinkedHashMap ist eine Map, die sich die Einfügereihenfolge der Schlüssel–Wert-Paare merkt (oder optional die Zugriffsreihenfolge).

Sie sind wie „gewöhnliche“ HashSet/HashMap implementiert, werden jedoch durch eine doppelt verkettete Liste ergänzt, um die Reihenfolge der Elemente zu speichern.

2. Einfüge- und Zugriffsreihenfolge

Einfügereihenfolge

Standardmäßig garantieren LinkedHashSet und LinkedHashMap, dass beim Iterieren die Elemente in der Reihenfolge zurückgegeben werden, in der sie hinzugefügt wurden (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);
}
// Ausgabe: 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));
}
// Ausgabe: 1 -> one, 2 -> two, 3 -> three

Zugriffsreihenfolge (nur für LinkedHashMap)

LinkedHashMap besitzt einen Modus der letzten Zugriffe (access order). Wenn man beim Erzeugen der Map true als dritten Konstruktor-Parameter übergibt, wird jedes Element bei einem Zugriff (get/put) ans Ende der Liste verschoben.

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); // Zugriff auf Schlüssel 2

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// Ausgabe: 1 3 2 (2 ist der letzte, weil darauf zugegriffen wurde)

LRU-Cache über removeEldestEntry

Der wichtigste „Clou“ von LinkedHashMap ist die einfache Implementierung eines LRU-Caches (Least Recently Used, „am längsten nicht verwendet“). Es genügt, die Methode removeEldestEntry(Map.Entry<K,V> eldest) zu überschreiben: Gibt sie true zurück, wird beim Hinzufügen eines neuen Elements das „älteste“ Element entfernt.

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

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true: Zugriffsreihenfolge
        this.maxSize = maxSize;
    }

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

// Verwendung:
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // Macht 1 zum "frischesten"
cache.put(4, "four"); // 2 wird entfernt (der älteste)
System.out.println(cache.keySet()); // [3, 1, 4]

3. Speicher- und Laufzeitkosten: LinkedHashSet/LinkedHashMap vs HashSet/HashMap

Wie es aufgebaut ist

Intern – fast wie bei „normalen“ HashSet/HashMap –, aber jedes Element wird zusätzlich in einer doppelt verketteten Liste gespeichert. Diese zusätzliche Struktur „merkt sich“ die Einfüge- bzw. Zugriffsreihenfolge.

Speicherbedarf

Wegen der Referenzen prev/next an jedem Knoten wird mehr Speicher benötigt. Bei Millionen von Elementen ist das spürbar; für typische Aufgaben ist es ein gerechtfertigter Preis für eine deterministische Reihenfolge.

Laufzeitkosten

Die Basisoperationen Einfügen/Suchen/Löschen bleiben amortisiert O(1). Das Iterieren ist etwas langsamer wegen der Listendurchläufe, aber meist ist der Unterschied minimal. Das Szenario „den ältesten löschen“ (LRU) ist sehr effizient, da das „älteste“ Element immer am Kopf der Liste steht.

Fazit: Wenn die Reihenfolge wichtig ist – wählen Sie LinkedHashSet/LinkedHashMap. Wenn Speicher gespart werden muss und die Reihenfolge egal ist – genügt HashSet/HashMap.

4. Caching, deterministische Ausgabe, stabile Tests

Caching (LRU)

LinkedHashMap ist eine ideale Grundlage für Caches mit Größenlimit und automatischem Entfernen „alter“ Einträge. Sie wird in Bibliotheken/Frameworks, bei der Arbeit mit Dateien, Bildern und Rechenergebnissen eingesetzt.

Deterministische Ausgabe

Für Berichte, Export, Serialisierung – überall, wo eine vorhersagbare Darstellung der Daten kritisch ist – verwenden Sie LinkedHashSet/LinkedHashMap. Das ist besonders für Tests wichtig – die Reihenfolge „springt“ nicht von Lauf zu Lauf.

Stabile Tests

In Unit-Tests vergleicht man häufig erwartete Collections mit erhaltenen. Ist die Reihenfolge nicht garantiert, können Tests „flappen“. Mit den „linked“-Implementierungen sorgt die Determiniertheit für Stabilität.

Beispiel: Vergleich HashMap und 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());   // Reihenfolge kann beliebig sein!
System.out.println(linkedMap.keySet()); // Immer 1, 2, 3, 4, 5

5. LinkedList vs ArrayDeque für Queues

LinkedList

• Implementiert die Interfaces List, Deque, Queue.
• Doppelt verkettete Liste: schnelle Einfügungen/Löschungen am Anfang und am Ende.
• Kann als Queue (FIFO), Stack (LIFO) und doppelt-gerichtete Queue verwendet werden.

ArrayDeque

• Implementiert Deque, Queue (aber nicht List).
• Basiert auf einem Array, wächst automatisch.
• Oft schneller als LinkedList für Queue-/Stack-Operationen; geringerer Overhead.
• Unterstützt kein Element null.

Wann was verwenden?

• Queues und Stacks – fast immer ArrayDeque.
• Viele Einfügungen/Löschungen in der Mitte und zusätzlich eine Liste nötig – LinkedList.
• Set/Map mit Reihenfolge – LinkedHashSet/LinkedHashMap.

Beispiel: Aufgaben-Queue

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

Beispiel: Stack

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

Fazit:
– Für Queues und Stacks – ArrayDeque.
– Für Listen mit häufigen Einfügungen in der Mitte – LinkedList.
– Für Set/Map mit Reihenfolge – LinkedHashSet/LinkedHashMap.

6. Häufige Fehler bei der Arbeit mit LinkedHashSet/LinkedHashMap

Fehler Nr. 1: Erwartung, dass HashSet/HashMap die Reihenfolge bewahren.
HashSet/HashMap garantieren keine Reihenfolge. Wenn sie wichtig ist – verwenden Sie LinkedHashSet/LinkedHashMap.

Fehler Nr. 2: LinkedHashMap als Cache ohne Überschreiben von removeEldestEntry.
Für LRU muss removeEldestEntry überschrieben werden, sonst wächst die Map unbegrenzt.

Fehler Nr. 3: Verwendung von LinkedList für Queues/Stacks ohne Notwendigkeit.
In den meisten Fällen ist ArrayDeque schneller und sparsamer.

Fehler Nr. 4: Von LinkedHashMap eine Sortierung erwarten.
LinkedHashMap bewahrt Einfüge-/Zugriffsreihenfolge, sortiert aber nicht nach Schlüssel. Zum Sortieren – TreeMap.

Fehler Nr. 5: Hinzufügen von null zu ArrayDeque.
ArrayDeque unterstützt keine Elemente null – es kommt zu NullPointerException.

Fehler Nr. 6: Vergleich von Collections ohne Berücksichtigung der Reihenfolge.
Beim Vergleich von LinkedHashSet/LinkedHashMap mit gewöhnlichen HashSet/HashMap berücksichtigen Sie die unterschiedlichen Elementreihenfolgen.