A perfect hash function, PHF, is an injection, F, from a set, W, of M objects into the set consisting of the first N non-negative integers where N>=M. If N=M then F is a minimal perfect hash function, MPHF. PHFs are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a natural language.
The mincycle algorithm for finding PHFs executes with an expected time complexity proportional to M4 and has been used successfully on sets of cardinality up to 256. The mincycle algorithm first chooses three pseudo-random functions h0,h1 and h2, then chooses an appropriate ordering of W, and finally performs an exhaustive search for a function, g, which makes F(w) = (h0 (w) + g∙h1 (w) + g∙h2 (w)) mod N a PHF. The chosen ordering is used to reduce the time necessary to perform the exhaustive search.
Sager, Thomas J., "A New Method for Generating Minimal Perfect Hash Functions" (1984). Computer Science Technical Reports. 5.
© 1984 University of Missouri--Rolla, All rights reserved.