|
Hash and Displace: Efficient Evaluation of Minimal Perfect Hash
Functions
Rasmus Pagh May 1999 |
Abstract:A new way of constructing (minimal) perfect hash functions is described. The technique considerably reduces the overhead associated with resolving buckets in two-level hashing schemes. Evaluating a hash function requires just one multiplication and a few additions apart from primitive bit operations. The number of accesses to memory is two, one of which is to a fixed location. This improves the probe performance of previous minimal perfect hashing schemes, and is shown to be optimal. The hash function description (``program'') for a set of size n occupies O(n) words, and can be constructed in expected O(n) time Available as PostScript, PDF. |