Quasi-perfect Hashing

The idea of quasi-perfect hashing is introduced and applied to solve the static dictionary problem. Given a universe U and a set S of n distinct keys belonging to U, we propose a quasi-perfect hash function which allows one to find a key from S, stored in the hash table of size m, m ≤ n, in O(1) time. While looking up a key at most two probes in the hash table are made. Our main motivation is to minimize the memory requirement for representing the hashing scheme, retaining a high probability of finding quasi-perfect hash functions for arbitrary sets S. If we compare the method of quasi-perfect hashing to Fredman, Komlós and Szemerédi's two-level hashing for the bounded universe U, we find that it is superior with regard to both space and speed.