Walzer, StefanHölldobler, Steffen2022-01-142022-01-142021978-3-88579-775-3https://dl.gi.de/handle/20.500.12116/37921Für Wörterbücher und verwandte Datentypen gibt es Implementierungsansätze, bei denen Hashfunktionen mehrere zufällige Möglichkeiten zur Speicherung jedes Schlüssels vorsehen. Solche Verfahren weisen oft einen scharfen Schwellwert bzgl. erzielbarer Auslastungsfaktoren auf, aus dem sich die Speichereffizienz der Datenstruktur ergibt. Hypergraphen spielen in Schwellwertanalysen – nicht aber in dieser Zusammenfassung – eine zentrale Rolle. Drei Ergebnisse der Arbeit liefern Schwellwerte für Varianten von Cuckoo-Hashtabellen, darunter die Doppel-Hashing-Variante und eine Variante mit nicht-ausgerichteten Blöcken. Drei weitere Ergebnisse untersuchen neue Varianten von Retrieval-Datenstrukturen, aus denen sich unter anderem neue speichereffiziente Alternativen zu Bloom-Filtern ergeben.deText/Conference Paper