Hashtabelle.

Eine Hashtabelle (auch Hashmap) speichert Schlüssel-Wert-Paare und liefert Suche, Einfügen und Löschen erwartet/amortisiert in O(1) bei guter Hash-Funktion und kontrolliertem Load Factor; Worst Case O(n). Eine Hash-Funktion bildet jeden Schlüssel auf einen Bucket-Index ab, und der Wert landet in diesem Bucket. Du lernst hier die Standard-Operationen mit ihren Komplexitäten, die zwei wichtigsten Kollisionsstrategien (Chaining mit verketteten Listen pro Bucket vs Open Addressing mit Linear/Quadratic Probing), den Load Factor α = n/m (Anzahl Einträge / Bucket-Anzahl) und wann Rehashing greift (typisch bei α > 0.75 in Java), wie konkrete Hash-Funktionen funktionieren (z. B. Java String.hashCode() mit Polynom-Hash h = s[0] · 31^(n-1) + dots + s[n-1]), und die Limitierungen (keine Sortier-Reihenfolge, keine effizienten Bereichsabfragen , dafür sind Suchbäume wie BST/B-Tree besser).

Was du in der Klausur können musst:

• Hash-Funktion: berechnet aus dem Schlüssel einen Hashwert, daraus wird ein Bucket-Index bestimmt, idealerweise gleichverteilt
• Kollision: zwei Schlüssel landen auf demselben Bucket-Index, passiert immer bei genug Daten
• Separate Chaining: jeder Bucket ist eine verkettete Liste von kollidierenden Werten
• Open Addressing (Linear Probing): bei Kollision gehe zum nächsten freien Slot
• Load-Factor = Anzahl Einträge / Anzahl Buckets. Java HashMap nutzt standardmäßig 0,75 als Trade-off zwischen Speicher und Geschwindigkeit. Bei Überschreiten wird resized und rehashed.

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.

Das Problem

Stell dir vor, du hast eine Klassenliste mit 1.000 Schülern und willst Annas Note finden. Drei Wege:

1. Liste von oben durchgehen: bis du Anna findest. Bei 1.000 Schülern im Schnitt 500 Vergleiche. Bei 1 Million Schülern: 500.000 Vergleiche. Ziemlich öde.
2. Liste sortieren und binär suchen: ~10 Vergleiche bei 1.000. Schon viel besser. Aber Sortieren kostet selbst Zeit.
3. Gleich wissen wo Anna steht: 1 Schritt. Egal ob 1.000 oder 1 Million Schüler. Zauberei?

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.

Die Idee in einem Bild

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:

• Nimm den Namen "Anna"
• Wend die gleiche Regel an → 274, Rest 4, Postfach 4
• Schau direkt in Postfach 4 → Annas Note

Ein Schritt. Du musstest nichts durchsuchen.

Das ist alles. Mehr ist eine Hashtabelle nicht.

Die Fachbegriffe

Jetzt die offiziellen Wörter:

Was wenn zwei Schüler dasselbe Postfach kriegen?

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:

• Postfach 4 öffnen
• In der Liste nach "Eva" suchen (1-2 Vergleiche)
• Note gefunden

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.

Was wenn die Postfächer voll werden?

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. Java HashMap resized automatisch, sobald die Anzahl der Einträge den Schwellwert capacity · loadFactor überschreitet (standardmäßig capacity · 0,75). Es geht also um die Anzahl Einträge im Verhältnis zur Kapazität, nicht um den Anteil belegter Buckets, durch Kollisionen kann die Zahl belegter Buckets deutlich anders sein. Beispiel: 15 Einträge in 20 Buckets → Load Factor α = 15/20 = 0,75, auch wenn z. B. nur 12 Buckets tatsächlich belegt sind (3 davon haben je 2 Einträge durch Kollisionen). Konkrete Rechnung: capacity=16, entries=12 → Load Factor 12/16 = 0,75 → bei nächstem put wird auf 32 Buckets resized und alle 12+1 Einträge re-hashed. Beim Resize verdoppelt sich die Bucket-Anzahl, alle Einträge werden neu verteilt. Das passiert intern, du merkst nichts davon.

Komplexität (das, was in der Klausur drankommt)

Worst Case tritt auf wenn viele Schlüssel im selben Postfach landen (schlechte Hash-Funktion oder bewusst schlecht gewählte Keys). Bei guter Hash-Funktion und kontrolliertem Load Factor sind put/get/remove durchschnittlich/amortisiert O(1).

Faustregel zum Mitnehmen: Hashtabellen sind die wichtigste allgemeine Datenstruktur für durchschnittlich konstante Key-Lookups, Inserts und Deletes. Direkte Adressierung (Arrays mit Integer-Index) liefert auch O(1), perfektes Hashing kann sogar Worst-Case-Konstantzeit garantieren, Hashtabellen sind die universelle Lösung für allgemeine Keys.

So sieht's im Code aus

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());
}

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}")

Wo nutzt man Hashtabellen?

Überall wo du per Schlüssel schnell etwas finden willst:

Hinweis zu Datenbank-Indizes: Hash-Indizes eignen sich für exakte Gleichheitsabfragen. Viele Datenbanken nutzen für allgemeine Indizes häufig B-Bäume/B+-Bäume, weil sie auch Bereichsabfragen und sortierte Zugriffe effizient unterstützen.

In Python ist das simpel:

noten = {}
noten["anna"] = 1
print(noten["anna"])   # 1, sofort

Hinter den Kulissen läuft genau die Postfach-Magie ab.

Vor- und Nachteile

Pro:

• ✅ Brutal schnell: O(1) für Standard-Operationen
• ✅ In jeder Sprache eingebaut, super einfach zu nutzen
• ✅ Funktioniert mit beliebigen Schlüssel-Typen (Strings, Zahlen, Tupel)

Contra:

• ❌ Iterations-Reihenfolge je nach Sprache: Java HashMap garantiert keine Reihenfolge. Python dict (seit 3.7) behält die Einfügereihenfolge bei, aber das ist trotzdem keine sortierte Map.
• ❌ Braucht mehr Speicher als ein einfaches Array (Postfächer müssen meist 25–30% leer bleiben)
• ❌ Schlechte Hash-Funktion → Hashtabelle wird langsam

Was du in der Klausur wissen musst

Frage: Welche Operation ist NICHT O(1) im Schnitt?

• put → O(1) ✓
• get → O(1) ✓
• contains → O(1) ✓
• Iteration durch alle Einträge → O(n) ✗ (du musst jedes Postfach öffnen)

Faustregel: Bei "schnell finden per Schlüssel" denk Hashtabelle. Bei "in Reihenfolge halten" denk Liste oder Baum. Bei "größtes/kleinstes finden" denk Heap.

Hashtabelle live

Spiel mit der Hashtabelle und beobachte:

• put(key, value): zeigt Hash-Berechnung + Ziel-Bucket + Chaining bei Kollision
• get(key): zeigt Hash + Bucket + Anzahl Vergleiche im Bucket
• remove(key): entfernt aus dem entsprechenden Bucket
• bucketCount-Slider: weniger Buckets = mehr Kollisionen, alle Einträge werden re-hashed

Probier folgendes:

• Setz bucketCount auf 3 mit 5+ Einträgen → fast jeder Bucket hat Kollisionen (rote Markierung)
• Setz bucketCount auf 11 mit denselben Einträgen → meist saubere Verteilung
• put mit existing Key überschreibt den Wert (statt zu duplizieren)
• get auf nicht-existierenden Key zeigt "Bucket leer" oder "Kein Match in Bucket"

Faustregel zum Mitnehmen: Die Hash-Funktion ist der Trick. Sie berechnet aus dem Key einen Hashwert; daraus wird ein Bucket-Index in der internen Tabelle bestimmt. Dort wird der Eintrag gesucht oder gespeichert. Daher durchschnittlich/amortisiert O(1), und so populär.

In der Realität ist die Hash-Funktion natürlich besser als unsere "Summe der char-Codes". String.hashCode() in Java nutzt klassisch einen 31-basierten Polynom-Hash, das streut viel gleichmäßiger. Java HashMap verwendet allgemein den hashCode() des jeweiligen Key-Objekts und wendet zusätzlich (seit Java 8) eine Bit-Mixing-Funktion hash ^ (hash >>> 16) an, um schwache hashCode()-Implementierungen abzufangen.

---

Code-Stepper: put mit Hash, Bucket, Kollision

Hier siehst du was put Schritt für Schritt macht: Hash berechnen, mit modulo auf einen Bucket-Index abbilden, dann in den Bucket einfügen oder bei Kollision mit Chaining anhängen. Wir nutzen eine Tabelle mit 5 Buckets und eine vereinfachte Hash-Funktion "Summe der char-Codes mod 5". Achte besonders auf den dritten put, der eine Kollision auslöst.