Bachelorarbeit stellt Grenzen der Hash-Tabellen-Suche auf den Kopf
(quantamagazine.org)- Andrew Krapivin, damals Undergraduate an der Rutgers University, entwarf angestoßen durch die Arbeit Tiny Pointers eine neue Hash-Tabelle und zeigte, dass sich die bisher angenommenen Grenzen bei Such- und Einfügeleistung übertreffen lassen
- In einer Arbeit vom Januar 2025 widerlegten Krapivin, Martín Farach-Colton und William Kuszmaul Yaos 40 Jahre alte Vermutung für eine bestimmte Kategorie von Hash-Tabellen
- Die bisherige Vermutung ging davon aus, dass für x, das den Füllgrad einer nahezu vollen Tabelle ausdrückt, die schlechteste Such- bzw. Einfügezeit nicht besser als x sein könne; die neue Struktur erreicht jedoch eine Zeit proportional zu (log x)²
- Die Forschenden zeigten zudem, dass (log x)² in der von Yao behandelten populären Kategorie von Hash-Tabellen eine optimale Schranke ist, die sich nicht weiter verbessern lässt, und dass bei nicht-gierigen Hash-Tabellen sogar eine durchschnittliche Suchzeit als Konstante unabhängig von x möglich ist
- Auch wenn sich daraus nicht sofort Anwendungen ergeben, schafft die Arbeit eine theoretische Grundlage, um die Leistungsgrenzen der alten Datenstruktur Hash-Tabelle neu zu ordnen und praktische Verbesserungen zu ermöglichen
Eine neue Hash-Tabelle, ausgehend von Tiny Pointers
- Andrew Krapivin stieß im Herbst 2021 als Undergraduate an der Rutgers University auf die Arbeit Tiny Pointers und kam zwei Jahre später beim genaueren Lesen auf eine Methode, noch kleinere Pointer zu bauen
- Weil die Daten, auf die die Pointer zeigen, besser organisiert werden mussten, rückte die Hash-Tabelle als gängige Form der Datenspeicherung in den Fokus der Forschung
- Im Verlauf der Experimente entwickelte Krapivin eine neue Hash-Tabelle, die nicht auf uniform probing beruht, und stellte fest, dass die Zeit und Zahl der Schritte zum Finden eines bestimmten Elements geringer waren als erwartet
- Martín Farach-Colton war zunächst skeptisch gegenüber dem Entwurf, doch William Kuszmaul erkannte, dass Krapivins Struktur nicht nur eine interessante Hash-Tabelle war, sondern eine 40 Jahre alte Vermutung zu Fall brachte
Das Problem der Leistungsgrenzen von Hash-Tabellen
- Hash-Tabellen sind Datenstrukturen zum Speichern und Zugreifen auf Daten und unterstützen grundsätzlich drei Operationen
- Ein Element abfragen (query)
- Ein Element löschen
- Ein Element in einen freien Slot einfügen
- Die ersten Hash-Tabellen reichen bis in die frühen 1950er Jahre zurück und sind seitdem eine alte, aber fortlaufend erforschte und genutzte Datenstruktur der Informatik
- Die Geschwindigkeitsgrenzen bei Suche oder Einfügen hängen meist damit zusammen, wie lange es dauert, in einer Hash-Tabelle einen freien Platz zu finden
- Wie voll eine Hash-Tabelle ist, lässt sich als Gesamtverhältnis ausdrücken, doch Forschende verwenden beim Umgang mit nahezu vollen Tabellen den Wert x
- Wenn x = 100, ist die Tabelle zu 99 % gefüllt
- Wenn x = 1.000, ist die Tabelle zu 99,9 % gefüllt
- Für bestimmte verbreitete Hash-Tabellen war bekannt, dass die erwartete schlechteste Einfügezeit, etwa beim Einfügen in den letzten verbliebenen freien Slot, proportional zu x ist
Yaos Vermutung von 1985 und ihre Widerlegung
- Andrew Yao vertrat in einer Arbeit von 1985 die Ansicht, dass bei Hash-Tabellen mit bestimmten Eigenschaften die beste Methode zum Finden einzelner Elemente oder freier Plätze im zufälligen Absuchen möglicher Positionen, dem uniform probing, liege
- Im schlimmsten Fall, also beim Finden des letzten verbleibenden freien Slots, gelte demnach die Vermutung, dass es nicht besser als x gehen könne; diese Annahme wurde 40 Jahre lang weitgehend als wahr akzeptiert
- Krapivin kannte Yaos Vermutung nicht, als er seine Untersuchungen im Zusammenhang mit Tiny Pointers vorantrieb, und entwickelte eine neue Hash-Tabelle, die nicht auf uniform probing beruht
- Die Arbeit vom Januar 2025 von Krapivin, Farach-Colton und Kuszmaul zeigt, dass bei dieser neuen Hash-Tabelle die schlechteste Such- und Einfügezeit proportional zu (log x)² ist
- Dieses Ergebnis steht in direktem Widerspruch zu Yaos Vermutung, und die Forschenden bewiesen zudem, dass (log x)² in der von Yao behandelten populären Kategorie von Hash-Tabellen eine optimale Schranke ist, die sich nicht weiter senken lässt
Ein noch überraschenderes Ergebnis zur durchschnittlichen Suchzeit
- Yao behandelte 1985 nicht nur die schlechteste Suchzeit, sondern auch die Durchschnittszeit über alle möglichen Suchvorgänge hinweg
- Für Hash-Tabellen mit bestimmten Eigenschaften, insbesondere gierige (greedy) Hash-Tabellen, bei denen neue Elemente an der ersten möglichen Position abgelegt werden müssen, bewies er, dass die Durchschnittszeit nicht besser als log x sein kann
- Farach-Colton, Krapivin und Kuszmaul wollten prüfen, ob dieselbe Grenze auch für nicht-gierige Hash-Tabellen gilt, und zeigten durch ein Gegenbeispiel, dass dies nicht der Fall ist
- Diese nicht-gierige Hash-Tabelle als Gegenbeispiel hat eine durchschnittliche Suchzeit, die weit besser als log x ist und tatsächlich überhaupt nicht von x abhängt
- Dass sich eine konstante durchschnittliche Suchzeit unabhängig davon erreichen lässt, wie voll die Hash-Tabelle ist, überraschte selbst die Forschenden
Eine theoretische Neubewertung einer alten Datenstruktur
- Alex Conway bezeichnete Hash-Tabellen als eine der ältesten Datenstrukturen und zugleich weiterhin als eine der effizientesten Methoden zur Datenspeicherung
- Guy Blelloch sieht das Ergebnis als elegant an, weil es ein klassisches Problem aufgreift und löst
- Sepehr Assadi bewertete die Arbeit so, dass das Forschungsteam nicht nur Yaos Vermutung widerlegt, sondern auch die beste Antwort auf seine Frage gefunden habe
- Conway meint, dass es wichtig ist, solche Datenstrukturen besser zu verstehen, auch wenn die Ergebnisse nicht sofort in Anwendungen münden
- Indem die theoretischen Grenzen von Hash-Tabellen neu geordnet werden, schafft diese Arbeit eine Grundlage, aus der später reale Leistungsverbesserungen entstehen könnten
1 Kommentare
Meinungen auf Hacker News
Krapivin gelang dieser Durchbruch, weil er Yaos Vermutung nicht kannte, und auch der Balatro-Entwickler schuf wohl ein preisgekröntes Spiel, weil er die bestehenden Deckbuilder nicht gut kannte.
Vielleicht ist der beste Weg, an ein Problem heranzugehen, die meisten früheren ähnlichen Versuche nicht zu kennen oder zu ignorieren.
Die Welt ist heute so vernetzt, dass man selten noch echte Neuheit sieht, die nicht in den Denkmustern der Vorgänger gefangen ist. Das Internet ist großartig, aber es ist schade, dass es Denken vereinheitlicht.
Meist führt das Ignorieren früherer Erfolge nur dazu, dass man erneut auf längst unfruchtbarem Boden sät.
Liest man die Vorarbeiten zu früh, bleibt man in bestehenden Denkweisen stecken; liest man sie gar nicht, verpasst man wichtige Dinge, auf die man selbst nicht gekommen wäre.
Selbst wenn der eigene Ansatz schlechter ist als der aktuelle Stand der Technik, kann man durch den Vergleich wichtige Einsichten gewinnen, warum der State-of-the-Art-Ansatz besser ist.
Laut einem direkten Zitat des Entwicklers war Luck be a Landlord der größte Einfluss auf Balatro; nachdem er einige Videos gesehen hatte, in denen Northernlion es spielte, gefiel ihm die Idee eines nicht auf Fantasy basierenden Score-Attack-Roguelikes, und er änderte das Kartenspiel, an dem er damals arbeitete, in ein Roguelike.
Von diesem Zeitpunkt an hielt er bewusst Abstand zum Genre und wollte den Designraum naiv erkunden, indem er selbst Fehler machte.
Er hört oft Vergleiche mit Slay the Spire, hatte dieses Spiel beim Design von Balatro aber weder gespielt noch Videos dazu gesehen und kam erst viel später damit in Berührung.
https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
„Aber ohne die Hilfe aller hätte ich es niemals geschafft“, widersprach [Milo].
„Vielleicht“, sagte Reason ernst. „Aber du hattest den Mut, es zu versuchen, und was du tun kannst, hängt meistens davon ab, was du tun willst.“
King Azaz sagte: „Deshalb gab es auf deinem Abenteuer eine sehr wichtige Sache, die wir dir nicht sagen konnten, bevor du zurückgekehrt warst.“
„Ich erinnere mich“, sagte Milo eifrig. „Sagen Sie es mir jetzt.“
„Es war unmöglich“, sagte der König und sah den Mathemagician an.
„Völlig unmöglich“, sagte der Mathemagician und sah den König an.
„Also …“, sagte der Käfer, dem plötzlich schwindlig wurde.
„Ja, genau“, sagten beide gemeinsam. „Aber hätten wir es dir damals gesagt, wärst du vielleicht nicht gegangen … und wie du erfahren hast, sind sehr viele Dinge möglich, solange man nicht weiß, dass sie unmöglich sind.“
— The Phantom Tollbooth (1961)
Weil bei mir einiges dazwischenkam, fiel ich in diesem Kurs durch und belegte ihn noch einmal, wobei mir eine Gewohnheit auffiel.
In jedem Semester stellte er bei einer der Aufgaben in der zweiten Semesterhälfte, in einem Set von etwa 30 Problemen, eine Aufgabe in einer Form, die tatsächlich ein offenes Problem war, und schickte ein oder zwei Tage vor Abgabeschluss eine Korrektur mit „Oh, das war ein Versehen“.
Da das immer genau einmal passierte, glaube ich nicht, dass es Zufall war.
monort [0] hat mit dem Link zum Video [1] sehr geholfen.
Eine kurze Zusammenfassung nach einmaligem Anschauen des Videos: Der Name ist Funnel Hashing.
Die Idee besteht darin, ein Array in exponentiell kleinere Teil-Arrays aufzuteilen. Der erste Block hat Größe n/m, der zweite n/(m^2) und so weiter, bis hinunter zu einzelnen Elementen. Wenn man sie A0, A1 usw. nennt, gilt |A0| = n/m, |A1| = n/(m^2), und insgesamt gibt es k Stufen.
Man versucht c-mal, in A0 einzufügen; wenn das fehlschlägt, versucht man es c-mal in A1. Wenn auch das fehlschlägt, steigt man den „Funnel“ hinab, bis man einen freien Slot findet.
\delta wird als Anteil freier Slots bezeichnet, aber ich bin mir nicht sicher, ob dieser Wert ein beim Erzeugen der Hash-Tabelle festgelegter Parameter ist oder dynamisch aktualisiert wird. Setzt man c = log(1/d) und k = log(1/d), ergibt sich im Worst Case eine Zeitkomplexität von O(log^2(1/d)).
Ich habe es so verstanden, dass dieses Verfahren nicht gierig ist und daher Yaos Ergebnis umgeht. Yaos Ergebnis gilt für gierige Einfüge- und Suchstrategien, während das obige Verfahren kaskadenartig den Funnel hinabgeht und damit nicht gierig ist.
Im Detail dürfte es viele knifflige Punkte geben, aber so weit habe ich die Idee verstanden. Falls ich völlig danebenliege, wäre ein Hinweis hilfreich.
Das erinnert stark an die Idee „Distinct Elements in Streams“ [2] von Chakraborty, Vinodchandran und Meel.
[0] https://news.ycombinator.com/item?id=43007860
[1] https://www.youtube.com/watch?v=ArQNyOU1hyE
[2] https://arxiv.org/pdf/2301.10191
Funnel Hashing ist „gierig“ und widerlegt Yaos Vermutung zu gierigen Hash-Mechanismen.
Elastic Hashing ist „nicht gierig“ und bietet eine bessere amortisierte Zeit als gierige Algorithmen.
Ich weiß nicht, ob der Artikel falsch ist oder ob das Paper missverstanden wurde, aber ich frage mich, ob der Artikelschreiber hier auf etwas hinweist, das ihm selbst nicht klar war.
Das scheint mit dem „special last level to catch a few keys“ etwa bei 14:41 im Video zusammenzuhängen; wenn aber auch das eine feste Größe haben muss, kann es voll werden. Was macht man dann?
[schamlose Eigenwerbung]: Wer sich für Hash-Tabellen interessiert, sollte sich auch Dandelion Hashtable [0] ansehen.
Wir verwenden sie in unserer Datenbank der nächsten Generation; sie wurde auf der HPDC'24 vorgestellt und ist derzeit nach realen Nutzungskriterien die schnellste In-Memory-Hash-Tabelle.
Durch Closed Addressing mit begrenztem Cacheline-Chaining verarbeitet sie auf normalen Servern mehr als eine Milliarde In-Memory-Requests pro Sekunde.
[0] https://dandelion-datastore.com/#dlht
Vortrag des Erfinders: https://www.youtube.com/watch?v=ArQNyOU1hyE
Es wirkt wie einer dieser Ressourcenmanagement-Tricks, die man anwendet, wenn man von Einschränkungen bedrängt wird und zu wenig Ressourcen hat.
Nach Prioritäten aufzuteilen ist bei der Ressourcenverteilung ein gängiger Ansatz, und dies ist eine Variante davon.
Ich frage mich, wie viele andere „Tricks aus dem Schützengraben“, die Leute in der Praxis gemacht haben und die nicht einmal die Erfinder selbst für bedeutend hielten, etwas weithin Akzeptiertes auf den Kopf stellen könnten. Etwa: „Wenn viel auszuliefern ist, habe ich eine clevere Methode gefunden, meist die schnellste Route zu zeichnen …“
Natürlich ist es eine große Leistung, das zu erkennen, zu formalisieren, auszuarbeiten und als Paper zu veröffentlichen. Das soll den Verdienst nicht schmälern.
Papers sollten einfach eine Videopräsentation enthalten.
Allerdings reserviert auch dieser Ansatz über Hilfs-Arrays zusätzlichen Speicher; daher fühlt es sich etwas seltsam an, warum das besser sein soll, als einfach überzureservieren, um die Wahrscheinlichkeit von Key-Kollisionen zu senken und auch den Worst Case weniger schlimm zu machen.
Beim Überfliegen des Papers [1] scheint der zentrale Unterschied darin zu liegen, dass der Einfügealgorithmus der Hash-Tabelle nicht gierig den ersten gefundenen freien Slot füllt, sondern weiter sucht.
In Kombination mit einer cleveren Sondierungsreihenfolge beweisen sie, dass freie Slots auch dann effizient gefunden werden, wenn die Tabelle sehr voll ist.
Das heißt: Einfügen wird langsamer, wenn die Hash-Tabelle weniger voll ist, dafür vermeidet man den Worst Case, in dem man suchen muss, ohne zu wissen, wo die letzten wenigen freien Slots liegen.
[1]: https://arxiv.org/pdf/2501.02305
Ein interessantes theoretisches Ergebnis, aber in der Praxis erwarte ich, dass der heutige „Trick“, eine größere Tabelle als nötig zu allokieren, die bessere Lösung ist.
Rusts hashbrown lässt zum Beispiel absichtlich 1/8 der Tabelle, also 12,5 %, frei; das verbraucht etwas mehr Speicher, macht Einfügen und Nachschlagen aber mit hoher Wahrscheinlichkeit sehr schnell.
Diese Methode erhöht auch dann die durchschnittliche Zahl der Sondierungspositionen, wenn die Tabelle weniger voll ist.
Innerhalb dieser Strategie platziert man den Eintrag aber weiterhin im ersten gefundenen freien Slot.
Das „Überspringen von Slots“ hängt damit zusammen, in der Hash-Reihenfolge nach vorne zu springen.
Hat jemand eine einfache Implementierung von „Tiny pointers“? Mein Kopf schaut lieber zuerst auf Code oder Pseudocode als auf Beweise.
Toll. Ich habe mich immer gefragt, ob es eine Möglichkeit gäbe, Tabellen auf diese Weise zu containerisieren.
Eine normale Tabelle ist wie ein Frachter, in den alles hineingestopft wird. Wenn man sie besser organisieren könnte, wie ein Containerschiff, ließe sich vermutlich viel mehr effizienter laden und auch schneller entladen.
Wandle die Tabellenzeilen in etwas wie einen String oder JSON um und wende dann base16 auf diese Variable an; daraus wird der base16-String dieser Daten.
Erstelle eine Hash-Tabelle und setze den Schlüsselwert für diesen base16-String, dann hast du einen Container mit den Daten.
Jetzt musst du nur noch den Hexadezimal-String dekodieren, um base32-Daten zu erhalten.
Die theoretischen Eigenschaften von Hash-Tabellen waren schon immer fast magisch beeindruckend, und dieses Ergebnis erweitert sie noch.
Was mir seltsam vorkam: Wie können Hash-Tabellen so viel besser sein als Bäume, die intuitiv wie die effizienteste Art wirken, Daten zu speichern?
Mir wurde klar, dass die Theorie der Hash-Tabellen mit einer Objektmenge fester Größe arbeitet. Für diese feste Menge erstellt man eine Hash-Funktion und nutzt sie wie einen Vektorindex, um in einem vorab allozierten Vektor zu speichern. Daraus ergibt sich ein Rezept, mit dem Einfügen, Löschen und Nachschlagen nahe an O(1) möglich sind. Verschiedene Baumstrukturen gehen dagegen nicht von einer bestimmten Größe aus.
Das Problem ist, dass man die Größe vorab festlegen muss, und wenn der Vektor fast voll ist, können Vorgänge wie Einfügen langsam werden.
Beim Überfliegen des Artikels wirkt es so, als würde dieses Ergebnis genau diesen langsam werdenden Teil lösen und schnelle Einfügungen auch in fast volle Tabellen ermöglichen.
Interessant und clever, aber vermutlich kein großer praktischer Fortschritt. In der Praxis würde man meiner Meinung nach eher die angenommene Größe erhöhen, statt sich eine clevere Befüllung der Tabelle zu überlegen.
Ich schreibe das, um zu prüfen, ob mein Verständnis stimmt; falls nicht, korrigiert mich gern.
Bei einem Einfügen, das eine Größenänderung auslöst, fällt eine deutlich höhere, zur Tabellengröße lineare Zeit an, aber diese Zeit wird über alle bereits ausgeführten Einfügungen amortisiert.
Wenn man die Tabelle jedes Mal, wenn sie zu voll wird, ausreichend stark vergrößert, passiert das immer seltener, sodass es im Durchschnitt weiterhin konstante Zeit bleibt.
In der funktionalen Welt sind Bäume wahrscheinlich weiterhin besser geeignet.
Ich hatte keine Zeit, das Paper vollständig zu verstehen, aber es behauptet, dass Einfügungen damit konstant schnell sind. Bis 75 % der Gesamtkapazität leuchtet mir das ein; ob es einen anderen Modus gibt, wenn alle Zeilen 75 % erreicht haben, weiß ich nicht.
Es wird auch behauptet, dass Lookups schnell sind, aber ich habe nicht genug gelesen, um zu verstehen, wie das Nachschlagen funktioniert oder warum es schnell ist.
Es gibt viele Situationen, in denen es wirklich gut wäre, wenn eine fast volle Hash-Tabelle trotzdem funktioniert. Während der Programmausführung kann man die Größe nicht immer ändern, und in manchen Umgebungen ist Speicher sehr wichtig.
Trotzdem würde ich gern die Implementierung sehen und selbst damit herumspielen. Ich bin nicht überzeugt, ob es im allgemeinen Fall „den Aufwand wert“ ist.
Die Cache-Effizienz dürfte ebenfalls eher schlecht sein. Das gilt zwar für die meisten Hash-Tabellen, aber der Sonderfall, bei dem man in einer recht vollen Tabelle mit linear probing liest, kann zusammenhängend aus dem Speicher geholt und geprüft werden.
Ob es aus Performance-Sicht wertvoll ist, ist noch nicht klar, aber es ist eine interessante neue Idee, die ich gern vollständig verstehen würde.
Ich verstehe den Teil nicht, in dem es heißt: „In dieser neuen Hash-Tabelle ist die für die schlechtesten Abfragen und Einfügungen benötigte Zeit proportional zu (log x)2 und damit viel schneller als x“, aber zugleich „die Ergebnisse des Teams führen möglicherweise nicht zu unmittelbaren Anwendungen“.
Warum sollten sie nicht zu unmittelbaren Anwendungen führen? Ist damit gemeint, dass man Hash-Implementierungen durch Analysen realer Use Cases besser abstimmen kann als mit einem rein mathematischen Ansatz?
Mitunter müsste der Datensatz unrealistisch groß sein, um einen Geschwindigkeitsgewinn zu sehen.
Dann wird x nicht größer als 4, sodass eine Verbesserung von O(x) auf O((log x)^2) nichts bringt, wenn x so klein ist.
In einigen speziellen Anwendungen mit Speicherbeschränkungen würde man x größer wählen, aber persönlich ist mir so ein Fall nicht begegnet.
Immer wenn sehr hohe Auslastungen nötig waren, etwa über 90 %, reichte Cuckoo Hashing aus; bei 70–80 % oder weniger war linear probing sehr schnell und gut genug.
Das neue Ergebnis hat auch den Nachteil, dass Einfügungen im „guten Fall“ langsamer werden.
Im Paper sehe ich nichts, was die Praxis beeinflussen würde.
Dieses Ergebnis scheint nur wichtig zu sein, wenn die Hash-Tabelle fast voll ist.
Könnte man dann nicht einfach die Tabellengröße um 10 % größer wählen oder, falls Größenänderungen möglich sind, früher resizen?
Wenn die Wahrscheinlichkeit von Hash-Kollisionen zu groß wird, ändern sie selbst ihre Größe.
Wenn die Tabelle zu voll wird, alloziert man einfach doppelt so viel Speicher oder ein festes Vielfaches mehr und kopiert die bestehenden Einträge.
Die meisten Tabellen mit nichtlinearem Probing, zum Beispiel Cuckoo Hashing, leiden darunter, dass RAM überhaupt nicht „zufällig“ ist.
Kennt jemand das GitHub-Repository mit dieser Implementierung?