Java LinkedHashSet-Klasse | W3Docs Learn Java

LinkedHashSet<E> ist HashSet<E> mit einem zusätzlichen Versprechen: Beim Iterieren erhält man die Elemente in der Reihenfolge, in der sie zuerst eingefügt wurden. Die Hash-Tabellen-Mechanik ist identisch — gleiche Buckets, gleicher Lastfaktor, gleiche O(1)-Operationen add, remove, contains — aber jeder Eintrag trägt zwei zusätzliche Zeiger (before, after), die die Einträge beim Hinzufügen zu einer doppelt verketteten Liste verbinden. Die Iteration folgt dieser Liste, nicht dem Bucket-Array.

Wenn man Hash-Set-Performance und eine deterministische, vorhersagbare Iterationsreihenfolge benötigt, ist LinkedHashSet die Antwort. Es ist in den Fällen, in denen die undefinierte Reihenfolge von HashSet Probleme bereitet hat, so gut wie ein kostenloses Upgrade.

Die "First-insertion-wins"-Regel

Die Reihenfolge wird beim ersten Einfügen eines Elements festgelegt. Ein bereits vorhandenes Element erneut hinzuzufügen, verschiebt es nicht:

Set<String> s = new LinkedHashSet<>();
s.add("a");
s.add("b");
s.add("c");
s.add("a");   // already present — returns false, order unchanged
System.out.println(s);   // [a, b, c]

Das macht es zum richtigen Werkzeug für "die Reihenfolge, in der Tags ankamen, merken" oder "eindeutige Ereignisse in zeitlicher Reihenfolge protokollieren." Wenn man ein Element entfernt und es erneut einfügt, wird es ans Ende der Liste gesetzt — die Position war an das aktuelle Einfügen gebunden, und das neue ist das einzige verbleibende.

Die Kosten: Zeiger und Zeiger

Die zusätzliche Sortierungsmechanik hat ihren Preis. Jeder Eintrag speichert nicht nur (hash, key, next-in-bucket) wie HashSet, sondern (hash, key, next-in-bucket, before, after). Das sind zwei zusätzliche Referenzen pro Element — ungefähr 16 Bytes extra auf einer 64-Bit-JVM. Bei einem Set mit 10 Millionen Long-Werten sind das rund 160 MB extra. Für den größten Teil des Anwendungscodes ist das nichts; bei Datenstrukturen in Cache-Größe spielt es jedoch eine Rolle.

Im Gegenzug erhält man O(1) für jede Operation (wie bei HashSet) plus eine stabile Iterationsreihenfolge, die weder vom Lastfaktor, noch vom Rehash, der Hash-Verteilung oder der JVM-Version abhängt.

Iterationskosten sind proportional zur Größe, nicht zur Kapazität

Es gibt einen subtilen Vorteil gegenüber HashSet: Das Durchlaufen eines LinkedHashSet folgt der verketteten Liste, sodass genau size Einträge besucht werden. Das Iterieren eines HashSet durchläuft jeden Bucket, also werden ungefähr capacity Slots besucht — einschließlich leerer. Bei einem spärlich befüllten Set kann das ein erheblicher Unterschied sein. Wenn man ein Set aufbaut, es weit über die zu behaltenden Elemente hinaus vergrößert und dann häufig iteriert, kann LinkedHashSet tatsächlich schneller iterieren.

Wann man es wählen sollte

Der Entscheidungsfluss:

Reihenfolge spielt keine Rolle, schnelle Mitgliedschaftsprüfung wird benötigt → HashSet. Kleiner, einfacher.
Einfügereihenfolge soll beibehalten werden → LinkedHashSet. Gleiche Geschwindigkeit für add/contains, vorhersagbare Iteration.
Sortierte Reihenfolge wird gewünscht → TreeSet. Anderer Algorithmus, Log-Zeit-Operationen.

Der häufigste Grund für LinkedHashSet ist defensiv: Man baut eine öffentliche API, die ein Set zurückgibt, und möchte nicht, dass Aufrufer von der willkürlichen Reihenfolge von HashSet abhängen. Ein LinkedHashSet ist das Freundlichste, was man zurückgeben kann — es hat denselben Vertrag wie ein Set, aber die Iteration ist reproduzierbar über Läufe und JVMs hinweg, was die für Benutzer sichtbare Ausgabe stabil und Tests leichter schreibbar macht.

Ein ausgearbeitetes Beispiel: eindeutige Tags in Ankunftsreihenfolge

Das folgende Programm baut zwei Sets aus demselben Strom von Tag-Eingaben: eines mit HashSet, eines mit LinkedHashSet. Die HashSet-Iterationsreihenfolge hängt von der JVM ab (sie ist stabil-aber-willkürlich für eine gegebene JVM); die LinkedHashSet-Reihenfolge ist genau die Reihenfolge, in der die eindeutigen Elemente zuerst erschienen. Dann zeigt es die "Entfernen und erneut Einfügen"-Regel und baut abschließend einen ordnungserhaltenden Deduplikator, der nur zwei Zeilen lang ist.

java— editable, runs on the server

import java.util.*;
import java.util.stream.*;

public class LinkedHashSetShowcase {
  public static void main(String[] args) {
    String[] events = { "login", "view", "purchase", "view", "logout", "login", "view" };

Set<String> hashed = new HashSet<>();
    Set<String> linked = new LinkedHashSet<>();
    for (String e : events) { hashed.add(e); linked.add(e); }

System.out.println("input:    " + Arrays.toString(events));
    System.out.println("HashSet:        " + hashed + "   (order may be anything)");
    System.out.println("LinkedHashSet:  " + linked + "   (first-insertion order)");

// --- The 'first-insertion wins' rule ---
    Set<String> demo = new LinkedHashSet<>();
    demo.add("a"); demo.add("b"); demo.add("c");
    demo.add("a");                 // already there — order unchanged
    System.out.println("\nre-add 'a':       " + demo);
    demo.remove("a"); demo.add("a"); // gone then back — moves to end
    System.out.println("remove+re-add 'a': " + demo);

// --- Order-preserving deduplicator in two lines ---
    List<Integer> noisy = List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);
    List<Integer> deduped = noisy.stream()
        .collect(Collectors.toCollection(LinkedHashSet::new))
        .stream().toList();
    System.out.println("\nnoisy:    " + noisy);
    System.out.println("deduped:  " + deduped + "   (order preserved)");

// --- Iteration cost: LinkedHashSet visits size entries, not capacity slots ---
    Set<Integer> big = new LinkedHashSet<>(2_000_000); // huge capacity, few elements
    for (int i = 0; i < 10; i++) big.add(i);
    long t0 = System.nanoTime();
    int sum = 0;
    for (int x : big) sum += x;
    long t1 = System.nanoTime();
    System.out.println("\nsum of " + big.size() + " elements in a " + 2_000_000
        + "-bucket set: " + sum + "  in " + (t1 - t0) + " ns");
  }
}

Was man aus dem Lauf ablesen kann:

Das LinkedHashSet druckte die eindeutigen Ereignisse in der Reihenfolge aus, in der sie zuerst erschienen. Das HashSet druckte sie in einer ganz anderen Reihenfolge — was auch immer das Bucket-Layout vorgab.
Das erneute Einfügen von "a" änderte die Reihenfolge nicht. Das Entfernen und erneute Einfügen verschob es ans Ende. Das erste Einfügen verankert die Position.
Der ordnungserhaltende Deduplikator ist ein Einzeiler, sobald man den Trick kennt: In ein LinkedHashSet sammeln, dann zurück in eine Liste.
Der Scan der 10 Elemente durch ein LinkedHashSet mit 2 000 000 Buckets durchlief genau 10 Einträge; ein HashSet derselben Form hätte jeden leeren Bucket dazwischen gescannt.

Was als nächstes kommt

Die dritte Standard-Set-Implementierung bietet etwas, das weder HashSet noch LinkedHashSet kann: sortierte Iteration und die Möglichkeit, Bereichsabfragen zu stellen wie "jedes Tag zwischen a und m." Als nächstes kommt TreeSet.

Übungen

Übung

Was bietet `LinkedHashSet` im Vergleich zu einem einfachen `HashSet`?

Iteration in der Reihenfolge, in der Elemente zuerst eingefügt wurden, auf Kosten von zwei zusätzlichen Referenzen pro EintragSortierte Iteration gemäß der natürlichen Ordnung des ElementsThread-sichere Operationen mit internen SperrenO(log n)-Suche statt O(1), mit stabiler Reihenfolge als Nebeneffekt