Datenstrukturen III (Schlüsselbasiert)
Schlüsselbasierte Datenstrukturen, die unauffällig fast jedes System antreiben.
Arrays bieten O(1)-Zugriff über die Position. Balancierte 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
Definition
Hash Table
Analogie
Definition
Aber Vorsicht: Ein echter Bibliothekar erkennt Ähnlichkeiten und korrigiert Tippfehler. Eine Hash-Funktion erkennt keine Ähnlichkeit; viele machen sogar aus kleinsten Unterschieden völlig verschiedene Hash-Werte (Avalanche-Effekt). Und was passiert, wenn zwei Titel auf dasselbe Regal zeigen? Der magische Bibliothekar hat dieses Problem nicht — Hash Tables schon.
Beispiel: Hash-Berechnung
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.Die ASCII-Werte der Buchstaben werden addiert und mit Modulo auf die Tabellengröße abgebildet. Das ergibt eine direkte Adresse — kein Suchen, kein Sortieren, einfach berechnen und springen. Diese Spielzeug-Funktion ist bewusst simpel: "act" ergibt ebenfalls 312 und landet wie "cat" in Slot 2; echte Hash-Funktionen mischen die Zeichen gründlicher.
Direktzugriff über Positionsnummer. Schnell, wenn du die Position kennst — aber du musst die Nummer wissen.
Direktzugriff über beliebigen Schlüssel (Name, URL, ID). Die Hash-Funktion berechnet die Position automatisch.
Achtung
Irrtum: Hash Tables sind immer O(1)
O(1) ist der Durchschnittsfall bei einer guten Hash-Funktion und moderatem Füllgrad. Im schlimmsten Fall — viele Kollisionen, hoher Füllgrad — degradiert der Zugriff auf O(n). Gegen den hohen Füllgrad hilft Rehashing: Die Tabelle wird vergrößert und alle Einträge neu verteilt.
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. Und schon lange vor einer vollen Tabelle sind Kollisionen wahrscheinlich: Bei zehn zufällig verteilten Schlüsseln in 100 Slots kommt es mit etwa 37 % Wahrscheinlichkeit zu mindestens einer Kollision (Geburtstagsparadoxon).
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.
Merke
Kollisionsstrategien
Beispiel: Kollision in der Praxis
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)]"cat" und "dog" haben beide 3 Buchstaben — ihre Hashes kollidieren an Slot 3. Mit Separate Chaining hält der Slot eine verkettete Liste beider Einträge. Die Suche nach "dog" braucht 2 Vergleiche statt 1, bleibt aber schnell. Bei steigendem Füllgrad wachsen die Ketten — ab 75% wird typischerweise ein Rehashing ausgelöst.
Merke
Rehashing: Wenn die Tabelle voll wird
Vorher und Nachher: Rehashing
Achtung
Irrtum: Kollisionen bedeuten, die Hash Table ist kaputt
Kollisionen sind durch das Schubfachprinzip mathematisch garantiert. Eine gut entworfene Hash Table behandelt sie effizient. Es wird erst problematisch, wenn die Hash-Funktion schlecht verteilt oder der Füllgrad ohne Rehashing zu hoch steigt.
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 gegen Geschwindigkeit tauschen
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.
Merke
Speicherhierarchie: Latenzen im Vergleich
- 1. L1-Cache: ~1 nsschnellster, kleinster Speicher
- 2. L2-Cache: ~5 ns
- 3. L3-Cache: ~20 ns
- 4. RAM: ~100 ns
- 5. SSD: ~100 μs1.000× langsamer als RAM
- 6. Internet über weite Strecken: ~100 ms1.000.000× langsamer als RAM
Praxisbeispiel: Browser-Caching
Erster Besuch: Browser lädt HTML, CSS und Bilder vom Server (~2 Sekunden). Der Server sendet Cache-Control: max-age=3600. Zweiter Besuch innerhalb einer Stunde: Browser liefert aus dem lokalen Cache (~50 ms). Nach einer Stunde: Cache abgelaufen, der Browser fragt beim Server nach und lädt nur Geändertes neu. Ergebnis: Deutlich schnellere wahrgenommene Ladezeit für wiederkehrende Besucher.
Achtung
Irrtum: Caching macht immer alles schneller
Caching hilft nur, wenn Daten wiederholt abgerufen werden. Bei einmaligen Abfragen dominieren Cache Misses, und der Cache verschwendet nur Speicher. Außerdem liefert aggressives Caching ohne saubere Invalidierung veraltete Daten. Daher der berühmte Spruch: "Die zwei schwierigen Dinge in der Informatik: Cache-Invalidierung und Namensgebung."
In großen Sprachmodellen (LLMs) werden Hash Tables für die Token-zu-ID-Zuordnung verwendet: Jedes Wort oder Teilwort wird auf eine Ganzzahl abgebildet, die als Index in die Embedding-Matrix dient. Auch bei der Datendeduplizierung spielt Hashing eine zentrale Rolle — identische Trainingsdaten werden über ihren Hash erkannt und gefiltert. Der KV-Cache (Key-Value-Cache) in Transformer-Modellen ist trotz des Namens keine Hash Table, sondern ein Beispiel für das Caching-Prinzip aus diesem Artikel: Die bereits berechneten Key- und Value-Vektoren früherer Tokens werden gecacht, um bei der Token-für-Token-Generierung keine Neuberechnung durchführen zu müssen.
Merke
Kernaussagen
- Eine Hash-Funktion wandelt jeden Schlüssel in einen Array-Index um — das ist der "Zaubertrick" hinter dem durchschnittlichen O(1)-Nachschlagen in Dictionaries, Maps und Caches.
- Caching tauscht Speicher gegen Geschwindigkeit: Speichere die Antwort einmal, überspringe die teure Berechnung oder den Netzwerkaufruf beim nächsten Mal — aber veraltete Daten sind der Preis ohne saubere Invalidierung.
- Kollisionen sind keine Fehler — sie sind mathematisch unvermeidlich. Gute Hash Tables behandeln sie elegant durch Chaining oder Probing und halten die Performance durch Rehashing stabil.
Prüfen
Quiz: Schlüsselbasierte Datenstrukturen
Was macht eine Hash-Funktion?
Wähle eine Antwort
1. Was macht eine Hash-Funktion?
2. Eine Hash-Funktion berechnet für einen Schlüssel den Wert 487. Die Tabelle hat 10 Slots. In welchem Slot landet der Eintrag?
3. Dein Cache hat max-age=3600 (eine Stunde). Ein Nutzer besucht die Seite nach 30 Minuten erneut. Was passiert?
4. Eine Hash Table mit 100 Slots speichert 200 Einträge. Warum müssen Kollisionen auftreten?
Prüfen
Checkpoint: Schlüsselbasierte Datenstrukturen
Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.
0 von 3 sitzen