Zurück zum Lernbereich

Datenstrukturen III (Schlüsselbasiert)

Schlüsselbasierte Datenstrukturen, die unauffällig fast jedes System antreiben.

  • Grundlagen
  • 15 min
  • Fortgeschritten

Einfache Sprache

Diese Vorschau ist in Einfacher Sprache. Das ganze Portal gibt es auch in Einfacher Sprache. Du kannst oben die Sprache wechseln. Oder nutze den Knopf unten. Unsere Texte in Einfacher Sprache entstehen KI-gestützt und werden redaktionell begleitet. Sie orientieren sich an den Grundprinzipien der Leichten Sprache, sind aber keine geprüfte Leichte Sprache: Eine Prüfgruppe von Menschen mit Lernschwierigkeiten prüft sie nicht.

Vorschau: Daten schnell finden mit Schlüsseln

Was sind Hash Tables?

Ein Hash Table ist eine Datenstruktur. Datenstruktur bedeutet: eine Ordnung für Daten. Ein Hash Table findet Daten sehr schnell. Dafür braucht er einen Schlüssel.

So funktioniert der Schlüssel

Du gibst einen Schlüssel ein. Das ist zum Beispiel ein Name. Eine Hash-Funktion rechnet daraus eine Nummer. Hash-Funktion bedeutet: eine Rechenregel. Diese Nummer zeigt den Speicherort der Daten.

Warum so schnell?

Bei anderen Methoden muss man viele Daten durchsuchen. Das dauert lang. Ein Hash Table berechnet die Position direkt. Das ist in einem Schritt möglich. Kein Suchen, kein Sortieren.

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

Stell dir eine riesige Bibliothek vor. Du könntest jedes Regal durchsuchen — O(n). Oder du nutzt einen alphabetischen Katalog, der den Suchraum jedes Mal halbiert — O(log n), wie ein Binärbaum. Oder du flüsterst dem magischen Bibliothekar den Titel zu, und er nennt dir sofort die exakte Regalnummer — O(1). Der Bibliothekar ist die Hash-Funktion: eine mechanische Regel, die den Titel in eine Nummer umwandelt, ohne ihn zu verstehen.

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.

Array: O(1) per Index

Direktzugriff über Positionsnummer. Schnell, wenn du die Position kennst — aber du musst die Nummer wissen.

Hash Table: O(1) per Schlüssel

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

Separate Chaining Jeder Bucket enthält eine verkettete Liste. Bei einer Kollision wird der neue Eintrag an die Liste angehängt. Suche: Hash berechnen, dann die Liste im Bucket durchlaufen.
Open Addressing Bei einer Kollision wird der nächste freie Slot gesucht (lineares Probing, quadratisches Probing oder Double Hashing). Alle Einträge bleiben direkt im Array.

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

Vor Rehashing: 75% Füllgrad, Ketten werden länger, Suche wird langsamer
Nach Rehashing: Doppelte Größe, kurze Ketten, schnelle Suche wiederhergestellt

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.

Steuerung
Hashtabelle
0
—
1
—
2
—
3
—
4
—
5
—
6
—
7
—
8
—
9
—

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. 1. L1-Cache: ~1 nsschnellster, kleinster Speicher
  2. 2. L2-Cache: ~5 ns
  3. 3. L3-Cache: ~20 ns
  4. 4. RAM: ~100 ns
  5. 5. SSD: ~100 μs1.000× langsamer als RAM
  6. 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

  1. 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.
  2. 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.
  3. 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

Noch offen

Was macht eine Hash-Funktion?

Wähle eine Antwort

Auflösung: 1) B · 2) C · 3) B · 4) B

Prüfen

Checkpoint: Schlüsselbasierte Datenstrukturen

Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.

0 von 3 sitzen