The quadratic quotient method

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The quadratic quotient method: a hash code eliminating secondary clustering

Full text

Pdf (260 KB)

Source

Communications of the ACM archive
Volume 13 , Issue 2 (February 1970) table of contents

Pages: 107 - 109

Year of Publication: 1970

ISSN:0001-0782

Author

James R. Bell

Digital Equipment Corp. Maynard, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 29, Citation Count: 24

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

ABSTRACT

Secondary clustering as a cause of hash code inefficiency is discussed, and a new hashing method based on its eliminiation is presented. Comparisons with previous methods are made both analytically and empirically.

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	PRESSER, L. The structure, specification, and evaluation of translators and translator writing systems. Rep. 68-51, U. of California, Los Angeles, Calif., Oct. 1968.
	2	Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968 [doi>10.1145/362851.362882]
	3	W. D. Maurer, Programming Technique: An improved hash code for scatter storage, Communications of the ACM, v.11 n.1, p.35-38, Jan. 1968 [doi>10.1145/362851.362880]

CITED BY 24

	Seiichi Nishihara , Katsuo Ikeda, Reducing the retrieval time of hashing method by using predictors, Communications of the ACM, v.26 n.12, p.1082-1088, Dec. 1983
	Richard P. Brent, Reducing the retrieval time of scatter storage techniques, Communications of the ACM, v.16 n.2, p.105-109, Feb. 1973
	R. A. Wagner, Algorithm 444: an algorithm for extracting phrases in a space-optimal fashion, Communications of the ACM, v.16 n.3, p.183-185, March 1973
	Robert A. Wagner, Common phrases and minimum-space text storage, Communications of the ACM, v.16 n.3, p.148-152, March 1973
	V. Y. Lum , P. S. T. Yuen , M. Dodd, Key-to-address transform techniques: a fundamental performance study on large existing formatted files, Communications of the ACM, v.14 n.4, p.228-239, April 1971
	W. D. Maurer , T. G. Lewis, Hash Table Methods, ACM Computing Surveys (CSUR), v.7 n.1, p.5-19, March 1975
	Salvatore T. March , Dennis G. Severance , Michael Wilens, Frame memory: a storage architecture to support rapid design and implementation of efficient databases, ACM Transactions on Database Systems (TODS), v.6 n.3, p.441-463, Sept. 1981
	Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974
	Thomas C. Irby, Minimizing the retrieval time of scatter storage techniques, Proceedings of the 1978 annual conference, p.834-839, January 1978
	Vladimir Batagelj, The quadratic hash method when the table size is not a prime number, Communications of the ACM, v.18 n.4, p.216-217, April 1975
	Constantine Halatsis , George Philokyprou, Pseudochaining in hash tables, Communications of the ACM, v.21 n.7, p.554-557, July 1978
	Fabrizio Luccio, Weighted increment linear search for scatter tables, Communications of the ACM, v.15 n.12, p.1045-1047, Dec. 1972
	Carter Bays, The reallocation of hash-coded tables, Communications of the ACM, v.16 n.1, p.11-14, Jan. 1973
	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
	Gordon Lyon, Packed scatter tables, Communications of the ACM, v.21 n.10, p.857-865, Oct. 1978
	Stanley T. Schuyler , Jonathan A. Soule , Patrick F. Turchetta , Malcolm H. Gotterer, An image matrix for accessing files, Proceedings of the ACM annual conference, August 01-01, 1972, Boston, Massachusetts, United States
	A. Frank Ackerman, Quadratic search for hash tables of sizes P n, Communications of the ACM, v.17 n.3, p.164, March 1974
	Leslie Lamport, Comment on Bell's quadratic quotient method for hash coded searching, Communications of the ACM, v.13 n.9, p.573-574, Sept. 1970
	James R. Bell , Charles H. Kaman, The linear quotient hash code, Communications of the ACM, v.13 n.11, p.675-676, Nov 1970
	Philip Clapson, Improving the access time for random access files, Communications of the ACM, v.20 n.3, p.127-135, March 1977
	W. A. Wulf , D. B. Russell , A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, v.14 n.12, p.780-790, Dec. 1971
	J. Gerry Purdy, A graduate course in database management, ACM SIGMOD Record, v.7 n.1, p.10-15, 1975
	Mathew N. Matelan, MPACT: microprocessor application to control-firmware translator, ACM SIGDA Newsletter, v.5 n.1, p.13-41, March 1975
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990

INDEX TERMS

Keywords:
calculated address, clustering, collisions, hash code, hashing, keys, scatter storage, search, symbol table, table look-up

Collaborative Colleagues:

James R. Bell: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player