Expected Length of the Longest Probe Sequence in Hash Code Searching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Expected Length of the Longest Probe Sequence in Hash Code Searching

Full text

Pdf (672 KB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 2 (April 1981) table of contents

Pages: 289 - 304

Year of Publication: 1981

ISSN:0004-5411

Author

Gaston H. Gonnet

Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 36, Downloads (12 Months): 128, Citation Count: 28

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/322248.322254 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	ABRAMOVITZ, M., AND STEGUN, I A. Handbook of Mathematical Functions Dover Publications, New York, 1964.
	2	ARFWEDSON, G A probabdlty distribution connected wRh Surhng's second class numbers. Skand Aktuartetidskrift 34, 3 (1951), 121-132
	3	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]
	4	DE BRUIJN, N.G.Asymptotic Methods m Analysis. North-Holland, Amsterdam, 1970
	5	FELLER, W. An Introduction to Probabd~ty Theory and Its Apphcatlons, VoL L John Wdey, New York, 1957, 3rd ed.
	6	GONNET, G.H.Average lower bounds for open-addressing hash coding. Proc. Conf. on Theoretical Computer Science, Waterloo, Ontario, Canada, Aug. 1977, pp 159-162.
	7	GONNET, G H Notes on the denvauon of asymptouc expressions from summations, lnf Proce. Lett. 7, 4 (June 1978), 165-169
	8	GONNET, G H, AND MUNRO, J I Efficient ordenng of hash tables SIAM ~ Comput. 8, 3 (Aug 1979), 463-478.
	9	Leo J. Guibas, The Analysis of Hashing Techniques That Exhibit k-ary Clustering, Journal of the ACM (JACM), v.25 n.4, p.544-555, Oct. 1978 [doi>10.1145/322092.322096]
	10	GUIBAS, L.J, AND SZEMEREDI, E The analysts of double hashing. J Comput. Syst. Sct 16, 2 (Aprd 1978), 226-274.
	11	HANSEN, E.R A Table of Series and Products. Prentice Hall, Englewood Cliffs, N.J, 1975.
	12	HARDY, G.H, AND WRIGHT, E M. An Introduction to the Theory of Numbers Oxford Umversay Press, Oxford, England, 1975
	13	JOHNSON, N L, AND KOTZ, S Dtstnbuttons m Stattsttcs Vol 1, Discrete Distributions Houghton Mifflin, Boston, 1969
	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	Ronald L. Rivest, Optimal Arrangement of Keys in a Hash Table, Journal of the ACM (JACM), v.25 n.2, p.200-209, April 1978 [doi>10.1145/322063.322065]
	16	STEVENS, W.L. Significance grouping. Ann. Eugenics 8 (1937), 57-69.

CITED BY 29

	Luc Devroye, Laws of large numbers and tail inequalities for random tries and PATRICIA trees, Journal of Computational and Applied Mathematics, v.142 n.1, p.27-37, 1 May 2002
	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
	Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
	Micah Adler , Soumen Chakrabarti , Michael Mitzenmacher , Lars Rasmussen, Parallel randomized load balancing, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.238-247, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Amos Fiat , Moni Naor , Jeanette P. Schmidt , Alan Siegel, Nonoblivious hashing, Journal of the ACM (JACM), v.39 n.4, p.764-782, Oct. 1992
	Amos Fiat , Moni Naor , Jeanette Schmidt , Alan Siegel, Non-oblivious hashing, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.367-376, May 02-04, 1988, Chicago, Illinois, United States
	M. V. Ramakrishna, Hashing practice: analysis of hashing and universal hashing, ACM SIGMOD Record, v.17 n.3, p.191-199, June 1988
	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada
	Per-Åke Larson, Performance analysis of linear hashing with partial expansions, ACM Transactions on Database Systems (TODS), v.7 n.4, p.566-587, Dec. 1982
	Walter A. Burkhard, Interpolation-based index maintenance, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	K. Donovan, Performance of Shared Memory in a Parallel Computer, IEEE Transactions on Parallel and Distributed Systems, v.2 n.2, p.253-256, April 1991
	Chung-Min Chen , Rakesh K. Sinha, Analysis and Comparison of Declustering Schemes for Interactive Navigation Queries, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.763-778, September 2000
	M. V. Ramakrishna , E. Fu , E. Bahcekapili, Efficient Hardware Hashing Functions for High Performance Computers, IEEE Transactions on Computers, v.46 n.12, p.1378-1381, December 1997
	Hagit Attiya , David Hay, Randomization does not reduce the average delay in parallel packet switches, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Luc Devroye , Pat Morin, Cuckoo hashing: further analysis, Information Processing Letters, v.86 n.4, p.215-219, 31 May 2003
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Nikhil Bansal , Tracy Kimbrel , Maxim Sviridenko, Job shop scheduling with unit processing times, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Krishnaram Kenthapadi , Gurmeet Singh Manku, Decentralized algorithms using both local and random probes for P2P load balancing, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Sailesh Kumar , Patrick Crowley, Segmented hash: an efficient hash table implementation for high performance networking subsystems, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA
	Krishnaram Kenthapadi , Rina Panigrahy, Balanced allocation on graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.434-443, January 22-26, 2006, Miami, Florida
	Niloy J. Mitra , Leonidas J. Guibas , Mark Pauly, Partial and approximate symmetry detection for 3D geometry, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	M. Gairing , T. Lücking , M. Mavronicolas , B. Monien , P. Spirakis, Structure and complexity of extreme Nash equilibria, Theoretical Computer Science, v.343 n.1-2, p.133-157, 10 October 2005
	Spyros Kontogiannis, Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Michael Mitzenmacher, Studying Balanced Allocations with Differential Equations, Combinatorics, Probability and Computing, v.8 n.5, p.473-482, September 1999
	Nikhil Bansal , Tracy Kimbrel , Maxim Sviridenko, Job Shop Scheduling with Unit Processing Times, Mathematics of Operations Research, v.31 n.2, p.381-389, February 2006
	Simon Fischer , Berthold Vöcking, On the structure and complexity of worst-case equilibria, Theoretical Computer Science, v.378 n.2, p.165-174, June, 2007
	Ye Xia , Shigang Chen , Chunglae Cho , Vivekanand Korgaonkar, Algorithms and performance of load-balancing with multiple hash functions in massive content distribution, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.1, p.110-125, January, 2009
	P. Brighten Godfrey, Balls and bins with structure: balanced allocations on hypergraphs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.511-517, January 20-22, 2008, San Francisco, California
	Wei Wang , Mehul Motani , Vikram Srinivasan, Dependent link padding algorithms for low latency anonymity systems, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA