Datenstrukturen und Big O im Einsatz: Hashmap, amortisierte Kosten und Strukturwahl

Track Konzepte · Datenstrukturen und Algorithmen · ca. 45 Min.

Worum es geht

Ein Endpunkt prüft pro Request, ob eine Event-ID schon verarbeitet wurde. Mit 1000 IDs in einer Liste merkt das niemand. Mit zehn Millionen ist der Server am Limit, weil jede Prüfung die ganze Liste durchläuft. Dieselbe Prüfung mit einem Set ist im Schnitt unabhängig von der Menge. Der Unterschied steckt nicht im Code, sondern in der Datenstruktur (data structure) und in ihrem Kostenverhalten, das man in Big O ausdrückt.

Am Ende dieses Teils kannst du:

  • erklären, warum ein Hashmap-Lookup meist O(1) kostet und wann er zu O(n) wird (Übung 1),
  • erklären, warum ein wachsendes Array trotz gelegentlichem Kopieren im Schnitt O(1) pro Anhängen kostet, und eine Wachstumsregel dafür bauen (Übung 2),
  • zu einer Aufgabe mit Randbedingungen die passende Struktur wählen (Übung 3).

Bloom Filter (probabilistische Strukturen) und Consistent Hashing folgen in Teil 2. Nicht Thema: Graphenalgorithmen (Dijkstra, topologische Sortierung) und Storage Engines (B-Baum, LSM-Tree, WAL). Sie bekommen eigene Lektionen. Index-Strukturen in Datenbanken und die B-Baum-Analogie stehen in Lektion 2, hier wiederholen wir sie nicht.

Plane ehrlich 45 Minuten ein: etwa 20 Minuten Lesen, 25 Minuten Übungen (drei Stück). Eine gute Pause ist nach Übung 2.

Von JS/TS her gedacht

Die Strukturen kennst du schon, nur unter anderen Namen:

Idee JS/TS Python
Array mit Index Array list
Schlüssel zu Wert Map (oder Objekt) dict
Menge ohne Duplikate Set set
Stack push und pop am Array-Ende list.append und list.pop()
Queue push und shift (oder eine Ring-Struktur selbst gebaut) collections.deque
Priority Queue keine eingebaute (Bibliothek oder selbst) heapq

Dasselbe Programm in beiden Sprachen, in JavaScript mit Node ausgeführt: IDs deduplizieren und zählen.

const ids = ["a1", "b2", "a1", "c3", "b2"];
const eindeutig = new Set(ids);
const zaehler = new Map();
for (const id of ids) zaehler.set(id, (zaehler.get(id) ?? 0) + 1);
console.log(eindeutig.size, eindeutig.has("c3"), [...zaehler]);

Ausgabe:

3 true [ [ 'a1', 2 ], [ 'b2', 2 ], [ 'c3', 1 ] ]

Und in Python (Ausgabe 3 True und danach die Paare):

Ausgabe: 3 True und [('a1', 2), ('b2', 2), ('c3', 1)]. Map und dict sind beide Hashmaps (hash map, Hashtabelle). Genau von denen handelt der zweite Schritt.

Konzept

Schritt 1: Big O als Gefühl, nicht als Mathematik

Big O beschreibt, wie die Kosten (Schritte oder Speicher) mit der Eingabegröße n wachsen. Du brauchst nur ein Gefühl für fünf Klassen:

Klasse Name Gefühl Beispiel
O(1) konstant (constant) egal wie groß n ist Listenindex liste[5]
O(log n) logarithmisch n verdoppeln kostet einen Schritt mehr binäre Suche
O(n) linear n verdoppeln verdoppelt die Kosten Liste durchsuchen
O(n log n) linearithmisch etwas mehr als linear gutes Sortieren (merge sort, Timsort)
O(n²) quadratisch (quadratic) n verdoppeln vervierfacht die Kosten zwei verschachtelte Schleifen über alle Elemente

Zwei Kurzthemen gehören dazu. Binäre Suche (binary search) halbiert in einer sortierten Liste bei jedem Schritt den Suchbereich. Das ist Divide and Conquer (teile und herrsche): ein Problem in kleinere Teile zerlegen, die Teile lösen, zusammensetzen. Sortierverfahren wie Merge Sort arbeiten genauso, deshalb O(n log n). Wie wenig Schritte das sind, siehst du bei einer Million Einträge:

Ausgabe: 20 Schritte, Index 388889 388889. Statt bis zu einer Million Vergleichen reichen 20. In Python nimmst du dafür das Modul bisect, du schreibst die Schleife nicht selbst.

Welche Struktur welche Kosten hat, ist der Kern dieser Lektion. Die wichtigsten Operationen in Python (allgemeines Fachwissen über CPython, die Kosten sind Standardwissen):

Struktur Stärke Teuer
list (Array) Index, append hinten (amortisiert O(1)) x in liste O(n), pop(0) und insert(0, x) O(n)
dict und set (Hashmap) Lookup, Einfügen, in im Schnitt O(1) Reihenfolge nach Größe, Bereichsabfragen; im Worst Case O(n)
deque Anhängen und Entnehmen an beiden Enden O(1) Zugriff in der Mitte
heapq (Priority Queue) kleinstes Element holen O(log n), Einfügen O(log n) beliebiges Element suchen O(n)
Sortierte Liste plus bisect Suche O(log n) Einfügen O(n), weil Elemente nachrücken
Graph als dict von Knoten zu Nachbarn Nachbarn eines Knotens in O(1) abrufen nichts Besonderes, es ist nur die Darstellung

Ein Muster mit heapq, das in Übung 3 vorkommt: die k größten Werte aus einem langen Strom behalten, ohne alle zu speichern. Du hältst einen Min-Heap, der nie mehr als k Einträge hat. Das kleinste Element liegt oben. Kommt ein neuer Wert, der größer ist als dieses kleinste Element, ersetzt er es (O(log k)), sonst wird er verworfen. Am Ende stehen im Heap die k größten. Speicher: O(k) statt O(n). Beispiel mit k = 3 und dem Strom 5, 1, 9, 3, 7, 8: Die ersten drei Werte füllen den Heap (5, 1, 9, das kleinste ist die 1). Die 3 ist größer als die 1 und ersetzt sie (Heap: 3, 5, 9). Die 7 ersetzt die 3 (5, 7, 9). Die 8 ersetzt die 5 (7, 8, 9). Am Ende stehen 7, 8 und 9 im Heap, die drei größten Werte.

Eine Warnung vorweg: Big O zählt Schritte, keine Sekunden. Es lässt Konstanten weg, und bei kleinem n kann eine einfache Liste schneller sein als eine “bessere” Struktur, weil Arrays im Speicher am Stück liegen und der CPU-Cache sie gut mag, Zeiger-Strukturen weniger (allgemeines Fachwissen, hier nicht gemessen, weil Zeitmessungen im Browser unzuverlässig sind). Darum misst du in dieser Lektion Schritte, nicht Zeit.

Schritt 2: Warum Hashmap-Lookups O(1) sind, und wann nicht

Eine Hashmap rechnet aus dem Schlüssel mit einer Hashfunktion (hash function) eine Zahl aus. Diese Zahl modulo Anzahl der Buckets ergibt den Bucket (Fach), in dem der Eintrag liegt. Beim Lookup rechnest du dasselbe, gehst direkt zum Bucket und vergleichst nur die Einträge darin. Ist der Bucket klein, ist der Lookup unabhängig von n: O(1).

Zwei verschiedene Schlüssel können im selben Bucket landen (Kollision, collision). Das ist normal, solange es wenige sind. Wir bauen eine Hashmap, die zählt, wie viele Schlüssel sie pro Lookup vergleicht:

Ausgabe:

alle in Bucket 0: (500.5, 1000)
sha256-Hash:      (2.924, 9)

Lies die Zahlen: Das Tupel ist (Vergleiche pro Lookup im Schnitt, längster Bucket). Bei einer Hashfunktion, die jedem Schlüssel 0 gibt, landen alle 1000 Einträge in einem Bucket. Ein Lookup durchsucht im Schnitt die halbe Liste (500.5 Vergleiche), die Hashmap ist zu einer Liste entartet: O(n). Mit gut gestreutem Hash sind es knapp 3 Vergleiche bei 256 Buckets und 1000 Einträgen.

Eine brauchbare Hashfunktion hat drei Eigenschaften:

  1. Deterministisch: derselbe Schlüssel ergibt immer dieselbe Zahl, sonst findest du nichts wieder.
  2. Gleichmäßig gestreut (uniform): auch ähnliche Schlüssel (order-1, order-2) landen in verschiedenen Buckets.
  3. Billig zu berechnen.

Wann ist ein Lookup also nicht O(1)? Erstens bei vielen Kollisionen, etwa durch eine schlechte Hashfunktion. Zweitens, wenn jemand absichtlich Schlüssel wählt, die kollidieren (Hash Flooding, ein Angriff auf Server: absichtlich Schlüssel schicken, die alle im selben Bucket landen, sodass jede Anfrage O(n) kostet). Aus diesem Grund ist der Hash von Strings in Python pro Prozess zufällig gesalzen (allgemeines Fachwissen). Drittens, wenn die Hashmap zu voll wird: Reale Hashmaps vergrößern die Bucket-Anzahl, sobald das Verhältnis Einträge zu Buckets (Load Factor) zu hoch wird. Dieses Vergrößern bringt uns zum nächsten Schritt.

In der ersten Übung bekommst du eine Hashfunktion, die “fast gut” aussieht und trotzdem über 20 Vergleiche pro Lookup braucht.

Schritt 3: Amortisierte Kosten, ein wachsendes Array

Eine Liste in Python (und Array in JS) ist ein Block im Speicher mit fester Kapazität (capacity). Ist er voll und kommt ein Element dazu, passiert das hier: Ein größerer Block wird angelegt, alle bisherigen Elemente werden kopiert, dann wird angehängt. Ein einzelnes append kann also O(n) kosten. Trotzdem sagt man “append ist O(1)”. Beides stimmt, wenn man amortisiert rechnet (amortized analysis): Man verteilt die seltenen teuren Schritte auf alle Operationen und betrachtet die Kosten pro Operation im Durchschnitt über eine lange Folge.

Wir zählen die Kopieroperationen in einer Simulation. naechste ist die Wachstumsregel: Sie bekommt die alte Kapazität und liefert die neue.

Ausgabe:

15 28
1000 1.023 124.5
10000 1.6383 1249.5
100000 1.31071 12499.5

Lies die erste Zeile: Bei 16 Elementen kostet Verdopplung (Kapazität 1, 2, 4, 8, 16) insgesamt 15 Kopien (1 + 2 + 4 + 8), fester Zuwachs von 4 schon 28. Die Tabelle darunter zeigt die Kopien pro Anhängen, je Zeile mit n Elementen: Bei Verdopplung bleibt der Wert klein und springt nie über 2 (1.023, 1.6383, 1.31071). Beim festen Zuwachs wächst er mit n (124.5, 1249.5, 12499.5): Er ist proportional zu n, also kostet das Anhängen im Schnitt O(n) und das Befüllen insgesamt O(n²).

Warum bleibt Verdopplung billig? Die Kopien bilden eine Reihe 1 + 2 + 4 + … bis höchstens n, und die Summe einer solchen Reihe ist kleiner als das Doppelte ihres letzten Gliedes. Also kommen auf n Anhängen weniger als 2n Kopien, im Schnitt unter zwei pro Anhängen (genau das zeigen die Werte 1.023, 1.6383 und 1.31071). Bei festem Zuwachs sind die Abstände zwischen den Kopier-Momenten konstant, die Kopien werden aber immer länger: Das addiert sich zu etwas Quadratischem.

Merke: Geometrisches Wachstum (Kapazität mal Faktor) ergibt amortisiert O(1). Additives Wachstum (Kapazität plus Konstante) ergibt amortisiert O(n). Die Faustregel hinter fast jeder dynamischen Struktur, auch hinter dem Vergrößern der Hashmap aus Schritt 2. Die Kehrseite: Nach einer Verdopplung ist der Block halb leer (Speicher gegen Kopierzeit).

Falle

  1. Hashfunktion, die nach Streuung aussieht, aber keine ist. Die Summe der Zeichencodes ist schnell und deterministisch, ordnet aber alle Wörter mit denselben Buchstaben gleich ein und deckt nur einen schmalen Zahlenbereich ab. Ergebnis: viele Kollisionen, O(n) statt O(1) (Übung 1).
  2. “O(1)” ohne “amortisiert” und “im Schnitt”. Ein append und ein Hashmap-Zugriff können einzeln teuer sein. Die Aussage gilt über eine Folge von Operationen bzw. über viele Schlüssel.
  3. Additives Wachstum. “Immer 100 mehr” fühlt sich harmlos an und ist quadratisch (Übung 2).
  4. Liste als Queue und Liste als Set. pop(0) und x in liste sind O(n). Bei kleinen Mengen unauffällig, bei großen ein Ausfall.

Übungen

Übung 1: Kaputter Hash, über 20 Vergleiche pro Lookup (ca. 8 Min.)

Ein Shop speichert Bestellnummern in einer Hashmap mit 256 Buckets (der ZaehlMap aus Schritt 2). Jemand hat als Hashfunktion die Summe der Zeichencodes geschrieben. Sie ist deterministisch, aber messe zeigt, dass ein Lookup im Schnitt 24 bis 28 Vergleiche braucht (je nach Schlüsselsorte). Repariere meine_hash: Sie bekommt einen String und liefert eine ganze Zahl. Ziel: im Schnitt unter 8 Vergleiche pro Lookup, bei mehreren Sorten von Schlüsseln (order-17, 00017, kunde:17:de), je 1000 Stück.

ZaehlMap und messe stehen bereit. Die letzte Zeile gibt die Funktion zurück, der Check misst sie.

Was haben "ab" und "ba" gemeinsam, und in welchem Zahlenbereich liegen die Summen von 5 bis 12 Zeichen langen Strings überhaupt? Wie könnte die Stelle, an der ein Zeichen steht, ins Ergebnis eingehen? Das Ergebnis muss für denselben Schlüssel immer dieselbe ganze Zahl sein.

def meine_hash(key):
    h = 7
    for zeichen in key:
        h = (h * 31 + ord(zeichen)) & 0xFFFFFFFF
    return h

print(messe(meine_hash, [f"{i:05d}" for i in range(1000)]))
meine_hash

Jedes Zeichen wird mit dem bisherigen Wert verrechnet (mal 31 plus Zeichencode), so zählt die Position mit und der Wertebereich ist groß (32 Bit). Das ist ein einfacher Polynom-Hash. Alternativ ginge hash(key) (in Python eingebaut) oder ein Teil eines SHA-256.

Übung 2: Wachstumsregel für ein Array bauen (ca. 8 Min.)

Ein Log-Puffer wächst, wenn er voll ist: Ein neuer Block wird angelegt, die vorhandenen Elemente werden kopiert. Die Anfangskapazität ist 4. Schreibe die Wachstumsregel naechste(kapazitaet), die aus der alten Kapazität die neue macht. Der Check simuliert das Anhängen von 1000, 10000 und 100000 Elementen wie in Schritt 3 und verlangt:

  • Amortisiert O(1): weniger als 3 Kopien pro Anhängen im Schnitt.
  • Nicht verschwenderisch: die Endkapazität ist höchstens das Vierfache der Elementzahl.
  • Das Ergebnis ist eine ganze Zahl und größer als die alte Kapazität.

Die letzte Zeile gibt die Funktion zurück.

Vergleiche in Schritt 3 die Zeile “Kapazität mal etwas” mit “Kapazität plus etwas”: Welche der beiden Regeln liefert Kopier-Momente, deren Abstand mit n mitwächst? Und denk an den Typ: Eine Kapazität von 6.5 Elementen gibt es nicht.

def naechste(kapazitaet):
    return kapazitaet * 2

naechste

Geometrisches Wachstum: Die Kopien bilden eine Reihe 4 + 8 + 16 + …, deren Summe kleiner als das Doppelte der Elementzahl bleibt. Auch kapazitaet * 3 // 2 (Faktor 1.5) erfüllt die Anforderungen und verschwendet weniger Speicher, kostet dafür etwas mehr Kopien.

Übung 3: Struktur wählen, vier Fälle (ca. 8 Min.)

Wähle in jedem Fall die Struktur mit der besten Antwort für die genannten Randbedingungen. Gib ein Tupel mit vier Buchstaben zurück, z. B. ("A", "B", "A", "D").

Fall 1: Ein Worker holt Jobs strikt in der Reihenfolge des Eingangs ab. Bis zu 500000 Jobs warten gleichzeitig, neue kommen hinten dazu, der Worker nimmt vorn weg. Es gibt keine Prioritäten, und jede dieser beiden Operationen soll möglichst wenig kosten.

  • A: set, Jobs einfügen, mit pop() jeweils ein Element entnehmen
  • B: deque, hinten anhängen, vorn mit popleft entnehmen
  • C: Liste, hinten mit append anfügen, vorn mit pop(0) entnehmen
  • D: Heap (heapq), die Eingangsnummer als Priorität, kleinste zuerst

Fall 2: Aus einem Strom von 10 Millionen Events sollen Duplikate verworfen werden. Für jede eingehende ID wird gefragt, ob sie schon vorkam. Die Reihenfolge der IDs ist egal. Die Antwort muss exakt sein (kein “vielleicht”), und die Prüfung soll im Schnitt nicht langsamer werden, wenn mehr IDs gesehen wurden.

  • A: Liste, vor dem Anhängen mit in die gesamte Liste durchsuchen
  • B: sortierte Liste, mit bisect suchen und die ID an der Stelle einsetzen
  • C: deque, hinten anhängen und beim Prüfen alle Einträge vergleichen
  • D: set, mit in prüfen und mit add einfügen

Fall 3: In einem Monorepo hängen 200 Module voneinander ab (rund 1000 Abhängigkeiten). Du willst zu einem Modul sofort alle direkten Abhängigkeiten abrufen und später prüfen können, ob es Zyklen gibt.

  • A: Graph als Adjazenzliste, ein dict von Modulname zu Liste der Abhängigkeiten
  • B: Stack, Module nacheinander darauflegen und wieder abnehmen
  • C: Priority Queue, Module nach Anzahl ihrer Abhängigkeiten geordnet
  • D: Array aller Modulnamen in der Reihenfolge, in der sie gebaut werden sollen

Fall 4: Aus einem Strom von 50 Millionen Bestellungen sollst du laufend die 10 teuersten bereithalten. Speicher gibt es nur für wenige Einträge, nicht für alle Bestellungen, und jede neue Bestellung soll schnell verarbeitet sein.

  • A: Min-Heap der Größe 10, eine teurere Bestellung ersetzt die kleinste darin
  • B: Liste aller Bestellungen, am Ende sortieren und die ersten 10 nehmen
  • C: dict von Bestellnummer zu Betrag, am Ende das Maximum suchen
  • D: set aller Bestellnummern, bei jeder neuen Nummer prüfen, ob sie neu ist

Frage dich pro Fall: Welche zwei oder drei Operationen kommen ständig vor, und welche Struktur macht genau diese billig? Achte auf Wörter wie “exakt”, “Speicher nur für wenige” und “Reihenfolge”.

antwort = ("B", "D", "A", "A")
antwort

Fall 1: deque (O(1) an beiden Enden, FIFO). Fall 2: set (exakt, in im Schnitt O(1)). Fall 3: Graph als Adjazenzliste (Nachbarn in O(1), Basis für Zyklensuche). Fall 4: Min-Heap der Größe k (Speicher O(k), je Bestellung O(log k)).

Merksatz

Die Struktur bestimmt die Kosten: Ein Hashmap-Lookup ist O(1), solange die Hashfunktion gut streut, und ein wachsendes Array ist amortisiert O(1), solange es mit einem Faktor wächst.

Prüfstein

  1. Warum ist ein Hashmap-Lookup meist O(1), und wann nicht? Nenne zwei Ursachen.
  2. Welche Struktur wählst du für eine Warteschlange, für eindeutige IDs, für Abhängigkeiten zwischen Modulen? Nenne je die Operation, die sie billig macht.

Weiter mit Teil 2: Bloom Filter und Consistent Hashing.

Quelle: quellen/konzeptuebersicht-software-grundlagen.md, Abschnitt “2. Datenstrukturen und Algorithmen” (Strukturen Array, Linked List, Hashmap, Set, Stack, Queue, Priority Queue, Baum, Graph; Big O; Rekursion und Divide and Conquer; Standardalgorithmen, Prüfsteine zu Hashmap und Strukturwahl). quellen/konzeptuebersicht-software-fortgeschritten.docx, Abschnitt “2. Algorithmen und Datenstrukturen im Einsatz” (Amortisierte Analyse; Cache-Realität).

Über die Quelle hinaus (allgemeines Fachwissen): die Kostentabelle der Python-Strukturen (CPython), die Erklärung von Load Factor und Hash Flooding und der Hinweis, dass Python-Strings mit zufälligem Salz gehasht werden, die Reihen-Argumentation zur Verdopplung, die Cache-Aussage zu Arrays (nicht gemessen). Alle Zahlen und Ausgaben in dieser Lektion stammen aus dem Ausführen des Codes mit Python 3 bzw. Node.