Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
An Improved Algorithm For Generating Minimal Perfect Hash Functions, Thomas J. Sager
An Improved Algorithm For Generating Minimal Perfect Hash Functions, Thomas J. Sager
Computer Science Technical Reports
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.