Hash Table Methods

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Hash Table Methods

Full text

Pdf (1.23 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 7 , Issue 1 (March 1975) table of contents

Pages: 5 - 19

Year of Publication: 1975

ISSN:0360-0300

Authors

W. D. Maurer	Department of Electrical Engineering and Computer Science, George Washington University, Washington, D. C.
T. G. Lewis	Computer Science Department, University of Southwestern Louisiana, Lafayette, Louisiana

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 134, Citation Count: 20

Additional Information:

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

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	A. Frank Ackerman, Quadratic search for hash tables of sizes P n, Communications of the ACM, v.17 n.3, p.164, March 1974 [doi>10.1145/360860.360907]
	2	Carter Bays, The reallocation of hash-coded tables, Communications of the ACM, v.16 n.1, p.11-14, Jan. 1973 [doi>10.1145/361932.361936]
	3	James R. Bell, The quadratic quotient method: a hash code eliminating secondary clustering, Communications of the ACM, v.13 n.2, p.107-109, Feb 1970 [doi>10.1145/362007.362040]
	4	James R. Bell , Charles H. Kaman, The linear quotient hash code, Communications of the ACM, v.13 n.11, p.675-676, Nov 1970 [doi>10.1145/362790.362797]
	5	Richard P. Brent, Reducing the retrieval time of scatter storage techniques, Communications of the ACM, v.16 n.2, p.105-109, Feb. 1973 [doi>10.1145/361952.361964]
	6	BUCHtIOLZ, W. "File organization and addressing," IBM Systems J. 2 (June 1963), pp. 86-111.
	7	A. Colin Day, Full table quadratic searching for scatter storage, Communications of the ACM, v.13 n.8, p.481-482, Aug. 1970 [doi>10.1145/362705.362709]
	8	DIPPEL, G.; AND HOUSE, W.C. Information systems, Scott, Foresman & Co, Glenview, Ill, 1969.
	9	DUMEY, A.I. "Indexing for rapid randomaccess memory systems," Computers and Automatwn 5, 12 (Dec. 1956), pp. 6-9
	10	GHOSH, S. P.; AND LUM, V Y. "An analysis of collisions when hashing by divmlon," Tech. Report RJ-1218, IBM, May 1973.
	11	HANAN, M.; AND PALERMO, F.P. "An application of coding theory to a file address problem," IBM j. Res. & Development 7, 2 (April 1963), pp. 127-129.
	12	HELLERMAN, H. D~gital computer system principles, McGraw-Hill, New York, 1967.
	13	L. R. Johnson, An indirect chaining method for addressing on secondary keys, Communications of the ACM, v.4 n.5, p.218-222, May 1961 [doi>10.1145/366532.366540]
	14	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
	15	KNUTH, D. E. "Computer scmnce and its relation to mathematics," Amer. Math. Monthly 81, 4 (April 1974), pp 323-343.
	16	LIN, A.D. "Key addressing of random access memories by radix transformation," Proc 1963 Spr~ng Jo~n~ Computer Conf. AFIPS Vol. 23, Spartan Books, Baltimore, 1963, pp. 355-366.
	17	Fabrizio Luccio, Weighted increment linear search for scatter tables, Communications of the ACM, v.15 n.12, p.1045-1047, Dec. 1972 [doi>10.1145/361598.361617]
	18	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 [doi>10.1145/362575.362578]
	19	V. Y. Lum , P. S. T. Yuen, Additional results on key-to-address transform techniques: a fundamental performance study on large existing formatted files, Communications of the ACM, v.15 n.11, p.996-997, Nov. 1972 [doi>10.1145/355606.361893]
	20	V. Y. Lum, General performance analysis of key-to-address transformation methods using an abstract file concept, Communications of the ACM, v.16 n.10, p.603-612, Oct. 1973 [doi>10.1145/362375.362385]
	21	W. D. Maurer, An improved hash code for scatter storage, Communications of the ACM, v.26 n.1, p.36-38, Jan. 1983 [doi>10.1145/357980.357995]
	22	MAVREa, W D. Programming, Holden-Day, San Francisco, Cahf., 1968.
	23	M. D. Mc Ilroy, A variant method of file searching, Communications of the ACM, v.6 n.3, p.101, March 1963 [doi>10.1145/366274.366304]
	24	Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968 [doi>10.1145/362851.362882]
	25	J. Nievergelt, Binary Search Trees and File Organization, ACM Computing Surveys (CSUR), v.6 n.3, p.195-207, Sept. 1974 [doi>10.1145/356631.356634]
	26	Charles A. Olson, Random access file organization for indirectly addressed records, Proceedings of the 1969 24th national conference, p.539-549, August 26-28, 1969 [doi>10.1145/800195.805959]
	27	PETERSON, W.W. "Addressing for randomaccess storage," IBM J. Res. & Development 1, 2 (April 1957), pp. 130-146.
	28	C. E. Price, Table Lookup Techniques, ACM Computing Surveys (CSUR), v.3 n.2, p.49-64, June 1971 [doi>10.1145/356586.356587]
	29	Charles E. Radke, The use of quadratic residue research, Communications of the ACM, v.13 n.2, p.103-105, Feb 1970 [doi>10.1145/362007.362036]
	30	SCHAY, G.; AND RAVER, N. "A method for key-to-address transformation," IBM J. Res. & Development 7,2 (April 1963), pp 121- 126.
	31	G. Schay, Jr. , W. G. Spruth, Analysis of a file addressing method, Communications of the ACM, v.5 n.8, p.459-462, Aug. 1962 [doi>10.1145/368637.368827]
	32	Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974 [doi>10.1145/356631.356633]
	33	M. Tainiter, Addressing for Random-Access Storage with Multiple Bucket Capacities, Journal of the ACM (JACM), v.10 n.3, p.307-315, July 1963 [doi>10.1145/321172.321178]
	34	J. D. Ullman, A Note on the Efficiency of Hashing Functions, Journal of the ACM (JACM), v.19 n.3, p.569-575, July 1972 [doi>10.1145/321707.321722]
	35	VAN DER POOL, J. A. "Optimum storage allocation for initial loading of a file," IBM J. Res. & Development 16, 6 (Nov. 1972), pp. 579-586.
	36	VAN DER POOL, J. A. "Optimum storage allocation for a file in steady state," IBM J. Res. & Development 17, 1 (Jan. 1973), pp. 27-38.
	37	W~BB, D.A. "The development and application of an evaluation model for hash coding systems," PhD Thesis, Syracuse Univ., Syracuse, N. Y., August 1972.
	38	Peter. Wegner, Programming Languages, Information Structures, and Machine Organization., McGraw Hill Text, 1968

CITED BY 20

	J. Ian Munro , Pedro Celis, Techniques for collision resolution in hash tables with open addressing, Proceedings of 1986 ACM Fall joint computer conference, p.601-610, November 1986, Dallas, Texas, United States
	Anil K. Garg , C. C. Gotlieb, Order-preserving key transformations, ACM Transactions on Database Systems (TODS), v.11 n.2, p.213-234, June 1986
	Denis Samson , Yves Reynaud, Storage management in APL machines, ACM SIGAPL APL Quote Quad, v.10 n.2, December 1979
	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
	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979
	Byung Suk Lee , Gio Wiederhold, Efficiently instantiating view-objects from remote relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.3, p.289-323, July 1994
	M. Negri , G. Pelagatti, Distributive join: a new algorithm for joining relations, ACM Transactions on Database Systems (TODS), v.16 n.4, p.655-669, Dec. 1991
	T. Raita , J. Teuhola, Predictive test compression by hashing, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.223-233, June 03-05, 1987, New Orleans, Louisiana, United States
	Kuo-Chung Tai, On the implementation of parsing tables, ACM SIGPLAN Notices, v.14 n.1, p.100-101, January 1979
	Emil Jovanov , Veljko Milutinovic , Ali R. Hurson, Acceleration of Nonnumeric Operations Using Hardware Support for the Ordered Table Hashing Algorithms, IEEE Transactions on Computers, v.51 n.9, p.1026-1040, September 2002
	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
	Jeffrey W. Smith, A hardware hashing mechanism, Proceedings of the 16th annual Southeast regional conference, p.187-189, April 13-15, 1978, Atlanta, Georgia
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Ted G. Lewis , Curtis R. Cook, Hashing for Dynamic and Static Internal Tables, Computer, v.21 n.10, p.45-56, October 1988
	Deepak Venugopal, An efficient signature representation and matching method for mobile devices, Proceedings of the 2nd annual international workshop on Wireless internet, p.16-es, August 02-05, 2006, Boston, Massachusetts
	Kuo-Chung Tai , Alan L. Tharp, An introduction to computed chaining, Proceedings of the May 19-22, 1980, national computer conference, May 19-22, 1980, Anaheim, California
	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
	Deepak Venugopal , Guoning Hu, Efficient signature based malware detection on mobile devices, Mobile Information Systems, v.4 n.1, p.33-49, January 2008
	M. H. McKinney, Variable-length hash area entries, Proceedings of the June 13-16, 1977, national computer conference, June 13-16, 1977, Dallas, Texas
	Santi Martínez , Magda Valls , Concepció Roig , Josep M. Miret , Francesc Giné, A secure elliptic curve-based RFID protocol, Journal of Computer Science and Technology, v.24 n.2, p.309-318, March 2009