A LINEAR-TIME ALGORITHM FOR FINDING MINIMAL PERFECT HASH FUNCTIONS

A new algorithm for finding minimal perfect hash functions (MPHF) is p roposed. The algorithm given three pseudorandom functions h0, h1 and h 2, searches for a function g such that F(w) = (h0(w) + g(h1(w)) + g(h2 (w))) mod m is a MPHF, where m is a number of input words. The algorit hm involves generation of random bipartite graphs and runs in linear t ime. The hash function generated is represented by using 2m + O(1) mem ory words of log m bits each. The empirical observations show that the algorithm runs very fast in practice.