A minimal perfect hash function (MPHF) is a function from a set of M objects to the first M non-negative integers. MPHF's 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. In this paper we improve on an earlier result and present an algorithm for generating MPHF's with an expected time complexity proportional to M4. We also give a MPHF for the 256 most frequently used words in the English language.
Sager, Thomas J., "An Improved Algorithm for Generating Minimal Perfect Hash Functions" (1984). Computer Science Technical Reports. 1.
Keywords and Phrases
Algorithms; Performance; Languages; Searching; Hashing; Minimal Perfect Hashing
© 1984 University of Missouri--Rolla, All rights reserved.