Efficient Minimal Perfect Hashing in Nearly Minimal Space

摘要

We consider the following problem: Given a subset S of size n of a universe {0,…,u－1} construct a minimal perfect hash function for S, i.e., a bijection h from S to {0,…,n－1}. The parameters of interest are the space needed to store h, its evaluation time, and the time required to compute h from S. The number of bits needed for the representation of h, ignoring the other parameters, has been thoroughly studied and is known to be n log e +log log u ± O（log n）, where “log” denotes the binary logarithm. A construction by Schmidt and Siegel uses O(n+log log u) bits and offers constant evaluation time, but the time to find h is not discussed. We present a simple randomized scheme that uses n log e + log log u + o(n+ log log u) bits and has constant evaluation time and O(n + log log u) expected construction time.