Datenstrukturen III (Schlüsselbasiert)

Arrays bieten O(1)-Zugriff über die Position. Binäre Suchbäume liefern O(log n)-Zugriff über die Reihenfolge. Aber was, wenn man Daten über einen beliebigen Schlüssel nachschlagen will — einen Benutzernamen, eine URL oder ein Session-Token? Hash Tables vervollständigen das Bild: Sie wandeln jeden Schlüssel in eine Array-Position um, und zwar in konstanter Zeit.

Dieser Artikel behandelt die drei Säulen schlüsselbasierter Datenstrukturen: den Hash-Trick selbst, das Kollisionsproblem, das jede Hash Table lösen muss, und das Caching-Prinzip, das den Hash-Trick in der Praxis ausnutzt.

Hash Tables: Der O(1)-Trick

Aber Vorsicht: Ein echter Bibliothekar erkennt Ähnlichkeiten und korrigiert Tippfehler. Eine Hash-Funktion behandelt selbst kleinste Unterschiede als völlig verschiedene Schlüssel (Avalanche-Effekt). Und was passiert, wenn zwei Titel auf dasselbe Regal zeigen? Der magische Bibliothekar hat dieses Problem nicht — Hash Tables schon.

Hash Table mit 10 Slots:

hash("cat") = (99 + 97 + 116) % 10 = 312 % 10 = 2
hash("dog") = (100 + 111 + 103) % 10 = 314 % 10 = 4

Nachschlagen von "cat":
→ Hash berechnen → 2
→ Zu Slot 2 springen
→ Fertig. Ein Schritt statt bis zu 10.

Kollisionen: Wenn zwei Schlüssel denselben Slot wollen

Eine Kollision tritt auf, wenn zwei verschiedene Schlüssel auf denselben Index gehasht werden. Das Schubfachprinzip garantiert, dass dies unvermeidlich ist: Wenn es mehr mögliche Schlüssel als Buckets gibt, müssen sich einige teilen.

Stell dir eine Garderobe mit 100 nummerierten Haken vor. Der Garderobier vergibt Haken nach dem Anfangsbuchstaben des Nachnamens — A bekommt Haken 1, B bekommt Haken 2. Wenn zwei Gäste namens "Schmidt" und "Schwarz" beide auf Haken 19 treffen, hat der Garderobier zwei Optionen: beide Mäntel am selben Haken aufhängen und später durchsuchen (Separate Chaining) oder den zweiten Mantel am nächsten freien Haken aufhängen (Open Addressing).

Ein echter Garderobier wird bei Platzmangel kreativ — er stapelt Mäntel, hängt sie an die Tür oder legt sie auf einen Stuhl. Eine Hash Table kann nicht improvisieren. Sie braucht strikte, vorprogrammierte Regeln (Chaining oder Probing) für jeden Kollisionsfall.

Hash Table mit 7 Slots, h(key) = len(key) % 7:

"cat" → len=3 → 3 % 7 = 3
"dog" → len=3 → 3 % 7 = 3  ← Kollision!
"elephant" → len=8 → 8 % 7 = 1
"bird" → len=4 → 4 % 7 = 4

Separate Chaining an Slot 3:
[("cat", val1) → ("dog", val2)]

Interaktiv: Hash-Demonstrator

Gib einen Schlüssel ein und beobachte, wie die Hash-Funktion daraus eine Slot-Nummer berechnet. Füge mehrere Schlüssel ein und erlebe Kollisionen live — wenn zwei verschiedene Schlüssel auf denselben Slot abgebildet werden.

Caching: Speicher tauscht gegen Geschwindigkeit

Caching speichert häufig oder kürzlich genutzte Daten in schnellem Speicher, um langsame Neuberechnungen oder Netzwerkaufrufe zu vermeiden. Die Kernbegriffe: Cache Hit (Daten lokal gefunden — schnell), Cache Miss (nicht im Cache — muss von der langsamen Quelle geholt werden) und Cache-Invalidierung (veraltete Einträge entfernen).

Die Pizza-im-Kühlschrank-Analogie: Pizza bestellen dauert 30-40 Minuten (Daten von der Originalquelle holen). Übrig gebliebene Pizza im Kühlschrank aufwärmen geht in Minuten (Cache Hit). Aber am nächsten Tag könnte sie nicht mehr frisch sein (veraltete Daten). Du musst entscheiden, wann du sie wegwirfst und neu bestellst (Cache-Invalidierung / TTL).

Im echten Leben verdirbt Pizza langsam — man merkt es am Geruch oder Geschmack. Im digitalen Cache gibt es keinen graduellen Verfall: Daten sind entweder gültig oder veraltet, ohne Zwischenstufe. Deshalb muss die Invalidierung durch exakte Metadaten wie max-age gesteuert werden, nicht durch Intuition.