5 października 2021 10:15
[Seminarium ZOK] Guy Even: "An extendable data structure for dynamic stable perfect hashing"
Streszczenie:
A dynamic stable perfect hashing is an injective function
that assigns hashcodes to elements in a dynamically changing set
(i.e., insertions and deletions) such that the hashcode of an element
does not change while the element is continuously in the set. We
present a data structure for dynamic stable perfect hashing in the
extendable setting in which the size of the data structure is not
predefined.
Let $N_t$ denote the maximum cardinality of the dynamic set till time
$t$. Our data structure has the following properties:
Time: all operations (insert, delete, query) require constant time in
the worst case with high probability.
Space: the number of bits per element is $O(\log \log N_t)$.
Hashcode Range: The range of the hashcodes is $[(1+1/\poly(\log N_t)) N_t]$.
This is the first constant time per operation data structure for
extendable dynamic stable perfect hashing whose space is within a
constant factor of the lower bound for the dynamic non-extendable
case. We conclude with an application of our data structure: A
succinct extendable dynamic dictionary with constant time worst case
operations with high probability whose space is smaller than known
dictionaries.