More analysis of double hashing
Tóm tắt
In [8], a deep and elegant analysis shows that double hashing is asymptotically equivalent to the ideal uniform hashing up to a load factor of about 0.319. In this paper we show how a randomization technique can be used to develop a surprisingly simple proof of the result that this equivalence holds for load factors arbitrarily close to 1.
Tài liệu tham khảo
Miklós Ajtai, János Komlós, andEndre Szemerédi: There Is No Fast Single Hashing Algorithm,Information Processing Letters 7 (1978), 270–273.
Béla Bollobás, Andrei Z. Broder andIstvan Simon: The Cost Distribution of Clustering in Random Probing,J. ACM 37 (1990), 224–237.
G. H. Gonnet andR. Baeza-Yates:Handbook of Algorithms and Data Structures: In Pascal and C, Second Edition, Addison-Wesley, Wokingham, England, 1991.
Wassily Hoeffding: Probability Inequalities for Sums of Bounded Random Variables,J. American Statistical Association 58 (1963), 13–30.
Kumar Jog-Dev andS. M. Samuels: Monotone Convergence of Binomial Probabilities and a Generalization of Ramanujan's Equation,The Annals of Mathematical Statistics 39 (1968), 1191–1195.
János Komlós: Private communication, 1986.
Leo J. Guibas: Private communication, Fall 1987.
Leo J. Guibas andEndre Szemerédi: The Analysis of Double Hashing,Journal of Computer and System Sciences 16 (1978), 226–274.
Narendra Karmarkar andRichard M. Karp: The Differencing Method of Set Partititoning, Report No. UCB/CSD 82/113, Computer Science Division (EECS), University of California, Berkeley, December 1982.
D. Knuth:The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, Mass., 1973.
George S. Lueker andMariko Molodowitch: More Analysis of Double Hashing,Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, May 1988, 354–359.
Nicholas Pippenger: Private communication, January 1988.
Jeanette P. Schmidt andAlan Siegel: On Aspects of the Universality and Performance for Closed Hashing,Proc. 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, May 1989, 355–366.
Jeffrey D. Ullman: A Note on the Efficiency of Hash Functions,Journal of the ACM 19 (1972), 569–575.
Andrew C. Yao: Uniform Hashing Is Optimal,Journal of the ACM 32 3 (1985), 687–693.