Im Jahr 1953 erfand Hans Peter Luhn, Forscher bei IBM, die Hash-Tabelle — die Datenstruktur, die wie keine andere modernes Programmieren von naivem scheidet. Der Kniff war einfach zu beschreiben und Mathematikern seit Jahrzehnten in Andeutungen vertraut: statt eine Liste nach einem Schlüssel zu durchsuchen, berechne den Ort aus dem Schlüssel selbst — mit einer Funktion (der Hashfunktion), die Schlüssel auf Array-Indizes abbildet, sodass Lookup, Einfügen und Löschen im Mittel O(1) statt O(n) werden. Hash-Tabellen, Listen, Bäume, Graphen, Heaps, Warteschlangen, Stacks — diese kleine Familie organisierender Formen ist die erste architektonische Entscheidung, die ein Programmierer trifft, wenn er sich an ein Problem setzt, und der Buchtitel Niklaus Wirths von 1976 — Algorithmen + Datenstrukturen = Programme — hält das Verhältnis knapp fest: der Algorithmus sagt, was zu tun ist, die Datenstruktur, woran, und beides zusammen ist das Programm.
Die großen Familien sind überraschend wenige. Lineare Strukturen — Arrays (O(1) wahlfreier Zugriff, O(n) Einfügen in der Mitte) und verkettete Listen (O(1) Einfügen am Kopf, O(n) wahlfreier Zugriff) — sind die schlichtesten; das Zugriffsmuster entscheidet. Hash-Tabellen (Luhns Beitrag) liefern bei Lookup, Einfügen und Löschen im Mittel O(1), brechen aber auf O(n) ein, sobald böswillige Eingabe Kollisionen erzwingt — die Hash-Flooding-Angriffe von 2011 nutzten genau das aus, gegengesteuert wurde mit randomisierten Hashfunktionen. Bäume spannen das Universum vergleichsorganisierter Daten auf: binäre Suchbäume (ausgeglichen O(log n), unausgeglichen O(n)), selbstausgleichende Varianten (Rot-Schwarz, AVL, B-Baum, B+-Baum) liegen nahezu jeder relationalen Datenbank (Postgres, MySQL, SQLite) und vielen Dateisystemen zugrunde, Tries tragen die Autovervollständigung, Heaps setzen Prioritätswarteschlangen und Dijkstras Algorithmus um. Graphen (Adjazenzliste für dünne, Adjazenzmatrix für dichte) sind das Substrat sozialer Netzwerke, des Internets und von Abhängigkeitsgraphen, während Spezialstrukturen ihre Nischen besetzen: Bloom-Filter prüfen probabilistisch Mengenmitgliedschaft bei einstellbarer Falsch-Positiv-Rate, Skip-Listen sind die probabilistische Alternative zu balancierten Bäumen (in Redis im Einsatz), und persistente Datenstrukturen tragen funktionale Programmierung und Gits inhaltsadressierte Speicherung. Die tiefere Einsicht: die Wahl der Datenstruktur entscheidet über Performance stärker als jede andere Einzelentscheidung — eine schlechte Wahl macht ein System leicht um den Faktor 1000 zu langsam, und die Reparatur ist selten der Algorithmus, sondern die Struktur selbst. Wiederkehrende Trade-offs sind Zeit gegen Speicher (Hash-Tabellen sind schnell, aber speicherhungrig; Bloom-Filter sparen Speicher, lassen aber Falsch-Positive zu), leseoptimiert gegen schreiboptimiert (B-Bäume bevorzugen Lesezugriffe, Log-Structured-Merge-Bäume in LevelDB, RocksDB, Cassandra und BigTable hohen Schreibdurchsatz) und die Cache-Lokalität — moderne CPUs greifen auf sequentiellen Speicher rund 100-mal schneller zu als auf wahlfreien, sodass Arrays und Vektoren zeigerverfolgenden Strukturen oft weit überlegen sind, auch wenn die Big-O-Analyse das Gegenteil suggeriert.
Moderner Produktionscode nutzt diese Strukturen überall: Hash-Tabellen in nahezu jeder Standardbibliothek (`std::unordered_map`, `HashMap`, `dict`, `Map`), B-Bäume und LSM-Bäume in jeder größeren Datenbank, persistente Datenstrukturen in funktionalen Sprachen und in Git, Tries in Autovervollständigung und IP-Routing-Tabellen, Bloom-Filter in Netzwerkprotokollen und verteilten Datenbanken. Cachefreundliche Varianten wie Googles Flat-Hashmaps und das Robin-Hood-Hashing tauchen in performance-kritischem Code auf. Die heutige Front sind Vektordatenbanken (Pinecone, Weaviate, FAISS, Milvus, pgvector) für die hochdimensionale Nearest-Neighbour-Suche, in der klassische Strukturen am Fluch der Dimensionalität scheitern; die Datenstrukturen dahinter — HNSW, LSH, Produktquantisierungsindizes — sind aktives Forschungsfeld und liegen jedem retrieval-augmentierten LLM-System zugrunde. Die Hauptintuition des arbeitenden Programmierers ist die Passung zwischen Datenanordnung und Zugriffsmuster, und der dauerhafteste Beitrag der Disziplin zur Ingenieurpraxis ist das Vokabular selbst.