Minimal perfect hash functions made simple

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Minimal perfect hash functions made simple

Full text

Pdf (274 KB)

Source

Communications of the ACM archive
Volume 23 , Issue 1 (January 1980) table of contents

Pages: 17 - 19

Year of Publication: 1980

ISSN:0001-0782

Author

Richard J. Cichelli

Software Consulting Services, Allentown, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 129, Citation Count: 38

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/358808.358813 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	2	B. A. Sheil, Median split trees: a fast lookup technique for frequently occuring keys, Communications of the ACM, v.21 n.11, p.947-958, Nov. 1978 [doi>10.1145/359642.359653]
	3	Renzo Sprugnoli, Perfect hashing functions: a single probe retrieving method for static sets, Communications of the ACM, v.20 n.11, p.841-850, Nov. 1977 [doi>10.1145/359863.359887]

CITED BY 38

	Jack E. Slingerland , Martin D. Waugh, Technical correspondence: on Cichelli's algorithm for finding minimal perfect hash functions, Communications of the ACM, v.24 n.5, p.322, May 1981
	Thomas J. Sager, A polynomial time generator for minimal perfect hash functions, Communications of the ACM, v.28 n.5, p.523-532, May 1985
	Per-Ake Larson , M. V. Ramakrishna, External perfect hashing, ACM SIGMOD Record, v.14 n.4, p.190-200, May 1985
	C. C. Chang, The study of an ordered minimal perfect hashing scheme, Communications of the ACM, v.27 n.4, p.384-387, April 1984
	Edward A. Fox , Qi Fan Chen , Lenwood S. Heath, A faster algorithm for constructing minimal perfect hash functions, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.266-273, June 21-24, 1992, Copenhagen, Denmark
	Thomas J. Sager, A polynomial time generator for minimal perfect hash functions, Communications of the ACM, v.28 n.5, p.523-532, May 1985
	Peter K. Pearson, Fast hashing of variable-length text strings, Communications of the ACM, v.33 n.6, p.677-680, June 1990
	G. Jaeschke, Reciprocal hashing: a method for generating minimal perfect hashing functions, Communications of the ACM, v.24 n.12, p.829-833, Dec. 1981
	R. Charles Bell , Bryan Floyd, A Monte Carlo study of Cichelli hash-function solvability, Communications of the ACM, v.26 n.11, p.924-925, Nov. 1983
	Sanjiv K. Bhatia , Chaman L. Sabharwal, Near perfect hash table for image databases, Proceedings of the 1996 ACM symposium on Applied Computing, p.442-446, February 17-19, 1996, Philadelphia, Pennsylvania, United States
	Jason Gait, Hash table methods for case statements, Proceedings of the 20th annual Southeast regional conference, p.211-216, April 01-03, 1982, Knoxville, Tennessee
	Edward A. Fox , Lenwood S. Heath , Qi Fan Chen , Amjad M. Daoud, Practical minimal perfect hash functions for large databases, Communications of the ACM, v.35 n.1, p.105-121, Jan. 1992
	Jack E. Slingerland , Martin D. Waugh, Technical correspondence: on Cichelli's algorithm for finding minimal perfect hash functions, Communications of the ACM, v.24 n.5, p.322, May 1981
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	M. V. Ramakrishna , P.-:1V Larson, File organization using composite perfect hashing, ACM Transactions on Database Systems (TODS), v.14 n.2, p.231-263, June 1989
	M. D. Brain , A. L. Tharp, Using Tries to Eliminate Pattern Collisions in Perfect Hashing, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.239-247, April 1994
	E. A. Fox , Q.-F. Chen , L. Heath , S. Datta, A more cost effective algorithm for finding perfect hash functions, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.114-122, February 21-23, 1989, Louisville, Kentucky
	Jun-ichi Aoe, An Efficient Digital Search Algorithm by Using a Double-Array Structure, IEEE Transactions on Software Engineering, v.15 n.9, p.1066-1077, September 1989
	Curtis R. Cook , R. R. Oldehoeft, A letter oriented minimal perfect hashing function, ACM SIGPLAN Notices, v.17 n.9, p.18-27, September 1982
	David Alan Wolverton, A perfect hash function for Ada reserved words, ACM SIGAda Ada Letters, v.IV n.1, p.40-44, July-August 1984
	Jun-ichi Aoe, An Efficient Implementation of Static String Pattern Matching Machines, IEEE Transactions on Software Engineering, v.15 n.8, p.1010-1016, August 1989
	Zhiyu Tian , Shibai Tong , Shiyuan Yang, A new hashing function: statistical behaviour and algorithm, ACM SIGIR Forum, v.27 n.1, p.3-13, Spring 1993
	Ted G. Lewis , Curtis R. Cook, Hashing for Dynamic and Static Internal Tables, Computer, v.21 n.10, p.45-56, October 1988
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Nick Cercone , Max Krause , John Boates, Lexicon design using perfect hash functions, ACM SIGSOC Bulletin, v.13 n.2-3, p.69-78, 1982
	Harri Jäppinen , Matti Ylilammi, Associative model of morphological analysis: an empirical inquiry, Computational Linguistics, v.12 n.4, p.257-272, October-December 1986
	Jacques Savoy, Statistical behavior of fast hashing of variable length test strings, ACM SIGIR Forum, v.24 n.3, p.62-71, Fall 1990
	John A. Trono, Optimal table lookup for reserved words in Ada, ACM SIGAda Ada Letters, v.XXVI n.1, April 2006
	Janne Nieminen , Pekka Kilpeläinen, Efficient implementation of Aho–Corasick pattern matching automata using Unicode, Software—Practice & Experience, v.37 n.6, p.669-690, May 2007
	Wei-Pang Yang , M. W. Du, A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table, Proceedings of the 10th International Conference on Very Large Data Bases, p.245-254, August 27-31, 1984
	Robert W. Sebasta , Mark A. Taylor, Minimal perfect hash functions for reserved word lists, ACM SIGPLAN Notices, v.20 n.12, p.47-53, Dec. 1985
	John A. Trono, An undergraduate project to compute minimal perfect hashing functions, ACM SIGCSE Bulletin, v.24 n.3, p.53-56, Sept. 1992
	Maurizio Panti , Salvatore Valenti, A modulus oriented hash function for the construction of minimal perfect tables, ACM SIGPLAN Notices, v.27 n.11, p.33-38, Nov. 1992
	John A. Trono, A comparison of three strategies for computing letter oriented, minimal perfect hashing functions, ACM SIGPLAN Notices, v.30 n.4, p.29-35, April 1995
	Gary Haggard , Kevin Karplus, Finding minimal perfect hash functions, ACM SIGCSE Bulletin, v.18 n.1, p.191-193, February 1986
	Amjad M. Daoud, Perfect hash functions for large dictionaries, Proceedings of the ACM first workshop on CyberInfrastructure: information management in eScience, November 09-09, 2007, Lisbon, Portugal
	PaiTzu Chang, An efficient hash-based searching for specimens in the museum's exhibit, Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication, January 15-16, 2009, Suwon, Korea
	P. Punitha , D. S. Guru, Symbolic image indexing and retrieval by spatial similarity: An approach based on B-tree, Pattern Recognition, v.41 n.6, p.2068-2085, June, 2008

INDEX TERMS

Keywords:
Pascal, Pascal reserved words, backtracking, dictionary lookup, direct addressing, hash coding, hashing, hashing methods, indentifier-to-address transformations, information retrieval, lexical analysis, perfect hash coding, perfect hashing functions, scatter storage, searching

Collaborative Colleagues:

Richard J. Cichelli: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player