Open AccessHash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions
Author(s) -
Rasmus Pagh
Publication year - 1999
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v6i13.20070
Subject(s) - hash function , perfect hash function , dynamic perfect hashing , double hashing , computer science , overhead (engineering) , set (abstract data type) , multiplication (music) , function (biology) , linear hashing , hash chain , hash table , mathematics , arithmetic , discrete mathematics , theoretical computer science , combinatorics , computer security , evolutionary biology , biology , programming language , operating system
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.