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.
Was du am Ende kannst
Abschnitt betitelt „Was du am Ende kannst“- 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
ArrayListzeigen, welches Interface welche Fähigkeit hinzufügt - veraltete Klassen wie
VectorundStackerkennen und ersetzen
Demo-Code: 21-collections
⤓ demo-collections.zip herunterladenDer 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
Der Überblick
Abschnitt betitelt „Der Überblick“| 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> TreeMapEine Map ist keine Collection: Sie enthält keine einzelnen Elemente,
sondern Paare aus Schlüssel und Wert. Sie gehört aber zum Framework.
Die Hierarchie am Beispiel ArrayList
Abschnitt betitelt „Die Hierarchie am Beispiel ArrayList“So steht die ArrayList im JDK:
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, SerializableList 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. DieArrayListhat es, dieLinkedListnicht.AbstractList– eine abstrakte Klasse, wie wir sie in Woche 1 geschrieben haben. Sie enthält Code, den viele Listen teilen, und erspart derArrayListArbeit.
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:
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")); }
}Anna Ben Clara3 Namen, Ben dabei? falseerster: Emil, letzter: Dorarückwärts: [Dora, Clara, Anna, Emil][Emil, Anja, Bert, Clara, Dora], Bert an Stelle 2Gegen das Interface programmieren
Abschnitt betitelt „Gegen das Interface programmieren“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.
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); } }
}[Clara, Anna, Ben, Anna] – 4 Einträgesortiert: [Anna, Anna, Ben, Clara]LinkedList: [Anna, Ben, Clara]zahlen: [30]grünList.of ist unveränderlich: java.lang.UnsupportedOperationExceptionArrayListist unserDynamischesArray: schneller Zugriff über die Position. Sie ist fast immer die richtige Wahl.LinkedListverkettet 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 alsArrayList.Collections(mit s) ist eine Hilfsklasse mit statischen Methoden wiesort,reverse,shuffleundmax– so wieArraysfür Arrays.removebeiList<Integer>ist eine Falle:remove(1)entfernt die Position 1. Den Wert 1 entferntremove(Integer.valueOf(1)).List.of(…)liefert eine Liste, die sich nicht ändern lässt.addwirft eineUnsupportedOperationException– die Methode gehört zum Vertrag, wird hier aber nicht unterstützt. Genau wie bei unseren Platzhaltern.
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); }
}HashSet: [Birne, Kiwi, Apfel, Mango]LinkedHashSet: [Kiwi, Apfel, Mango, Birne]TreeSet: [Apfel, Birne, Kiwi, Mango]Apfel neu? false1 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.
Tabellen
Abschnitt betitelt „Tabellen“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())); } }
}Parisnullunbekannttrue, 3 Einträge{I=4, M=1, P=2, S=4}I: ****M: *P: **S: ****putlegt einen Eintrag an – oder ersetzt den Wert, wenn es den Schlüssel schon gibt.getliefert für einen unbekannten Schlüsselnull,getOrDefaulteinen Ersatzwert. Damit lässt sich bequem zählen.- Über eine Map läuft man mit
entrySet(): Jeder Eintrag ist einMap.EntrymitgetKey()undgetValue(). - Für die Reihenfolge gilt dasselbe wie bei den Mengen:
HashMapungeordnet,LinkedHashMapin Einfügereihenfolge,TreeMapnach Schlüsseln sortiert.
Warteschlangen und Stapel
Abschnitt betitelt „Warteschlangen und Stapel“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(); }
}als Nächstes: Annadran: Anna, dann Ben, übrig [Clara]oben: Teller 3weg: 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.
Alt und threadsicher
Abschnitt betitelt „Alt und threadsicher“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.
Welche Sammlung wann?
Abschnitt betitelt „Welche Sammlung wann?“- Spielt die Reihenfolge eine Rolle, und darf etwas doppelt vorkommen? →
List, meistArrayList - Soll jedes Element nur einmal vorkommen? →
Set:HashSet, sortiertTreeSet - Willst du zu einem Schlüssel einen Wert nachschlagen? →
Map:HashMap, sortiertTreeMap - Kommt es nur auf das nächste Element an? →
QueueoderDeque:ArrayDeque
Übung: Textstatistik
Abschnitt betitelt „Übung: Textstatistik“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.
-
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 Wortjavavorkommt. -
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. -
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. -
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
91 Wörter, das erste: java, das letzte: bessere"java" kommt 3-mal vor54 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 8new 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
MISSISSIPPIin der Demo, nur mit Wörtern statt Buchstaben. - Wörter mit Umlaut sortiert
Stringnach dem Zeichencode: Ein „über“ stünde hinter „zur“. Wie man nach deutschen Regeln sortiert, gehört zum Thema Lokalisierung.
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
"(a[b]{c})" passt"if (x[0] > 1) { y(); }" passt"(]" passt nicht"((" passt nicht"())" passt nicht"" passtDrei 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.
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"); } }
}