Java Set Interface

Set<E> ist Collection<E> mit einer zusätzlichen Regel: keine Duplikate. Das Interface selbst fügt kaum neue Methoden hinzu — es erbt add, remove, contains, size, iterator und den Rest. Was es ändert, sind die Versprechen dieser Methoden: add(e) gibt false zurück (und ändert nichts), wenn ein gleiches Element bereits im Set vorhanden ist; zwei Sets sind equals, wenn sie dieselben Elemente enthalten, unabhängig von der Reihenfolge; und hashCode ist die Summe der Element-Hashwerte, sodass gleiche Sets stets übereinstimmen.

Dieser kleine Vertrag — „Elemente sind eindeutig" — ist genau das, was man für Mitgliedschaftstests, Deduplizierung, Schnittmengen/Vereinigungen und tausend andere Muster braucht, die sich mit einer List schlecht lesen.

Was als Duplikat gilt

Ein Set entscheidet über Duplikate anhand von equals (und bei hash-basierten Sets anhand von hashCode als Bucket-Funktion). Es handelt sich nicht um Zeigergleichheit und nicht um „sieht beim Drucken gleich aus." Wenn Sie eine eigene Klasse in ein Set legen, müssen Sie beide Methoden gemeinsam überschreiben; das Kapitel equals und hashCode behandelt den Vertrag.

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("java");      // add returns false; the set still has one element
tags.add(new String("java")); // also false — equals, not reference

Eine häufige Falle: veränderliche Elemente speichern und sie dann mutieren, während sie in einem hash-basierten Set leben. Der Hashwert des Elements ändert sich, das Set sucht es im falschen Bucket, und contains fängt an zu lügen. Die Regel: Wenn Sie ein Objekt in ein Hash-Set legen, behandeln Sie es ab diesem Zeitpunkt als effektiv unveränderlich. TreeSet hat dieselbe Falle mit compareTo.

Die vier Standard-Implementierungen

java.util liefert vier Implementierungen von Set, die nahezu jeden Anwendungsfall abdecken:

Die ersten drei werden in den nächsten drei Kapiteln behandelt; EnumSet wird später im Buch zusammen mit EnumMap vorgestellt.

Die Mengenoperationen: Vereinigung, Schnittmenge, Differenz

Ein Set erbt vier Mengenoperationen von Collection, und bei einem Set haben sie die Bedeutung aus der Mengenlehre:

• addAll(other) — Vereinigung (in-place). Nach dem Aufruf enthält a jedes Element beider Seiten.
• retainAll(other) — Schnittmenge (in-place). Nach dem Aufruf enthält a nur Elemente, die auch in other waren.
• removeAll(other) — Differenz (in-place). Nach dem Aufruf enthält a nur Elemente, die nicht in other waren.
• containsAll(other) — Teilmengentest. Gibt true zurück, wenn jedes Element von other in a enthalten ist.

Diese Operationen verändern den Empfänger. Wenn Sie eine nicht-destruktive Version benötigen, kopieren Sie zuerst: Set<E> u = new HashSet<>(a); u.addAll(b);.

Gleichheit und Hashcodes von Sets

Der Set-Vertrag für equals ist ungewöhnlich: Zwei Sets sind gleich, wenn sie dieselben Elemente enthalten, unabhängig von Reihenfolge oder Implementierungstyp. Ein HashSet, ein LinkedHashSet und ein TreeSet mit denselben Elementen sind alle untereinander gleich.

Set<Integer> a = new HashSet<>(List.of(1, 2, 3));
Set<Integer> b = new TreeSet<>(List.of(3, 2, 1));
System.out.println(a.equals(b));   // true

Deshalb können die Mengenoperationen und die unveränderlichen Factory-Methoden frei zwischen Implementierungen wechseln — nur die Regel „gleiche Elemente" wird beachtet.

Read-only- und unveränderliche Factories

Seit Java 9 ist Set.of(...) der einfachste Weg, um ein kleines, festes Set zu erstellen:

Set<String> primary = Set.of("red", "green", "blue");

Set.of gibt ein unveränderliches Set zurück, das keine Null-Elemente akzeptiert und bei einem Duplikat zur Konstruktionszeit eine Exception wirft. Für einen defensiven Snapshot eines bestehenden Sets verwenden Sie Set.copyOf(existing) — ebenfalls unveränderlich, ebenfalls keine Nulls.

Für eine Sicht, die Mutationen verbirgt (das Original kann noch verändert werden, aber Aufrufer können nichts über die Sicht hinzufügen), verwenden Sie Collections.unmodifiableSet(s). Das Kapitel über unveränderliche Collections weiter hinten in diesem Teil erläutert, wann welche Variante zu wählen ist.

Ein Praxisbeispiel: Deduplizierung, Mengenalgebra und Reihenfolge

Das folgende Programm verwendet alle vier Implementierungen, demonstriert die Mengenoperationen mit echten Daten und zeigt, wie sich die Iterationsreihenfolge zwischen HashSet, LinkedHashSet und TreeSet unterscheidet.

Was man aus dem Programmablauf mitnimmt:

• add hat für jedes doppelte \"java\" false zurückgegeben — so schreibt man einen Deduplizierer in zwei Zeilen.
• Vereinigung, Schnittmenge und Differenz sind je ein addAll/retainAll/removeAll — zuerst kopieren, wenn das Original erhalten bleiben soll.
• Die drei Implementierungen enthalten dieselben Elemente und vergleichen sich als gleich, iterieren aber in sehr unterschiedlichen Reihenfolgen. Wählen Sie die Implementierung nach der benötigten Reihenfolge, nicht aus Gewohnheit.

Was kommt als Nächstes

Die gebräuchlichste Set-Implementierung — und die, die man standardmäßig verwendet, sofern kein besonderer Grund dagegen spricht — ist hash-tabellenbasiert. HashSet kommt als Nächstes; wir behandeln den Ladefaktor, das Rehashing und was „nahezu konstante Zeit" in der Praxis bedeutet.

Übungen