Die wichtigste Datenstruktur überhaupt. Key-Value-Lookup in O(1) durch eine Hash-Funktion. Java HashMap, Python dict. Verstehe Buckets, Kollisionen und Chaining.
Eine Hashtabelle (auch Hashmap) speichert Schlüssel-Wert-Paare und liefert Suche, Einfügen und Löschen im Durchschnitt in O(1). Eine Hash-Funktion bildet jeden Schlüssel auf einen Bucket-Index ab, und der Wert landet in diesem Bucket.
Was du in der Klausur können musst:
In Klausuren wirst du oft gefragt: trage die Werte in eine gegebene Hashtabelle ein und behandle Kollisionen mit der vorgegebenen Methode. Achte darauf, ob die Aufgabe Chaining oder Open Addressing fordert, das ändert die Position der kollidierenden Werte komplett.
Stell dir vor, du hast eine Klassenliste mit 1.000 Schülern und willst Annas Note finden. Drei Wege:
Genau diese Zauberei macht eine Hashtabelle: Sie weiß sofort, wo ein bestimmter Eintrag liegt — ohne suchen, ohne sortieren.
In Java heißt sie HashMap, in Python dict. In jeder modernen Sprache eingebaut.
Stell dir eine Wand mit 10 Postfächern vor, nummeriert 0 bis 9. Jeder Schüler-Eintrag landet in genau einem Postfach. Aber wie entscheiden welches?
Regel: Nimm den Namen, rechne mit den Buchstaben eine Zahl aus, teile durch 10, der Rest ist die Postfach-Nummer.
Anna → Buchstaben-Zahl 274 → 274 ÷ 10 = 27 Rest 4 → Postfach 4
Ben → Buchstaben-Zahl 215 → 215 ÷ 10 = 21 Rest 5 → Postfach 5
Kim → Buchstaben-Zahl 222 → 222 ÷ 10 = 22 Rest 2 → Postfach 2
Anna's Eintrag wandert in Postfach 4. Wenn du später Anna's Note willst:
Ein Schritt. Du musstest nichts durchsuchen.
Das ist alles. Mehr ist eine Hashtabelle nicht.
Jetzt die offiziellen Wörter:
| Im Bild | Im Code | Bedeutung |
|---|---|---|
| Postfächer | Buckets | das Array das die Einträge speichert |
| Buchstaben-Zahl | Hash | die Zahl die aus dem Schlüssel berechnet wird |
| Regel | Hash-Funktion | das was Schlüssel zu Hash macht |
| Schüler-Name | Key | womit du suchst |
| Schüler-Note | Value | was du speicherst und zurückbekommst |
| Postfach-Nummer | Bucket-Index | Hash modulo Bucket-Anzahl |
Beispiel: Anna und Eva haben beide eine Buchstaben-Zahl, die durch 10 geteilt Rest 4 ergibt. Beide wollen Postfach 4. Was tun?
→ Kollision.
Lösung: Im Postfach steht nicht ein einziger Eintrag, sondern eine kleine Liste. Anna kommt rein, Eva kommt dazu. Wenn du nach "Eva" suchst:
Solange wenige Schüler dasselbe Postfach kriegen, geht's immer noch fast genauso schnell wie ohne Kollision. Genau deshalb sind Hashtabellen praktisch immer O(1): weil gute Hash-Funktionen die Schüler gleichmäßig auf alle Postfächer verteilen.
Wenn ich 100 Schüler in 10 Postfächern habe, sind im Schnitt 10 Schüler pro Postfach — und Suchen wird wieder linear (O(n)).
Lösung: Größere Wand bauen. Sobald 70-75% gefüllt ist, baut die Hashtabelle automatisch eine neue Wand mit doppelt so vielen Postfächern und teilt alle Einträge neu auf. Das passiert intern, du merkst nichts davon.
| Operation | Normal | Worst Case |
|---|---|---|
| put (Eintrag speichern) | O(1) | O(n) |
| get (Eintrag holen) | O(1) | O(n) |
| remove (Eintrag löschen) | O(1) | O(n) |
Worst Case tritt auf wenn alle Schlüssel im selben Postfach landen (schlechte Hash-Funktion) — in der Praxis quasi nie.
Faustregel zum Mitnehmen: Hashtabellen sind die einzige Datenstruktur, die konstante Zeit für Lookup, Insert und Delete schafft. Daher steckt sie in fast jeder Programmiersprache und in jedem zweiten Programm.
import java.util.HashMap;
HashMap<String, Integer> noten = new HashMap<>();
noten.put("anna", 1); // O(1)
noten.put("ben", 3);
noten.put("kim", 2);
int annas = noten.get("anna"); // 1, O(1)
boolean hat = noten.containsKey("max"); // false
noten.remove("ben"); // O(1)
int size = noten.size(); // 2
// Iterieren
for (var entry : noten.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}Überall wo du per Schlüssel schnell etwas finden willst:
| Was du speicherst | Schlüssel (Key) | Wert (Value) |
|---|---|---|
| Nutzer-Datenbank | User-Profil | |
| Wörter zählen in Text | Wort | Anzahl Vorkommen |
| Cache (z.B. Browser) | URL | gespeicherte Seite |
| DNS-Auflösung | Domain-Name | IP-Adresse |
| Datenbank-Indizes | Spaltenwert | Zeilen-Position |
In Python ist das simpel:
noten = {}
noten["anna"] = 1
print(noten["anna"]) # 1, sofort
Hinter den Kulissen läuft genau die Postfach-Magie ab.
Pro:
Contra:
Frage: Welche Operation ist NICHT O(1) im Schnitt?
Faustregel: Bei "schnell finden per Schlüssel" denk Hashtabelle. Bei "in Reihenfolge halten" denk Liste oder Baum. Bei "größtes/kleinstes finden" denk Heap.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Eine Hashtabelle (auch Hashmap) speichert Schlüssel-Wert-Paare und liefert Suche, Einfügen und Löschen im Durchschnitt in O(1). Eine Hash-Funktion bildet jeden Schlüssel auf einen Bucket-Index ab, und der Wert landet in diesem Bucket.
Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).
Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.
Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.
Was du in der Klausur können musst:
In Klausuren wirst du oft gefragt: trage die Werte in eine gegebene Hashtabelle ein und behandle Kollisionen mit der vorgegebenen Methode. Achte darauf, ob die Aufgabe Chaining oder Open Addressing fordert, das ändert die Position der kollidierenden Werte komplett.
Stell dir vor, du hast eine Klassenliste mit 1.000 Schülern und willst Annas Note finden. Drei Wege:
Genau diese Zauberei macht eine Hashtabelle: Sie weiß sofort, wo ein bestimmter Eintrag liegt — ohne suchen, ohne sortieren.
In Java heißt sie HashMap, in Python dict. In jeder modernen Sprache eingebaut.
Stell dir eine Wand mit 10 Postfächern vor, nummeriert 0 bis 9. Jeder Schüler-Eintrag landet in genau einem Postfach. Aber wie entscheiden welches?
Regel: Nimm den Namen, rechne mit den Buchstaben eine Zahl aus, teile durch 10, der Rest ist die Postfach-Nummer.
Anna → Buchstaben-Zahl 274 → 274 ÷ 10 = 27 Rest 4 → Postfach 4
Ben → Buchstaben-Zahl 215 → 215 ÷ 10 = 21 Rest 5 → Postfach 5
Kim → Buchstaben-Zahl 222 → 222 ÷ 10 = 22 Rest 2 → Postfach 2
Anna's Eintrag wandert in Postfach 4. Wenn du später Anna's Note willst:
Ein Schritt. Du musstest nichts durchsuchen.
Das ist alles. Mehr ist eine Hashtabelle nicht.
Jetzt die offiziellen Wörter:
| Im Bild | Im Code | Bedeutung |
|---|---|---|
| Postfächer | Buckets | das Array das die Einträge speichert |
| Buchstaben-Zahl | Hash | die Zahl die aus dem Schlüssel berechnet wird |
| Regel | Hash-Funktion | das was Schlüssel zu Hash macht |
| Schüler-Name | Key | womit du suchst |
| Schüler-Note | Value | was du speicherst und zurückbekommst |
| Postfach-Nummer | Bucket-Index | Hash modulo Bucket-Anzahl |
Beispiel: Anna und Eva haben beide eine Buchstaben-Zahl, die durch 10 geteilt Rest 4 ergibt. Beide wollen Postfach 4. Was tun?
→ Kollision.
Lösung: Im Postfach steht nicht ein einziger Eintrag, sondern eine kleine Liste. Anna kommt rein, Eva kommt dazu. Wenn du nach "Eva" suchst:
Solange wenige Schüler dasselbe Postfach kriegen, geht's immer noch fast genauso schnell wie ohne Kollision. Genau deshalb sind Hashtabellen praktisch immer O(1): weil gute Hash-Funktionen die Schüler gleichmäßig auf alle Postfächer verteilen.
Wenn ich 100 Schüler in 10 Postfächern habe, sind im Schnitt 10 Schüler pro Postfach — und Suchen wird wieder linear (O(n)).
Lösung: Größere Wand bauen. Sobald 70-75% gefüllt ist, baut die Hashtabelle automatisch eine neue Wand mit doppelt so vielen Postfächern und teilt alle Einträge neu auf. Das passiert intern, du merkst nichts davon.
| Operation | Normal | Worst Case |
|---|---|---|
| put (Eintrag speichern) | O(1) | O(n) |
| get (Eintrag holen) | O(1) | O(n) |
| remove (Eintrag löschen) | O(1) | O(n) |
Worst Case tritt auf wenn alle Schlüssel im selben Postfach landen (schlechte Hash-Funktion) — in der Praxis quasi nie.
Faustregel zum Mitnehmen: Hashtabellen sind die einzige Datenstruktur, die konstante Zeit für Lookup, Insert und Delete schafft. Daher steckt sie in fast jeder Programmiersprache und in jedem zweiten Programm.
import java.util.HashMap;
HashMap<String, Integer> noten = new HashMap<>();
noten.put("anna", 1); // O(1)
noten.put("ben", 3);
noten.put("kim", 2);
int annas = noten.get("anna"); // 1, O(1)
boolean hat = noten.containsKey("max"); // false
noten.remove("ben"); // O(1)
int size = noten.size(); // 2
// Iterieren
for (var entry : noten.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}Java HashMap mit Generics. put/get/remove sind alle O(1) im Average Case.
noten = {}
noten["anna"] = 1 # O(1)
noten["ben"] = 3
noten["kim"] = 2
annas = noten["anna"] # 1, O(1)
hat = "max" in noten # False, O(1)
del noten["ben"] # O(1)
size = len(noten) # 2
# Iterieren
for key, value in noten.items():
print(f"{key}: {value}")Python dict ist die Standard-Hashtabelle. Syntax-Zucker mit [] und in-Operator.
Überall wo du per Schlüssel schnell etwas finden willst:
| Was du speicherst | Schlüssel (Key) | Wert (Value) |
|---|---|---|
| Nutzer-Datenbank | User-Profil | |
| Wörter zählen in Text | Wort | Anzahl Vorkommen |
| Cache (z.B. Browser) | URL | gespeicherte Seite |
| DNS-Auflösung | Domain-Name | IP-Adresse |
| Datenbank-Indizes | Spaltenwert | Zeilen-Position |
In Python ist das simpel:
noten = {}
noten["anna"] = 1
print(noten["anna"]) # 1, sofort
Hinter den Kulissen läuft genau die Postfach-Magie ab.
Pro:
Contra:
Frage: Welche Operation ist NICHT O(1) im Schnitt?
Faustregel: Bei "schnell finden per Schlüssel" denk Hashtabelle. Bei "in Reihenfolge halten" denk Liste oder Baum. Bei "größtes/kleinstes finden" denk Heap.
Spiel mit der Hashtabelle und beobachte:
Probier folgendes:
Interaktive Visualisierung
Zeigt Hashtabelle mit Hash-Funktion, Buckets und Kollisions-Auflösung.
Faustregel zum Mitnehmen: Die Hash-Funktion ist der Trick. Sie übersetzt Keys direkt in Speicheradressen, ohne lineare Suche. Daher O(1) — und so populär.
In der Realität ist die Hash-Funktion natürlich besser als unsere "Summe der char-Codes" — Java nutzt Polynom-Hashing mit Multiplikator 31, das streut viel gleichmäßiger.
Klausurfragen mit Lösungen (8)
Antwort: O(1)
Erklärung: Im Average Case sind alle drei Operationen O(1). Die Hash-Funktion springt direkt zum Bucket, der dann meist nur 1-2 Einträge hat. Das ist die Magie der Hashtabelle.
Antwort: Zwei verschiedene Keys hashen zum selben Bucket
Erklärung: Eine Kollision tritt auf, wenn zwei verschiedene Keys (z.B. 'ab' und 'ba') zur selben Bucket-Position gehasht werden. Lösung: Chaining (Liste pro Bucket) oder Open Addressing.
Antwort: Wenn alle Keys im selben Bucket landen, wird linear gesucht
Erklärung: Bei sehr schlechter Hash-Funktion (oder bewusster Manipulation) können alle Keys im selben Bucket landen. Dann degeneriert die Hashtabelle zu einer linearen Liste mit O(n) Lookup. Daher: gute Hash-Funktion ist Pflicht.
Antwort: Wörterzählung in einem Text
Erklärung: Wörterzählung: Key = Wort, Value = Anzahl. O(1) put/get pro Wort. Sortierung braucht eine andere Datenstruktur (TreeMap), Pfade brauchen Graph-Algorithmen, Klammern brauchen Stack.
Antwort: n
Erklärung: Wenn alle n Einträge im selben Bucket landen (extreme Kollision), muss linear durch die Liste gegangen werden bis Treffer. Das ist exakt O(n). Genau das soll eine gute Hash-Funktion verhindern.
Antwort: Sie wird automatisch vergrößert (resize + rehash)
Erklärung: Java HashMap hat einen loadFactor von 0.75. Sobald die Tabelle 75% voll ist, wird die Bucket-Anzahl verdoppelt und alle Einträge re-hashed. Das ist O(n) für die einmalige Resize-Operation, aber amortisiert bleibt put bei O(1).
HashMap<String, Integer> m = new HashMap<>();
m.put("a", 1);
m.put("b", 2);
m.put("a", 99);
System.out.println(m.get("a") + ", " + m.size());Antwort: 99, 2
Erklärung: Beim zweiten put('a', 99) wird der existierende Wert für Key 'a' überschrieben. Größe bleibt 2 (a + b), Wert von a ist 99.
Antwort: 100
Erklärung: 10.000 / 100 = 100 Einträge pro Bucket. Das ist viel zu hoch (loadFactor 100), die HashMap würde automatisch vergrößern. Default-Java würde das auf ~133 Buckets ausdehnen, dass jeder Bucket nur ~75 Einträge hat.
Typ: Zahlen-Eingabe