Datenstrukturen

Hashtabellen, Bäume, Graphen, Heaps: Es sind wenige Ordnungsformen, und welche man wählt, entscheidet über die Geschwindigkeit mehr als fast alles andere, was beim Programmieren zu entscheiden ist.

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

Der Beitrag

1953 kam einem IBM-Forscher namens Hans Peter Luhn ein täuschend einfacher Gedanke: Warum eine Liste durchsuchen, wenn sich aus dem gesuchten Ding selbst ausrechnen lässt, wo es liegen müsste? Eine Funktion macht aus dem Schlüssel direkt eine Adresse, und ein Nachschlagen, das eine Million Einträge hätte durchmustern müssen, schrumpft im Mittel auf einen einzigen Schritt. Luhns Hashtabelle ist die Erfindung, die wie keine zweite flüssiges von umständlichem Programmieren trennt. Sie gehört zu einer kleinen Familie ordnender Formen — Listen, Bäume, Graphen, Heaps, Stacks, Warteschlangen —, unter denen man sich entscheidet, bevor auch nur eine Zeile Logik entsteht. Niklaus Wirth hat das in einen Buchtitel gefasst, der zur Losung wurde: Algorithmen + Datenstrukturen = Programme. Der Algorithmus sagt, was zu tun ist; die Struktur sagt, woran.

Die Formen sind wenige, weil jede eine Frage gut beantwortet und dafür an anderer Stelle zahlt. Ein Array gibt jedes Element sofort über seine Position her, lässt sich in der Mitte aber nur mühsam erweitern; bei der verketteten Liste ist es genau umgekehrt. Eine Hashtabelle findet im Mittel in einem einzigen Schritt, verstreut ihre Einträge dafür über den ganzen Speicher. Ein Baum hält die Daten sortiert, sodass jede Suchstufe das Problem halbiert — der Grund, warum unter fast jeder Datenbank und jedem Dateisystem ein Baum liegt. Und ein Graph bildet ab, was sich allein über seine Verbindungen bestimmt: ein soziales Netz, das Web, ein Gestrüpp von Softwareabhängigkeiten. Die Lehre unter allen lautet, dass die Anordnung der Daten mehr über die Geschwindigkeit entscheidet als fast jede andere Entscheidung beim Programmieren. Dieselbe Aufgabe läuft tausendmal schneller oder langsamer, je nachdem welche Struktur die Daten hält, und wenn ein Programm kriecht, hilft selten ein klügerer Algorithmus, meist ein besser geschnittener Behälter. Zwei Kräfte lenken die Wahl. Die eine ist der alte Tausch Geschwindigkeit gegen Speicher — eine Hashtabelle ist schnell, aber hungrig, während eine schlankere Struktur Platz zurückgewinnt, indem sie sich gelegentlich eine falsche Antwort leistet. Die andere ist die Hardware: Ein moderner Prozessor liest Speicher der Reihe nach rund hundertmal schneller, als er darin herumspringt. Deshalb schlägt ein schlichtes Array oft die theoretisch überlegene Struktur, sobald diese mit verstreuten Zeigern durchsetzt ist — was die abstrakte Analyse auch verspricht.

Warum jetztDiese Formen stecken in jedem laufenden Programm — die Hashtabelle hinter dem eingebauten Wörterbuch jeder Sprache, der balancierte Baum hinter jedem Datenbankindex, der inhaltsadressierte Speicher hinter Git. Offen ist heute vor allem die Suche in sehr vielen Dimensionen: Wo die Bedeutung eines Bildes oder eines Satzes als lange Zahlenreihe kodiert ist, versagen die gewohnten Strukturen, weil am Ende alles von allem ungefähr gleich weit entfernt liegt. Die Spezialindizes, die das handhabbar halten — die Maschinerie in Vektordatenbanken —, sitzen inzwischen im Herzen jedes Systems, das ein Sprachmodell nachschlagen lässt, was ihm fehlt. Das haltbarste Geschenk des Fachs ist aber bescheidener als jede einzelne Struktur: das Vokabular selbst und die Gewohnheit, vor allem anderen zu fragen, welche Form die Daten annehmen wollen.