Platzeffiziente Hashverfahren mit garantierter konstanter Zugriffszeit

We present a new algorithm for a minimal perfect hash function (MPHF) and a new dynamic cache friendly dictionary. We describe the procedures and analyse them with respect to space and time. For our analysis we assume full randomness of hash functions which are used by the algorithms. Finally we give experimental results and discuss them. We show that it is possible to construct a minimal perfect hash function which stores n keys and consumes 0.93n words. It takes O(n) expected time to build such a MPHF. To evaluate our MPHF only 2 memory cells have to be read and only 2 hash functions have to be evaluated. Our dynamic dictionary consumes (1+epsilon)n space for an arbitrary epsilon > 0. For a \lkp{} operation only 2 hash functions have to be evaluated and 2d memory cells have to be inspected, which are located in 2 contiguous blocks for each d >= 1+3.26 ln(1/epsilon). Further we proof that for each d >= 90.1 ln(epsilon) the expected time for inserting a new key is constant. Finally we show how to adapt our dictionary to use strings as keys in a cache friendly manner.

Wir stellen ein neues Verfahren zur Konstruktion einer minimalen perfekten Hashfunktion (MPHF) und ein neues cachefreundliches dynamisches Wörterbuch vor, beschreiben die neuen Verfahren algorithmisch und analysieren sie hinsichtlich Platzbedarf und Laufzeit. Für die Analyse nehmen wir an, dass die in den Verfahren benutzten Hashfunktionen volle Unabhängigkeit gewährleisten. Schließlich werden wir jeweils experimentelle Resultate angeben und interpretieren. Wir zeigen, dass man eine minimale perfekte Hashfunktion für n Schlüssel mit einem Platzbedarf von 0.93n Wörtern in erwarteter Zeit O(n) realisieren kann. Zur Auswertung der MPHF werden 2 Hashfunktionen berechnet und zwei Speicherzugriffe durchgeführt. Unser dynamisches Wörterbuch benötigt (1+epsilon)n Platz für ein beliebiges epsilon > 0. Bei der Suche müssen 2 Hashfunktionen ausgewertet und 2d Speicherzellen inspiziert werden, die in zwei zusammenhängenden Speicherbereichen liegen, wobei d >= 1+3.26 ln(1/epsilon). Wir können zeigen, dass für d >= 90.1 ln(1/epsilon) die erwartete Einfügezeit für einen neuen Schlüssel konstant ist. Am Ende werden wir zeigen, wie man dynamisches Hashing mit Zeichenketten cachefreundlich realisieren kann.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.