Home → Magazine Archive → January 1980 (Vol. 23, No. 1) → Minimal perfect hash functions made simple → Abstract

Minimal perfect hash functions made simple

By Richard J. Cichelli

Communications of the ACM, Vol. 23 No. 1, Pages 17-19
10.1145/358808.358813


Save PDF
A method is presented for computing machine independent, minimal perfect hash functions of the form: hash value ← key length + the associated value of the key's first character + the associated value of the key's last character. Such functions allow single probe retrieval from minimally sized tables of identifier lists. Application areas include table lookup for reserved words in compilers and filtering high frequency words in natural language processing. Functions for Pascal's reserved words, Pascal's predefined identifiers, frequently occurring English words, and month abbreviations are presented as examples.

The full text of this article is premium content

0 Comments

No entries found