Space Upper Bounds for α-Perfect Hashing

In the problem of minimal perfect hashing, we are given a size k subset A of a universe of keys [n] = {1,2, ⋯,n}, for which we wish to construct a hash function h: [n] → [k] such that h(·) maps A to [k] with no collisions, i.e., the restriction of h(·) to A is injective. In this paper, we extend the study of minimal perfect hashing to the approximate setting. For an α ∈ [0,1], we say that a randomized hashing scheme is α-perfect if for any input A of size k, it outputs a hash function which exhibits at most (1 − α)k collisions on A in expectation. One important performance consideration for any hashing scheme is the space required to store the hash functions. For minimal perfect hashing, it is well known that approximately k log(e) bits, or log(e) bits per key, is required to store the hash function. In this paper, we propose schemes for constructing minimal α-perfect hash functions and analyze their space requirements. We begin by presenting a simple base-line scheme which randomizes between perfect hashing and zero-bit random hashing. We then present a more sophisticated hashing scheme based on sampling which significantly improves upon the space requirement of the aforementioned strategy for all values of α.