Datenstrukturen

Hashtabellen, Bäume, Graphen, Heaps: eine Handvoll Ordnungsformen — und die Wahl entscheidet, was schnell ist.

Als Nächstes empfohlen → Compiler & Interpreter · CS·KI

Der Beitrag

Im Jahr 1953 hatte ein IBM-Forscher namens Hans Peter Luhn eine trügerisch einfache Idee. Statt eine Liste zu durchsuchen, um etwas zu finden — warum nicht aus dem Ding selbst berechnen, wo es liegen sollte? Eine Funktion verwandelt den Schlüssel unmittelbar in eine Adresse, sodass ein Lookup, der das Durchmustern von einer Million Einträgen bedeutet hätte, im Mittel zu einem einzigen Schritt wird. Luhns Hash-Tabelle ist die Erfindung, die wie keine andere flüssiges Programmieren von unbeholfenem scheidet. Sie gehört zu einer kleinen Familie organisierender Formen — Listen, Bäume, Graphen, Heaps, Stacks, Warteschlangen —, unter denen ein Programmierer wählt, ehe er eine Zeile Logik schreibt. Wie Niklaus Wirths Buchtitel es in eine Losung fasste, Algorithmen + Datenstrukturen = Programme: Der Algorithmus sagt, was zu tun ist, die Struktur, woran.

Die Formen sind wenige, weil jede eine Frage gut beantwortet und anderswo dafür bezahlt. Ein Array gewährt sofortigen Zugriff auf jedes Element über seine Position, wächst aber nur langsam in der Mitte; eine verkettete Liste ist das genaue Gegenteil. Eine Hash-Tabelle findet Dinge in einem einzigen mittleren Schritt, verstreut sie aber über den Speicher. Ein Baum hält seine Daten sortiert, sodass eine Suche das Problem bei jedem Schritt halbiert — weshalb nahezu jede Datenbank und jedes Dateisystem im Untergrund ein Baum ist. Ein Graph modelliert alles, was sich über seine Verbindungen definiert: ein soziales Netz, das Web, ein Gewirr von Softwareabhängigkeiten. Die Lehre unter allen ist, dass wie die Daten angeordnet sind, für die Leistung entscheidender ist als fast jede andere Entscheidung eines Programmierers. Dieselbe Aufgabe kann tausendmal schneller oder langsamer laufen, allein je nach der Struktur, die die Daten hält, und wenn ein Programm kriecht, ist die Heilung meist kein klügerer Algorithmus, sondern ein besser geformter Behälter. Zwei Kräfte lenken die Wahl. Die eine ist der alte Tausch von Geschwindigkeit gegen Speicher — eine Hash-Tabelle ist schnell, aber hungrig, während eine schlankere Struktur Platz zurückkauft, indem sie die gelegentliche falsche Antwort duldet. Die andere ist die Hardware selbst: Ein moderner Prozessor liest Speicher in gerader Linie rund hundertmal schneller, als er umherspringt, sodass ein schlichtes Array oft eine theoretisch überlegene, aber mit verstreuten Zeigern durchsetzte Struktur schlägt, was auch immer die abstrakte Analyse verspricht.

Warum jetztDiese Formen sind überall im arbeitenden Code — die Hash-Tabelle hinter dem eingebauten Wörterbuch jeder Sprache, der balancierte Baum hinter jedem Datenbankindex, der inhaltsadressierte Speicher hinter Git. Die lebendige Front ist die Suche in sehr hohen Dimensionen, wo die Bedeutung eines Bildes oder eines Satzes als lange Zahlenreihe kodiert ist und gewöhnliche Strukturen versagen, weil am Ende alles ungefähr gleich weit von allem entfernt liegt. Die Spezialindizes, die das handhabbar machen — die Maschinerie in Vektordatenbanken —, sitzen heute im Herzen jedes Systems, das ein Sprachmodell nachschlagen lässt, was es wissen muss. Doch das dauerhafteste Geschenk des Fachs ist bescheidener als jede einzelne Struktur: Es ist das Vokabular selbst und die Gewohnheit, vor allem anderen zu fragen, welche Form die Daten annehmen wollen.