Practical perfect hashing in nearly optimal space

Abstract: A hash function is a mapping from a key universe U to a range of integers, i.e., , where m is the range''s size. A perfect hash function for some set is a hash function that is one-to-one on S, where . A minimal perfect hash function for some set is a perfect hash function with a range of minimum size, i.e., . 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 to bits, and for it ranges from to bits. This is within a small constant factor from the theoretical lower bounds of bits for m=n and bits for . 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). [Copyright &y& Elsevier]