Hashtabellen sind ein Grundwerkzeug zahlloser Algorithmen und Datenstrukturen. Sowohl in der Theorie als auch in der Praxis ermöglichen sie die effiziente Beantwortung von Membership-Anfragen sowie die Assoziation von Schlüsseln zu Werten. Es gibt an sie verschiendene Anforderungen:

• Konstante Laufzeit (mit hoher Wahrscheinlichkeit) für Anfragen, Einfüge- und Löschoperationen
• Cache-Effizienz
• Hohe Lastfaktoren (also wenig Speicher“verschnitt”), insb. auch unter dynamischen Größenveränderungen durch Einfüge- und Löschoperationen
• Referentielle Stabilität (d.h. Zeiger auf Einträge in der Tabelle bleiben auch über Einfüge- und Löschoperationen hinweg gültig)

In [1] werden Verfahren vorgestellt, welche alle oben genannten Anforderungen unter ein Dach bringen soll. In der Arbeit sollen sowohl das (zunächst statische) Iceberg Hashing als auch das zur effizienten Dynamisierung erforderliche Waterfall Addressing implementiert und in einer praktischen Evaluation mit bewährten Hashtabellen auf Performance (Laufzeit, Cache- und Speichereffizienz) verglichen werden.

Bachelor- oder Masterarbeit

• Spaß an algorithmischen Problemstellungen
• gute Kenntnisse in einer speicher/laufzeit-effizienten Programmiersprache (C++, Rust, etc.)
• Erfahrung mit der Programmierung auf Bit-Ebene

[1]: Bender, Conway, Farach-Colton, Kuszmaul & Tagliavini: All-Purpose Hashing, arXiv abs/2109.04548 (2021)

Bei Interesse wenden Sie sich bitte an Patrick Dinklage und Johannes Fischer.