Vor etwa 70 Jahren änderte ein Ingenieur bei IBM namens Hans Peter Luhn still und heimlich den Kurs der Informatik. Luhn besaß bereits mehrere Patente, darunter eines für ein Gerät, das die Fadenzahl eines Tuchs messen konnte, und ein weiteres für einen Leitfaden, der festlegte, welche Mixgetränke man aus den Zutaten in seiner Küche zubereiten konnte. In einem internen IBM-Artikel aus dem Jahr 1953 schlug er jedoch eine neue Technik zum Speichern und Abrufen von Informationen vor, die heute in nahezu allen Computersystemen integriert ist: die Hash-Tabelle.

Hash-Tabellen sind eine Hauptklasse von Datenstrukturen. Sie bieten eine besonders bequeme Möglichkeit, auf Informationen in umfangreichen Datenbanken zuzugreifen und diese zu ändern. Diese Technologie bringt jedoch einen unvermeidbaren Kompromiss mit sich.

In einer 1957 Krepppapier veröffentlicht im IBM Journal für Forschung und EntwicklungW. Wesley Peterson identifizierte die größte technische Herausforderung, die Hash-Tabellen mit sich bringen: Sie müssen schnell sein, das heißt, sie können die notwendigen Informationen schnell abrufen. Sie müssen aber auch kompakt sein und so wenig Speicher wie möglich verbrauchen. Diese beiden Ziele stehen grundsätzlich im Widerspruch zueinander. Der Zugriff auf und die Änderung einer Datenbank können schneller erfolgen, wenn die Hash-Tabelle über mehr Speicher verfügt. und Vorgänge werden in Hash-Tabellen, die weniger Platz beanspruchen, langsamer. Seit Peterson diese Herausforderung formuliert hat, versuchen Forscher, das beste Gleichgewicht zwischen Zeit und Raum zu finden.

Informatiker haben nun mathematisch bewiesen, dass sie den optimalen Kompromiss gefunden haben. Die Lösung kam von a Paar der letzten Zeit Papiere die sich gegenseitig ergänzten. „Diese Papiere lösen die seit langem offene Frage nach den bestmöglichen Raum-Zeit-Kompromissen und liefern zutiefst überraschende Ergebnisse, von denen ich erwarte, dass sie noch viele Jahre lang erhebliche Auswirkungen haben werden“, sagte er Michael Mittenmacher, ein Informatiker an der Harvard University, der an keiner der beiden Studien beteiligt war.

„Ich würde definitiv sagen, dass es eine große Sache ist“, fügte er hinzu Rasmus Pagh, Informatiker an der Universität Kopenhagen. „Viele Leute haben an diesem Problem gearbeitet und versucht herauszufinden, wie viel Platz man sparen und gleichzeitig zeiteffizient arbeiten kann. Das ist das Problem, das ich gerne gelöst hätte.“

Einen Hash daraus machen

Hash-Tabellen gehören heute zu den ältesten, einfachsten, schnellsten und am weitesten verbreiteten Datenstrukturen. Sie dienen dazu, drei grundlegende Vorgänge auszuführen: Einfügungen, bei denen neue Elemente zur Datenbank hinzugefügt werden; Abfragen, die auf ein Element zugreifen oder prüfen, ob es existiert; und Löschungen. Eine Hash-Tabelle kann kurzlebig sein – also nur so lange existieren, wie ein bestimmtes Programm ausgeführt wird – oder sie kann ein dauerhafter Bestandteil des Betriebssystems Ihres Computers sein. Ein Webbrowser wie Chrome oder Safari verfügt möglicherweise über mehrere integrierte Hash-Tabellen, die dazu dienen, den Überblick über verschiedene Arten von Daten zu behalten.

Einträge in einer Hash-Tabelle werden als Paare gespeichert, wobei das Element – ​​die Informationen selbst – mit einem Schlüssel verbunden ist, der die Informationen identifiziert. Fügen Sie einen Schlüssel in den Abfragealgorithmus einer Hash-Tabelle ein und Sie gelangen direkt zum Element. Das klingt vielleicht nicht so außergewöhnlich, kann aber bei riesigen Datenbanken eine große Zeitersparnis bedeuten.

Um ein extrem vereinfachtes Beispiel zu nehmen, betrachten wir das Oxford English Dictionary, das Definitionen für mehr als 600,000 Wörter enthält. Wenn eine digitale Ausgabe auf einer Hash-Tabelle basiert, können Sie einfach ein bestimmtes Wort als Schlüssel verwenden und direkt mit der Definition fortfahren. Ohne eine Hash-Tabelle würde das Wörterbuch wahrscheinlich auf einen viel langsameren Suchmechanismus angewiesen sein und einen Eliminierungsprozess verwenden, um schließlich zur angeforderten Definition zu gelangen. Und während eine Hash-Tabelle jedes Wort in einer konstanten Zeitspanne (normalerweise in einem winzigen Bruchteil einer Sekunde) finden kann, kann die Suchzeit bei anderen Methoden mit zunehmender Anzahl von Wörtern im Wörterbuch ansteigen. Eine Hash-Tabelle bietet noch einen weiteren Vorteil: Sie kann das Wörterbuch dynamisch halten und so das Einfügen neuer Wörter und das Löschen veralteter Wörter erleichtern.

Forscher haben Jahrzehnte damit verbracht, Hash-Tabellen zu erstellen, die versuchen, die Geschwindigkeit zu maximieren und den Speicher zu minimieren. Im 20. Jahrhundert boten Lösungen tendenziell erhebliche Vorteile nur in einem Aspekt, sei es zeitlich oder räumlich. Dann im Jahr 2003, Forscher zeigte dass es theoretisch möglich sei, sowohl zeitlich als auch räumlich gleichzeitig einen großen Effizienzsprung zu machen. Es würde jedoch noch zwei Jahrzehnte dauern, bis die Forscher das ideale Gleichgewicht zwischen beiden gefunden hätten.

Der Datenmix

Der erste große Schritt in Richtung dieses Ziels erfolgte im Jahr 2022 bei a Große Informatikkonferenz in Rom. Dort schlug ein Team eine Hash-Tabelle mit neuen Funktionen vor, die die bisher beste Kombination aus Zeit- und Platzeffizienz bieten könnte. Der erste Autor des Artikels (in alphabetischer Reihenfolge) war Michael Bender von der Stony Brook University, daher wird er allgemein als Bender et al. bezeichnet. Hash-tabelle. Das Team versuchte zwar nicht, eine funktionierende Hash-Tabelle zu erstellen, bewies jedoch, dass diese im Prinzip mit den von ihnen beschriebenen Funktionen erstellt werden kann.

Um die von ihnen erstellte Hash-Tabelle auszuwerten, erstellte die Gruppe eine Kompromisskurve – ein Diagramm, das die Zeit pro Vorgang (Einfügung oder Löschung) auf einer Achse und den vom Speicher belegten Platz auf der anderen Achse darstellt. Dieses Diagramm definiert den Speicherplatz jedoch auf besondere Weise: Hash-Tabellen benötigen aufgrund ihres Aufbaus mehr Speicher als nur das absolute Minimum, das zum Speichern einer bestimmten Menge von Elementen erforderlich ist. Informatiker nennen diesen zusätzlichen Speicherplatz „verschwendete Bits“, obwohl sie nicht wirklich verschwendet und in gewissem Maße notwendig sind. Die Raumachse auf einer Kompromisskurve misst die Anzahl der verschwendeten Bits pro Schlüssel.

Durch die Analyse einer Kompromisskurve können Forscher die schnellstmögliche Zeit für eine Hash-Tabelle ermitteln, die einen bestimmten Speicherplatz beansprucht. Sie können die Frage auch umdrehen, um den kleinstmöglichen Platz für eine bestimmte Operationszeit zu ermitteln. Normalerweise führt eine kleine Änderung einer Variablen zu einer kleinen Änderung der anderen, sagte er William Kuszmaul, ein theoretischer Informatiker in Harvard und Mitautor der Arbeit von 2022. „Wenn Sie die Zeit verdoppeln, halbieren Sie möglicherweise die Anzahl der verschwendeten Bits pro Schlüssel.“

Bei der von ihnen entworfenen Hash-Tabelle ist das jedoch nicht der Fall. „Wenn man die Zeit ein wenig verlängert, sinken die verschwendeten Bits pro Schlüssel exponentiell“, sagte Kuszmaul. Die Kompromisskurve war so steil, dass sie buchstäblich außerhalb der Charts lag.

Das Team baute seine Hash-Tabelle in zwei Teilen auf. Sie verfügten über eine primäre Datenstruktur, in der die Elemente ohne jegliche verschwendete Bits gespeichert werden, und eine sekundäre Datenstruktur, die einer Abfrage dabei hilft, das gesuchte Element zu finden. Obwohl die Gruppe den Begriff einer sekundären Datenstruktur nicht erfunden hat, machte sie eine entscheidende Entdeckung, die ihre hypereffiziente Hash-Tabelle ermöglichte: Die Gesamtspeichereffizienz der Struktur hängt davon ab, wie die primäre Struktur ihre gespeicherten Elemente anordnet.

Die Grundidee besteht darin, dass jeder Artikel in der Primärstruktur bevorzugte Lagerorte hat – einen besten Ort, einen zweitbesten, einen drittbesten und so weiter. Befindet sich ein Element an seinem besten Platz, wird ihm die Nummer 1 zugeordnet und diese Nummer in der sekundären Datenstruktur gespeichert. Als Antwort auf eine Anfrage liefert die Sekundärstruktur lediglich die Zahl 1, die die genaue Position des Artikels in der Primärstruktur angibt.

Befindet sich das Element an der 100. Stelle, hängt die sekundäre Datenstruktur die Zahl 100 an. Und da das System binär arbeitet, stellt es die Zahl 100 als 1100100 dar. Es braucht natürlich mehr Speicher, um die Zahl 1100100 als 1 zu speichern – die Nummer, die einem Gegenstand zugewiesen wird, wenn er sich an der besten Stelle befindet. Solche Unterschiede werden erheblich, wenn Sie beispielsweise eine Million Artikel lagern.

Das Team erkannte also, dass man durch die kontinuierliche Verschiebung von Elementen in der primären Datenstruktur an ihre bevorzugten Speicherorte den von der sekundären Struktur verbrauchten Speicher erheblich reduzieren könnte, ohne die Abfragezeiten verlängern zu müssen.

„Vor dieser Arbeit wusste niemand, dass man die Datenstruktur durch das Verschieben von Informationen weiter komprimieren kann“, sagte Pagh. „Das war die große Erkenntnis des Bender-Papiers.“

Die Autoren zeigten, dass ihre Erfindung eine neue Obergrenze für die effizientesten Hash-Tabellen festlegte, was bedeutete, dass es sich um die beste Datenstruktur handelte, die jemals in Bezug auf Zeit- und Platzeffizienz entwickelt wurde. Aber die Möglichkeit blieb bestehen, dass jemand anderes es noch besser machen könnte.

Mit Erfolg verbunden

Im nächsten Jahr wurde ein Team unter der Leitung von Huacheng Yu, ein Informatiker an der Princeton University, versuchte, die Hash-Tabelle des Bender-Teams zu verbessern. „Wir haben wirklich hart gearbeitet und konnten es nicht schaffen“, sagte er Renfei Zhou, ein Student an der Tsinghua-Universität in Peking und Mitglied von Yus Team. „Da vermuteten wir, dass ihre Obergrenze [auch] eine Untergrenze war“ – das Beste, was überhaupt erreicht werden kann. „Wenn die Obergrenze der Untergrenze entspricht, ist das Spiel vorbei und Sie haben Ihre Antwort.“ Egal wie schlau Sie sind, keine Hash-Tabelle kann es besser.

Yus Team wandte eine neuartige Strategie an, um herauszufinden, ob diese Vermutung richtig war, indem es eine Untergrenze auf der Grundlage erster Prinzipien berechnete. Erstens argumentierten sie, dass eine Hash-Tabelle – oder eigentlich jede Datenstruktur – mehrmals auf den Speicher des Computers zugreifen muss, um eine Einfügung oder Löschung durchzuführen. Wenn sie herausfinden könnten, wie oft eine platzsparende Hash-Tabelle mindestens benötigt wird, könnten sie diese mit der pro Zugriff erforderlichen Zeit (einer Konstante) multiplizieren und so eine Untergrenze für die Laufzeit erhalten.

Aber wenn sie nichts über die Hash-Tabelle wussten (außer dass sie platzsparend war), wie konnten die Forscher dann herausfinden, wie oft mindestens erforderlich war, um auf den Speicher zuzugreifen? Sie leiteten es rein theoretisch ab und verwendeten dabei ein scheinbar unabhängiges Fachgebiet namens Theorie der Kommunikationskomplexität, das untersucht, wie viele Bits erforderlich sind, um Informationen zwischen zwei Parteien zu übermitteln. Schließlich gelang es dem Team: Sie fanden heraus, wie oft eine Datenstruktur pro Vorgang auf ihren Speicher zugreifen muss.

Dies war ihr größter Erfolg. Anschließend konnten sie eine untere Laufzeitgrenze für jede platzsparende Hash-Tabelle festlegen. Und sie sahen, dass es genau mit der Bender-Hash-Tabelle übereinstimmte. „Wir dachten [zuerst], dass es verbessert werden könnte“, sagte Zhou. „Es stellte sich heraus, dass wir falsch lagen.“ Das wiederum bedeutete, dass Petersons Problem endlich gelöst war.

Neben der Beantwortung der jahrzehntealten Frage, sagte Kuszmaul, sei das Erstaunliche am Yu-Beweis seine Allgemeingültigkeit. „Ihre Untergrenze gilt für alle möglichen Datenstrukturen, auch für solche, die noch nicht erfunden wurden.“ Das bedeutet, dass keine Methode zur Datenspeicherung jemals die Bender-Hash-Tabelle in Bezug auf Speicher und Geschwindigkeit übertreffen kann.

Hashing in die Zukunft

Trotz der beispiellosen Effizienz der neuen Hash-Tabelle wird in naher Zukunft wahrscheinlich niemand versuchen, sie zu erstellen. Der Aufbau ist einfach zu kompliziert. „Ein Algorithmus, der in der Theorie schnell ist, ist nicht unbedingt auch in der Praxis schnell“, sagte Zhou.

Es sei nicht ungewöhnlich, dass solche Lücken zwischen Theorie und Praxis lange bestehen bleiben, sagte Kuszmaul, weil Theoretiker dazu neigen, konstante Faktoren zu ignorieren. Die für die Ausführung einer Operation benötigte Zeit wird typischerweise mit einer Zahl multipliziert, einer Konstante, deren genauer Wert aus theoretischer Sicht unerheblich sein kann. „Aber in der Praxis sind Konstanten wirklich wichtig“, sagte er. „In der realen Welt bedeutet ein Faktor 10 ein Spielende.“

Tatsächliche Hash-Tabellen verbessern sich immer noch in materieller Hinsicht, auch wenn sie weit hinter dem theoretischen Ideal zurückbleiben. Zum Beispiel eine neue Hash-Tabelle namens EisbergHT, gebaut von Bender, Kuszmaul und anderen, ist weitaus besser als seine Vorgänger. Laut Kuszmaul ist sie doppelt so schnell wie die derzeit platzsparendste Hash-Tabelle und benötigt dreimal weniger Platz als die schnellste Hash-Tabelle.

Mitzenmacher hofft, dass das Ergebnis von 2023 bald einen weiteren Nutzen bringen könnte: „Wann immer man eine neue Untergrenze erhält – insbesondere eine, die einige neue Techniken beinhaltet – besteht immer die Hoffnung, dass man sie nutzen kann … für damit verbundene Probleme.“

Hinzu kommt die intellektuelle Befriedigung, die sich aus dem Wissen ergibt, ein schwieriges und seit langem bestehendes Problem gelöst zu haben, sagte der Informatiker Piotr Indyk des Massachusetts Institute of Technology. „Wenn Sie sicher sind, dass bestimmte Datenstrukturen nicht verbessert werden können, kann dies dazu beitragen, den Forschungsaufwand zu fokussieren.“ Endlich können Datenforscher ihre Aufmerksamkeit von Petersons Herausforderung abwenden und sich auf neue Probleme in der theoretischen Informatik konzentrieren, an denen es keinen Mangel gibt.