Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Hash, Displace, and Compress
verfasst von : Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger
Erschienen in: Algorithms - ESA 2009
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A hash function
h
, i.e., a function from the set
U
of all keys to the range range [
m
] = {0,...,
m
− 1} is called a perfect hash function (PHF) for a subset
S
⊆
U
of size
n
≤
m
if
h
is 1-1 on
S
. The important performance parameters of a PHF are representation size, evaluation time and construction time. In this paper, we present an algorithm that permits to obtain PHFs with expected representation size very close to optimal while retaining
O
(
n
) expected construction time and
O
(1) evaluation time in the worst case. For example in the case
m
= 1.23
n
we obtain a PHF that uses space 1.4 bits per key, and for
m
= 1.01
n
we obtain space 1.98 bits per key, which was not achievable with previously known methods. Our algorithm is inspired by several known algorithms; the main new feature is that we combine a modification of Pagh’s “hash-and-displace” approach with data compression on a sequence of hash function indices. Our algorithm can also be used for
k
-perfect hashing, where at most
k
keys may be mapped to the same value.