A New Method for Generating Minimal Perfect Hash Functions

Author

Thomas J. Sager

Abstract

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 M⁴ and has been used successfully on sets of cardinality up to 256. The mincycle algorithm first chooses three pseudo-random functions h₀,h₁ and h₂, then chooses an appropriate ordering of W, and finally performs an exhaustive search for a function, g, which makes F(w) = (h₀ (w) + g∙h₁ (w) + g∙h₂ (w)) mod N a PHF. The chosen ordering is used to reduce the time necessary to perform the exhaustive search.

Recommended Citation

Sager, Thomas J., "A New Method for Generating Minimal Perfect Hash Functions" (1984). Computer Science Technical Reports. 5.
https://scholarsmine.mst.edu/comsci_techreports/5

Department(s)

Computer Science

Report Number

CSc-84-15

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