More analysis of double hashing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

More analysis of double hashing

Full text

Pdf (531 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twentieth annual ACM symposium on Theory of computing table of contents

Chicago, Illinois, United States

Pages: 354 - 359

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

George Lueker	Department of Information and Computer Science, University of California, Irvine, Irvine, CA
Mariko Molodowitch	Department of Information and Computer Science, University of California, Irvine, Irvine, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 23, Citation Count: 5

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

ABSTRACT

In [GS78] a deep and elegant analysis showed that double hashing was equivalent to the ideal uniform hashing up to a load factor of about 0.319. In this paper we give an analysis which extends this to load factors arbitrarily close to 1. We understand from [Ko86, Gu87] that Ajtai, Guibas, Komlós, and Szemerédi obtained this result in the first part of 1986; the analysis in this paper is of interest nonetheless because we demonstrate how a resampling technique can be used to obtain a remarkably simple proof.

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.

	AKS78	Mikl6s Ajtai, Jgnos Koml6s, Endre Szemer~di, "There Is No Fast Single Hashing Algorithm," Information Processing Letters 7,6 (October 1978), pp. 270-273.
	Ho63	Wassily Hoeffding, "Probability Inequalities for Sums of Bounded Bandom V~riables," J. American Statistical Association 58 (March 1963), pp. 13-30.
	Ko86	J~nos Kolnl6s, private communication, 1986.
	Gu87	Leo J. Gl, il,as, priwte colun~unication, Fall 1987.
	GS78	Leo J. Guibas and Eudre Szemer~di, "The Analysis of Double Hashing," JournM of Computer and System Sciences 16 (1978), pp. 226-274.
	KK82	Narenda Karmarker , Richard M. Karp, The Differencing Method of Set Partitioning, University of California at Berkeley, Berkeley, CA, 1983
	Kn73	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
	Pi88	Nicholas Pippenger, private communication, January 1988.
	Ul72	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]
	Ya85	Andrew C. Yao, Uniform hashing is optimal, Journal of the ACM (JACM), v.32 n.3, p.687-693, July 1985 [doi>10.1145/3828.3836]

CITED BY 5

	J. P. Schmidt , A. Siegel, On aspects of university and performance for closed hashing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.355-366, May 14-17, 1989, Seattle, Washington, United States
	Alan Siegel, On the statistical dependencies of coalesced hashing and their implications for both full and limited independence, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.10-19, January 22-24, 1995, San Francisco, California, United States
	J. P. Schmidt , A. Siegel, The analysis of closed hashing under limited randomness, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.224-234, May 13-17, 1990, Baltimore, Maryland, United States
	Béla Bollobás , Andrei Z. Broder , Istvan Simon, The cost distribution of clustering in random probing, Journal of the ACM (JACM), v.37 n.2, p.224-237, April 1990
	Gregory L. Heileman , Chaouki T. Abdallah , Bernard M. E. Moret , Bradley J. Smith, Dynamical system representation of open address hash functions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.919-920, January 17-19, 1999, Baltimore, Maryland, United States