Studie eines Undergraduates belegt schnellere Suche in Hash-Tabellen

Einführung

• Im Herbst 2021 stieß der Undergraduate Andrew Krapivin von der Rutgers University auf eine Arbeit, die sein Leben verändern sollte.
• In dieser Arbeit ging es um „kleine Zeiger“, die auf Informationen im Computerspeicher verweisen.
• Krapivin entwickelte eine Methode, Zeiger zu verkleinern und so den Speicherverbrauch zu senken.

Entdeckung einer neuen Hash-Tabelle

• Krapivin führte Experimente mit Hash-Tabellen durch, einer gängigen Methode zur Speicherung von Daten.
• Während der Experimente erfand Krapivin eine neue Art von Hash-Tabelle, die schneller arbeitet als bisherige Ansätze.
• Diese Entdeckung führte zu einem Ergebnis, das eine 40 Jahre alte Vermutung der Datenwissenschaft widerlegt.

Die Bedeutung von Hash-Tabellen

• Hash-Tabellen gehören zu den ältesten Datenstrukturen der Informatik und ermöglichen eine effiziente Datenspeicherung.
• Hash-Tabellen sind dafür ausgelegt, drei Funktionen auszuführen: Elemente suchen, löschen und einfügen.

Yaos Vermutung und ihre Widerlegung

• 1985 formulierte der Informatiker Andrew Yao eine Vermutung darüber, wie sich Elemente im schlechtesten Fall in Hash-Tabellen mit bestimmten Eigenschaften finden lassen.
• Krapivins neue Hash-Tabelle widerlegt Yaos Vermutung und beweist, dass die für Abfragen und Einfügungen im schlechtesten Fall benötigte Zeit proportional zu (log x)² ist.

Neue Erkenntnis zur durchschnittlichen Abfragezeit

• Krapivin und sein Team zeigten, dass bei nicht-gierigen Hash-Tabellen die durchschnittliche Abfragezeit nicht von x abhängt.
• Das bedeutet, dass sich eine konstante durchschnittliche Abfragezeit unabhängig vom Füllgrad der Hash-Tabelle erreichen lässt.

Fazit

• Diese Forschung vertieft das Verständnis von Hash-Tabellen und könnte zu praktischen Anwendungen führen.
• Dieses Verständnis von Datenstrukturen kann eine Grundlage für künftige praktische Verbesserungen sein.

[GN⁺]

Hacker-News-Kommentare

• Krapivin gelang ein Durchbruch, ohne Yaos Vermutung zu kennen

  • Der Entwickler von Balatro schuf ein preisgekröntes Deckbuilder-Spiel, ohne bestehende Deckbuilder zu kennen
  • Der beste Weg, ein Problem anzugehen, könnte sein, frühere ähnliche Versuche nicht zu kennen oder zu ignorieren
  • Die heutige Welt ist zu stark vernetzt, sodass man leicht in frühere Denkmuster gerät
  • Das Internet ist großartig, neigt aber dazu, die Welt des Denkens zu homogenisieren

• Tolles Ergebnis, aber es sollte wohl eher eine Vermutung der Informatik genannt werden

• Ich frage mich, ob jemand ein GitHub-Repository mit dieser Implementierung kennt

• Cool, aber der Stil dieser "Promi-Inszenierung" im Artikel ist etwas unangenehm

  • Ich frage mich, ob man wirklich mehrere Fotos eines jungen Menschen in verschiedenen Posen auf dem Campus brauchte
  • Es wirkt, als brauche man eine Version von La La Land, um die Überlebenden von Computer-Erfolgen zu verherrlichen und so mehr Beteiligung anzulocken

• Bei der neuen Hashtabelle ist die im Worst Case für Abfragen und Einfügungen benötigte Zeit proportional zu (log x)²

  • Das Ergebnis des Teams führt möglicherweise nicht sofort zu praktischen Anwendungen
  • Ich verstehe nicht, warum es nicht sofort zu praktischen Anwendungen führen sollte
  • Ich frage mich, ob die Analyse realer Anwendungsfälle Hashtabellen-Implementierungen besser abstimmen kann als ein rein mathematischer Ansatz

• Diesen Artikel zu lesen ist wie eine Erklärung des Monty-Hall-Problems zu lesen

  • Die Schlussfolgerung scheint dem gesunden Menschenverstand zu widersprechen, ist aber beweisbar
  • Dass man unabhängig vom Füllgrad der Hashtabelle eine konstante durchschnittliche Abfragezeit erreichen kann, hatten selbst die Autoren nicht erwartet

• Ein guter aktueller Test

  • Mal sehen, ob Deep Research dieses Ergebnis hervorbringen kann, ohne es zu kopieren
  • GPT-4, Gemini 2 und Claude hatten kein Glück
  • Von Menschen geführte Informatik ist weiterhin sicher

• Ich frage mich, ob jemand eine einfache Implementierung von 'Tiny pointers' hat

  • Für mich stehen Code/Pseudocode vor dem Beweis

• Wie der Bösewicht in <i>Scooby Doo</i> immer sagte:

  • <i>"Und wenn da nicht diese nervigen Kinder gewesen wären, hätte ich es geschafft!"</i>

• Beim groben Überfliegen der Arbeit scheint der wesentliche Unterschied zu sein, dass ihr Einfügealgorithmus für Hashtabellen weiter sucht, statt gierig den ersten leeren Slot zu füllen

  • Er kombiniert das mit einer beweisbar guten Suchreihenfolge, um auch bei sehr voller Tabelle leere Slots effizient zu finden
  • Wenn die Tabelle weniger voll ist, werden Einfügungen langsamer, aber dafür lässt sich das Worst-Case-Szenario vermeiden, in dem der letzte verbliebene leere Slot nicht gefunden wird

• Ein interessantes theoretisches Ergebnis, aber in der Praxis scheint der aktuelle 'Trick', eine größere Tabelle als nötig zu reservieren, die bessere Lösung zu sein

  • Zum Beispiel lässt Rusts hashbrown 1/8 der Tabelle (12,5 %) leer, verbraucht also etwas mehr Speicher, dafür sind Einfügungen/Lookups sehr schnell