Zum Inhalt springen

Das Collection-Framework

Ein dynamisches Array haben wir selbst gebaut, Verträge und Implementierungen auseinandergehalten. Jetzt kommt beides zusammen: Das JDK bringt im Package java.util eine ganze Familie von Sammlungen mit – das Collection-Framework. Es besteht aus Interfaces, die festlegen, was eine Sammlung kann, und Klassen, die es umsetzen.

  • die vier Arten von Sammlungen unterscheiden: Liste, Menge, Tabelle, Warteschlange
  • für eine Aufgabe das passende Interface und die passende Implementierung wählen
  • an der ArrayList zeigen, welches Interface welche Fähigkeit hinzufügt
  • veraltete Klassen wie Vector und Stack erkennen und ersetzen

Demo-Code: 21-collections

⤓ demo-collections.zip herunterladen

Der fertige Stand aus der Vorführung – zum Nachlesen, Ausprobieren und Weiterbauen.

Entpacke die ZIP-Datei nach C:\dev\intellij. In IntelliJ: File → Open… → den Ordner 21-collections wählen → OK → Trust Project. Zeigt IntelliJ oben Project JDK is not defined: auf Setup SDK klicken und das JDK 21 wählen.

Enthält: Hierarchie.java, ListenDemo.java, SetDemo.java, MapDemo.java, QueueDemo.java, Texte.java

Art Interface Eigenschaft wichtigste Implementierungen
Liste List<E> Reihenfolge, Zugriff über Position, Duplikate erlaubt ArrayList, LinkedList
Menge Set<E> keine Duplikate HashSet, LinkedHashSet, TreeSet
Tabelle Map<K, V> Schlüssel → Wert, jeder Schlüssel nur einmal HashMap, LinkedHashMap, TreeMap
Warteschlange Queue<E>, Deque<E> Hinzufügen und Herausnehmen an den Enden ArrayDeque, PriorityQueue

Und so hängen die Interfaces zusammen – vereinfacht, rechts jeweils die Klassen:

Iterable<E>
└── Collection<E>
├── SequencedCollection<E> seit Java 21
│ ├── List<E> ArrayList, LinkedList
│ ├── Deque<E> (ist auch eine Queue) ArrayDeque, LinkedList
│ └── SequencedSet<E> LinkedHashSet
│ └── SortedSet<E> TreeSet
├── Set<E> HashSet
└── Queue<E> PriorityQueue
Map<K, V> HashMap
└── SequencedMap<K, V> LinkedHashMap
└── SortedMap<K, V> TreeMap

Eine Map ist keine Collection: Sie enthält keine einzelnen Elemente, sondern Paare aus Schlüssel und Wert. Sie gehört aber zum Framework.

So steht die ArrayList im JDK:

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

List selbst erweitert SequencedCollection, diese Collection und diese Iterable. Jede Stufe fügt etwas hinzu:

Interface verspricht wichtige Methoden
Iterable<E> Man kann über die Elemente laufen. iterator() – und damit die for-each-Schleife
Collection<E> eine Sammlung mit Größe size, isEmpty, contains, add, remove, addAll, clear
SequencedCollection<E> Es gibt einen Anfang und ein Ende. getFirst, getLast, addFirst, addLast, removeFirst, removeLast, reversed
List<E> Jedes Element hat eine Position. get(i), set(i, e), add(i, e), remove(i), indexOf, subList, sort

Dazu kommen:

  • RandomAccess – ein Interface ohne Methoden. Es sagt nur: Der Zugriff über eine Position ist schnell. Die ArrayList hat es, die LinkedList nicht.
  • AbstractList – eine abstrakte Klasse, wie wir sie in Woche 1 geschrieben haben. Sie enthält Code, den viele Listen teilen, und erspart der ArrayList Arbeit.

Das Programm Hierarchie betrachtet dieselbe Liste durch jedes Interface. Über eine Variable vom Typ Collection gibt es kein get(1) – nicht, weil die Liste es nicht könnte, sondern weil der Vertrag Collection es nicht verspricht:

Hierarchie.java
package de.drv.collections;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.SequencedCollection;
/** Eine ArrayList durch die Brille jedes ihrer Interfaces. */
public class Hierarchie {
public static void main(String[] args) {
ArrayList<String> namen = new ArrayList<>();
namen.add("Anna");
namen.add("Ben");
namen.add("Clara");
// Iterable: Man kann darüber laufen – mehr nicht.
Iterable<String> iterable = namen;
for (String name : iterable) {
System.out.print(name + " ");
}
System.out.println();
// Collection: eine Sammlung mit Größe – hinzufügen, entfernen, suchen
Collection<String> collection = namen;
collection.add("Dora");
collection.remove("Ben");
System.out.println(collection.size() + " Namen, Ben dabei? " + collection.contains("Ben"));
// SequencedCollection (seit Java 21): Es gibt einen Anfang und ein Ende.
SequencedCollection<String> sequenced = namen;
sequenced.addFirst("Emil");
System.out.println("erster: " + sequenced.getFirst() + ", letzter: " + sequenced.getLast());
System.out.println("rückwärts: " + sequenced.reversed());
// List: Jedes Element hat eine Position.
List<String> liste = namen;
liste.set(1, "Anja");
liste.add(2, "Bert");
System.out.println(liste + ", Bert an Stelle " + liste.indexOf("Bert"));
}
}
Terminal-Fenster
Anna Ben Clara
3 Namen, Ben dabei? false
erster: Emil, letzter: Dora
rückwärts: [Dora, Clara, Anna, Emil]
[Emil, Anja, Bert, Clara, Dora], Bert an Stelle 2

Deshalb schreibt man links das Interface und rechts die Klasse:

List<String> namen = new ArrayList<>();

Alles, was danach mit namen geschieht, verlässt sich nur auf den Vertrag List. Wer später eine LinkedList braucht, ändert eine Zeile. Dasselbe gilt für Parameter: Eine Methode, die nur über die Elemente läuft, nimmt am besten eine Collection – dann passt jede Liste und jede Menge.

ListenDemo.java
package de.drv.collections;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class ListenDemo {
public static void main(String[] args) {
// Links das Interface, rechts die Implementierung
List<String> namen = new ArrayList<>();
namen.add("Clara");
namen.add("Anna");
namen.add("Ben");
namen.add("Anna"); // doppelt ist erlaubt
System.out.println(namen + " – " + namen.size() + " Einträge");
Collections.sort(namen);
System.out.println("sortiert: " + namen);
// Austauschen: nur die rechte Seite ändert sich
List<String> andere = new LinkedList<>(namen);
andere.remove("Anna"); // entfernt das erste Vorkommen
System.out.println("LinkedList: " + andere);
// Vorsicht bei List<Integer>: remove(int) entfernt eine Position!
List<Integer> zahlen = new ArrayList<>();
zahlen.add(10);
zahlen.add(20);
zahlen.add(30);
zahlen.remove(1); // Position 1 – die 20
zahlen.remove(Integer.valueOf(10)); // der Wert 10
System.out.println("zahlen: " + zahlen);
// List.of: fest und unveränderlich
List<String> fest = List.of("rot", "gelb", "grün");
System.out.println(fest.get(2));
try {
fest.add("blau");
} catch (UnsupportedOperationException e) {
System.out.println("List.of ist unveränderlich: " + e);
}
}
}
Terminal-Fenster
[Clara, Anna, Ben, Anna] – 4 Einträge
sortiert: [Anna, Anna, Ben, Clara]
LinkedList: [Anna, Ben, Clara]
zahlen: [30]
grün
List.of ist unveränderlich: java.lang.UnsupportedOperationException
  • ArrayList ist unser DynamischesArray: schneller Zugriff über die Position. Sie ist fast immer die richtige Wahl.
  • LinkedList verkettet die Elemente einzeln. Einfügen am Anfang ist billig, get(i) dagegen langsam – sie muss vom Anfang aus zählen. In der Praxis selten besser als ArrayList.
  • Collections (mit s) ist eine Hilfsklasse mit statischen Methoden wie sort, reverse, shuffle und max – so wie Arrays für Arrays.
  • remove bei List<Integer> ist eine Falle: remove(1) entfernt die Position 1. Den Wert 1 entfernt remove(Integer.valueOf(1)).
  • List.of(…) liefert eine Liste, die sich nicht ändern lässt. add wirft eine UnsupportedOperationException – die Methode gehört zum Vertrag, wird hier aber nicht unterstützt. Genau wie bei unseren Platzhaltern.
SetDemo.java
package de.drv.collections;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class SetDemo {
record Punkt(int x, int y) {
}
public static void main(String[] args) {
String[] obst = {"Kiwi", "Apfel", "Mango", "Apfel", "Birne", "Kiwi"};
Set<String> hash = new HashSet<>();
Set<String> linked = new LinkedHashSet<>();
Set<String> tree = new TreeSet<>();
for (String sorte : obst) {
hash.add(sorte);
linked.add(sorte);
tree.add(sorte);
}
System.out.println("HashSet: " + hash);
System.out.println("LinkedHashSet: " + linked);
System.out.println("TreeSet: " + tree);
// add sagt, ob das Element neu war
System.out.println("Apfel neu? " + hash.add("Apfel"));
// Ein Set fragt equals und hashCode – ein Record hat beide
Set<Punkt> punkte = new HashSet<>();
punkte.add(new Punkt(1, 2));
punkte.add(new Punkt(1, 2));
System.out.println(punkte.size() + " Punkt: " + punkte);
}
}
Terminal-Fenster
HashSet: [Birne, Kiwi, Apfel, Mango]
LinkedHashSet: [Kiwi, Apfel, Mango, Birne]
TreeSet: [Apfel, Birne, Kiwi, Mango]
Apfel neu? false
1 Punkt: [Punkt[x=1, y=2]]

Alle drei enthalten jede Sorte nur einmal. Sie unterscheiden sich in der Reihenfolge:

Klasse Reihenfolge braucht
HashSet scheinbar zufällig – nach hashCode equals und hashCode
LinkedHashSet in der Reihenfolge des Hinzufügens equals und hashCode
TreeSet sortiert Comparable

Ob ein Element schon drin ist, entscheidet beim HashSet nicht ==, sondern equals und hashCode – deshalb war es in Woche 1 so wichtig, beide passend zu schreiben. Ein Record hat beide von selbst: Die zwei Punkt(1, 2) sind gleich, das Set behält nur einen.

MapDemo.java
package de.drv.collections;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class MapDemo {
public static void main(String[] args) {
// Schlüssel → Wert: Ländercode → Hauptstadt
Map<String, String> hauptstadt = new HashMap<>();
hauptstadt.put("DE", "Berlin");
hauptstadt.put("FR", "Paris");
hauptstadt.put("AT", "Wien");
hauptstadt.put("DE", "Bonn"); // gleicher Schlüssel: der alte Wert wird ersetzt
hauptstadt.put("DE", "Berlin");
System.out.println(hauptstadt.get("FR"));
System.out.println(hauptstadt.get("IT")); // kein Eintrag: null
System.out.println(hauptstadt.getOrDefault("IT", "unbekannt"));
System.out.println(hauptstadt.containsKey("AT") + ", " + hauptstadt.size() + " Einträge");
// Zählen: Wie oft kommt jeder Buchstabe vor?
Map<Character, Integer> anzahl = new TreeMap<>();
for (char zeichen : "MISSISSIPPI".toCharArray()) {
anzahl.put(zeichen, anzahl.getOrDefault(zeichen, 0) + 1);
}
System.out.println(anzahl);
// Über alle Einträge laufen
for (Map.Entry<Character, Integer> eintrag : anzahl.entrySet()) {
System.out.println(eintrag.getKey() + ": " + "*".repeat(eintrag.getValue()));
}
}
}
Terminal-Fenster
Paris
null
unbekannt
true, 3 Einträge
{I=4, M=1, P=2, S=4}
I: ****
M: *
P: **
S: ****
  • put legt einen Eintrag an – oder ersetzt den Wert, wenn es den Schlüssel schon gibt.
  • get liefert für einen unbekannten Schlüssel null, getOrDefault einen Ersatzwert. Damit lässt sich bequem zählen.
  • Über eine Map läuft man mit entrySet(): Jeder Eintrag ist ein Map.Entry mit getKey() und getValue().
  • Für die Reihenfolge gilt dasselbe wie bei den Mengen: HashMap ungeordnet, LinkedHashMap in Einfügereihenfolge, TreeMap nach Schlüsseln sortiert.
QueueDemo.java
package de.drv.collections;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;
import java.util.Queue;
public class QueueDemo {
public static void main(String[] args) {
// Warteschlange (FIFO): Wer zuerst kommt, ist zuerst dran.
Queue<String> schlange = new ArrayDeque<>();
schlange.offer("Anna");
schlange.offer("Ben");
schlange.offer("Clara");
System.out.println("als Nächstes: " + schlange.peek());
System.out.println("dran: " + schlange.poll() + ", dann " + schlange.poll() + ", übrig " + schlange);
// Stapel (LIFO): Was zuletzt kam, geht zuerst – dieselbe Klasse als Deque
Deque<String> stapel = new ArrayDeque<>();
stapel.push("Teller 1");
stapel.push("Teller 2");
stapel.push("Teller 3");
System.out.println("oben: " + stapel.peek());
System.out.println("weg: " + stapel.pop() + ", übrig " + stapel);
// Vorrang: Das kleinste Element kommt zuerst – egal, wann es kam.
Queue<Integer> vorrang = new PriorityQueue<>();
vorrang.offer(30);
vorrang.offer(10);
vorrang.offer(20);
System.out.print("nach Vorrang:");
while (!vorrang.isEmpty()) {
System.out.print(" " + vorrang.poll());
}
System.out.println();
}
}
Terminal-Fenster
als Nächstes: Anna
dran: Anna, dann Ben, übrig [Clara]
oben: Teller 3
weg: Teller 3, übrig [Teller 2, Teller 1]
nach Vorrang: 10 20 30
Interface Prinzip Methoden
Queue FIFO – first in, first out: wie an der Kasse offer hinten anstellen, poll vorn herausnehmen, peek nachsehen
Deque als Stapel LIFO – last in, first out: wie ein Tellerstapel push drauflegen, pop herunternehmen, peek nachsehen

Deque (gesprochen „Deck“, von double-ended queue) kann an beiden Enden hinzufügen und herausnehmen – und ist damit Warteschlange und Stapel zugleich. Die übliche Implementierung ist ArrayDeque. Die PriorityQueue ordnet nicht nach Ankunft, sondern nach Größe: Das kleinste Element kommt zuerst.

Einige Klassen stammen noch aus Java 1.0 – aus der Zeit vor dem Collection-Framework. Du findest sie in altem Code und in alten Anleitungen:

alt heute warum
Vector ArrayList
Stack ArrayDeque (als Deque) Stack erbt von Vector – man kann mitten im Stapel einfügen
Hashtable HashMap

Die alten Klassen sind threadsicher: Jede Methode ist synchronized – wie bei StringBuffer gegenüber StringBuilder. Das kostet bei jedem Aufruf Zeit, auch wenn gar keine zwei Threads beteiligt sind. Die neuen Klassen verzichten darauf.

Und wenn doch mehrere Threads dieselbe Sammlung benutzen? Dann gibt es eigene, dafür gebaute Klassen im Package java.util.concurrent, etwa ConcurrentHashMap. Die sehen wir uns beim Thema Parallelität an.

  1. Spielt die Reihenfolge eine Rolle, und darf etwas doppelt vorkommen? → List, meist ArrayList
  2. Soll jedes Element nur einmal vorkommen? → Set: HashSet, sortiert TreeSet
  3. Willst du zu einem Schlüssel einen Wert nachschlagen? → Map: HashMap, sortiert TreeMap
  4. Kommt es nur auf das nächste Element an? → Queue oder Deque: ArrayDeque

Im Demo-Code steht die Klasse Texte mit einem kurzen Text in der Konstanten Texte.JAVA. Schreibe ein Programm Textstatistik, das diesen Text auswertet. Die Wörter bekommst du – klein geschrieben und ohne Satzzeichen – mit:

String[] teile = Texte.JAVA.toLowerCase().split("[^a-zäöüß]+");

Das Muster heißt: Trenne an allem, was kein Buchstabe ist. Mehr zu solchen Mustern beim Thema String-Verarbeitung.

  1. Liste: Lege alle Wörter in einer List<String> ab. Gib aus, wie viele es sind, welches das erste und welches das letzte ist, und wie oft das Wort java vorkommt.

  2. Menge: Wie viele verschiedene Wörter enthält der Text? Gib sie alphabetisch sortiert aus. Tipp: Die Klassen des Frameworks haben einen Konstruktor, der eine andere Collection übernimmt.

  3. Tabelle: Zähle mit einer Map<String, Integer>, wie oft jedes Wort vorkommt. Gib alphabetisch alle Wörter aus, die mindestens dreimal vorkommen – mit ihrer Anzahl.

  4. Für Schnelle: Schreibe eine Methode Klammern.passen(String text), die prüft, ob die Klammern ( ) [ ] { } in einem Text zueinander passen: "(a[b]{c})" passt, "(]", "((" und "())" nicht. Tipp: Lege jede öffnende Klammer auf einen Stapel. Bei einer schließenden muss oben die passende öffnende liegen.

Lösung
Terminal-Fenster
91 Wörter, das erste: java, das letzte: bessere
"java" kommt 3-mal vor
54 verschiedene Wörter
[bessere, bibliothek, bietet, danach, das, dateien, die, duplikate, eine, einen, für, gehören, groß, ist, java, jedem, keine, kennen, kennt, klassen, kürzere, lernt, liste, listen, man, maschine, menge, mengen, methoden, netz, ordnet, plattform, programme, programmiersprache, reihenfolge, sammlungen, schleifen, schlüssel, schreibt, sind, sprache, tabelle, tabellen, texte, und, variablen, viele, virtuelle, wer, werkzeuge, wert, zu, zuerst, zur]
Mindestens dreimal:
die 8
eine 5
für 4
ist 3
java 3
kennt 3
lernt 3
plattform 4
sammlungen 3
und 8
  • new TreeSet<>(woerter) übernimmt alle Wörter der Liste – Duplikate fallen dabei weg, und sortiert ist die Menge auch gleich.
  • Die Zählschleife ist dieselbe wie bei MISSISSIPPI in der Demo, nur mit Wörtern statt Buchstaben.
  • Wörter mit Umlaut sortiert String nach dem Zeichencode: Ein „über“ stünde hinter „zur“. Wie man nach deutschen Regeln sortiert, gehört zum Thema Lokalisierung.
Textstatistik.java
package de.drv.collections;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
public class Textstatistik {
public static void main(String[] args) {
// Stufe 1: alle Wörter in einer Liste
List<String> woerter = new ArrayList<>();
for (String wort : Texte.JAVA.toLowerCase().split("[^a-zäöüß]+")) {
if (!wort.isEmpty()) {
woerter.add(wort);
}
}
System.out.println(woerter.size() + " Wörter, das erste: " + woerter.getFirst()
+ ", das letzte: " + woerter.getLast());
int java = 0;
for (String wort : woerter) {
if (wort.equals("java")) {
java++;
}
}
System.out.println("\"java\" kommt " + java + "-mal vor");
// Stufe 2: verschiedene Wörter – ein TreeSet sortiert gleich mit
Set<String> verschiedene = new TreeSet<>(woerter);
System.out.println(verschiedene.size() + " verschiedene Wörter");
System.out.println(verschiedene);
// Stufe 3: Wie oft kommt jedes Wort vor?
Map<String, Integer> haeufigkeit = new TreeMap<>();
for (String wort : woerter) {
haeufigkeit.put(wort, haeufigkeit.getOrDefault(wort, 0) + 1);
}
System.out.println("Mindestens dreimal:");
for (Map.Entry<String, Integer> eintrag : haeufigkeit.entrySet()) {
if (eintrag.getValue() >= 3) {
System.out.printf(" %-12s %d%n", eintrag.getKey(), eintrag.getValue());
}
}
}
}
Lösung
Terminal-Fenster
"(a[b]{c})" passt
"if (x[0] > 1) { y(); }" passt
"(]" passt nicht
"((" passt nicht
"())" passt nicht
"" passt

Drei Arten, falsch zu sein – und drei Prüfungen:

  • "(]": Oben auf dem Stapel liegt die falsche öffnende Klammer.
  • "())": Der Stapel ist leer, obwohl noch eine schließende kommt.
  • "((": Am Ende liegt noch etwas auf dem Stapel.

Als Stapel dient eine Deque<Character> – nicht Stack.

Klammern.java
package de.drv.collections;
import java.util.ArrayDeque;
import java.util.Deque;
/** Prüft, ob die Klammern in einem Text zueinander passen. */
public class Klammern {
public static boolean passen(String text) {
Deque<Character> offen = new ArrayDeque<>();
for (char zeichen : text.toCharArray()) {
if (zeichen == '(' || zeichen == '[' || zeichen == '{') {
offen.push(zeichen);
} else if (zeichen == ')' || zeichen == ']' || zeichen == '}') {
if (offen.isEmpty() || offen.pop() != gegenstueck(zeichen)) {
return false;
}
}
}
return offen.isEmpty(); // keine Klammer darf offen bleiben
}
private static char gegenstueck(char schliessend) {
return switch (schliessend) {
case ')' -> '(';
case ']' -> '[';
default -> '{';
};
}
public static void main(String[] args) {
String[] beispiele = {"(a[b]{c})", "if (x[0] > 1) { y(); }", "(]", "((", "())", ""};
for (String beispiel : beispiele) {
System.out.printf("%-26s %s%n", "\"" + beispiel + "\"", passen(beispiel) ? "passt" : "passt nicht");
}
}
}