Practical perfect hashing in nearly optimal space ?
A hash function is a mapping from a key universe U  to a range of integers, i.e., h:U?{0,1,,m?1} h : U ? { 0,1 ,  , m ? 1 } , where m is the range's size. A perfect hash function  for some set S?U S ? U is a hash function that is one-to-one on S , where m?|S| m ? | S | . A minimal perfect hash function  for some set S?U S ? U is a perfect hash function with a range of minimum size, i.e., m=|S| m = | S | . This paper presents a construction for (minimal) perfect hash functions that combines theoretical analysis, practical performance, expected linear construction time and nearly optimal space consumption for the data structure. For n keys and m=n  the space consumption ranges from 2.62n+o(n) 2.62 n + o ( n ) to 3.3n+o(n) 3.3 n + o ( n ) bits, and for m=1.23n m = 1.23 n it ranges from 1.95n+o(n) 1.95 n + o ( n ) to 2.7n+o(n) 2.7 n + o ( n ) bits. This is within a small constant factor from the theoretical lower bounds of 1.44n 1.44 n bits for m=n  and 0.89n 0.89 n bits for m=1.23n m = 1.23 n . We combine several theoretical results into a practical solution that has turned perfect hashing into a very compact data structure to solve the membership problem when the key set S is static and known in advance. By taking into account the memory hierarchy we can construct (minimal) perfect hash functions for over a billion keys in 46min using a commodity PC. An open source implementation of the algorithms is available at http://cmph.sf.net under the GNU Lesser General Public License (LGPL).
perfect hash functions randomized algorithms random graphs large key sets