Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions

Authors

  • Rasmus Pagh

DOI:

https://doi.org/10.7146/brics.v6i13.20070

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.

Downloads

Published

1999-01-13

How to Cite

Pagh, R. (1999). Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions. BRICS Report Series, 6(13). https://doi.org/10.7146/brics.v6i13.20070