Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions
DOI:
https://doi.org/10.7146/brics.v6i13.20070Abstract
A new way of constructing (minimal) perfect hash functions is described. Thetechnique 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
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.