An Improved Algorithm for Generating Minimal Perfect Hash Functions

Author

Thomas J. Sager

Abstract

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 M⁴. We also give a MPHF for the 256 most frequently used words in the English language.

Recommended Citation

Sager, Thomas J., "An Improved Algorithm for Generating Minimal Perfect Hash Functions" (1984). Computer Science Technical Reports. 1.
https://scholarsmine.mst.edu/comsci_techreports/1

Department(s)

Computer Science

Keywords and Phrases

Algorithms; Performance; Languages; Searching; Hashing; Minimal Perfect Hashing

Report Number

CSc-84-1

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1984 University of Missouri--Rolla, All rights reserved.

Publication Date

1984