Konferenzbeitrag
Zufällige Hypergraphen für Hashing-basierte Datenstrukturen
Vorschaubild nicht verfügbar
Volltext URI
Dokumententyp
Text/Conference Paper
Zusatzinformation
Datum
2021
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik e.V.
Zusammenfassung
Fü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.