Reciprocal hashing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Reciprocal hashing: a method for generating minimal perfect hashing functions

Full text

Pdf (449 KB)

Source

Communications of the ACM archive
Volume 24 , Issue 12 (December 1981) table of contents

Pages: 829 - 833

Year of Publication: 1981

ISSN:0001-0782

Author

G. Jaeschke

Heidelberg Scientific Center, Niederlassung Heidelberg, Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 33, Citation Count: 24

Additional Information:

abstract references cited by index terms

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/358800.358806 What is a DOI?

ABSTRACT

A method is presented for building minimal perfect hash functions, i.e., functions which allow single probe retrieval from minimally sized tables of identifier sets. A proof of existence for minimal perfect hash functions of a special type (reciprocal type) is given. Two algorithms for determining hash functions of reciprocal type are presented and their practical limitations are discussed. Further, some application results are given and compared with those of earlier approaches for perfect hashing.

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	Richard J. Cichelli, Minimal perfect hash functions made simple, Communications of the ACM, v.23 n.1, p.17-19, Jan. 1980 [doi>10.1145/358808.358813]
	2	Marek Greniewski , Wladyslaw Turski, The external language KLIPA for the URAL-2 digital computer, Communications of the ACM, v.6 n.6, p.321-324, June 1963 [doi>10.1145/366604.366654]
	3	Jaeschke, G. Minimal perfect hashing. Tech. Rept. TR 80.02.003, IBM Heidelberg Scientific Center, Niederlassung Heidelberg, Germany.
	4	Jaeschke, G., Osterburg, G. On Cichelli's minimal perfect hash functions method. Comm. ACM, 23, 12 (Dec. 1980), 728-729.
	5	Knott, G.D. Hashing functions. Computer J., 18 (Aug. 1975), 265-278.
	6	Leveque, W. J. Topics in Number Theory. Addison-Wesley, Reading, Mass., 1956.
	7	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 24

	Takao Miura , Wataru Matsumoto , Isamu Shioya , Yukio Wada, Extensible perfect hashing, Proceedings of the ninth international conference on Information and knowledge management, p.446-452, November 06-11, 2000, McLean, Virginia, United States
	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
	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
	CORPORATE Tech Correspondence, Technical Correspondence, Communications of the ACM, v.28 n.10, p.1086-1087, Oct. 1985
	CORPORATE Tech Correspondence, Technical correspondence, Communications of the ACM, v.29 n.10, p.1001-1005, Oct. 1986
	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984
	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
	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
	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
	Christos Faloutsos , Stavros Christodoulakis, Optimal signature extraction and information loss, ACM Transactions on Database Systems (TODS), v.12 n.3, p.395-428, Sept. 1987
	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
	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
	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
	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
	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
	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
	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