Minimal perfect hash functions made simple
- 1 January 1980
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 23 (1) , 17-19
- https://doi.org/10.1145/358808.358813
Abstract
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.Keywords
This publication has 2 references indexed in Scilit:
- Median split treesCommunications of the ACM, 1978
- Perfect hashing functionsCommunications of the ACM, 1977