PHast – P erfect H ashing made f ast

Perfect hash functions give unique “names” to arbitrary keys requiring only a few bits per key. This is an essential building block in applications like static hash tables, databases, or bioinformatics. This paper introduces the PHast approach that combines the fastest available queries, very fast construction, and good space consumption (below 2 bits per key). PHast improves bucket-placement which first hashes each key \(k\) to a bucket, and then looks for the bucket seed \(s\) such that a placement function maps pairs \((s,\, k)\) in a collision-free way. PHast can use smallrange hash functions with linear mapping, fixed-width encoding of seeds, and parallel construction. This is achieved using small overlapping slices of allowed values and bumping to handle unsuccessful seed assignment. A variant we called PHast+ uses additive placement, which enables bit-parallel seed searching, speeding up the construction by an order of magnitude.