Simple Minimal Perfect Hashing in Less Space

摘要

A minimal perfect hash function for a set S is an injective mapping from S to {0,..., |S|―1}. Taking as our model of computation a unit-cost RAM with a word length of ω bits, we consider the problem of constructing minimal perfect hash functions with constant evaluation time for arbitrary subsets of U = {0, ...,2~ ω ―1}. Pagh recently described a simple randomized algorithm that, given a set S is contained in U of size n, works in O(n) expected time and computes a minimal perfect hash function for S whose representation, besides a constant number of words, is a table of at most (2 + ∈)n integers in the range {0,..., n ―1}, for arbitrary fixed ∈ > 0. Extending his method, we show how to replace the factor of 2 + ∈ by 1 + ∈.