The effect of table expansion on the program complexity of perfect hash functions

It has been shown by various researchers that designing a perfect hashing function for a fixed set ofn elements requires (n) bits in the worst case. A possible relaxation of this scheme is to partition the set into pages, and design a hash function which maps keys to page addresses, requiring subsequent binary search of the page. We have shown elsewhere that (nk/2 ^k+1)(1 +o(1)) bits are necessary and sufficient to describe such a hash function where the pages are of size 2 ^k . In this paper we examine the additional scheme of expanding the address space of the table, which does substantially improve the hash function complexity of perfect hashing, and show that in contrast, it does not reduce the hash function complexity of the paging scheme.Research supported by NSF Grant CCR-9017125 and by a grant from Texas Instruments.