Item

Abstract

A perfect hash function for a (multi)set $X$ of
$n$ integers is an injective function $h:X\to\{1,\ldots,s\}$,
where $s=O(n)$, that can be stored in $O(n)$ space
and evaluated in constant time by a single processor.
We show that a perfect hash function for a given
multiset of $n$ integers can be constructed
optimally in $O(\log^* n)$ time using
$O(n/\log^* n)$ processors.
Our algorithm is faster than all previously published
methods.
More significantly, it is highly
reliable:
Whereas analyses of previous fast parallel
hashing schemes provided bounds on the expected
resource requirements only, our algorithm is
guaranteed to stay within the bounds given
with overwhelming probability.