Linear time algorithm for finding minimal perfect hash functions

A new algorithm for finding minimal perfect hash functions (MPHF) is proposed. The algorithm given three pseudorandom functions h₀, h₁ and h₂, searches for a function g such that F(w) = (h₀(w) + g(h₁(w)) + g(h₂(w))) mod m is a MPHF, where m is a number of input words. The algorithm involves generation of random bipartite graphs and runs in linear time. The hash function generated is represented by using 2m + O(1) memory words of log m bits each. The empirical observations show that the algorithm runs very fast in practice.