Fast and Reliable Parallel Hashing

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