The cost distribution of clustering in random probing

ABSTRACT

A new approach to the analysis of random probing hashing algorithms is presented. The probability-generating function in closed form for the asymptotic cost of insertion via random probing with secondary clustering is derived. For higher-order clustering, it is shown that all the moments of the probability distribution of the insertion cost exist and are asymptotically equal to the corresponding moments of the cost distribution under uniform hashing. The method in this paper also leads to simple derivations for the expected cost of insertion for random probing with secondary and higher-order clustering.

REFERENCES

• 1: 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]
• 2: FELLER, W. An Introduction to Probability Theory and Its Applications, vol. I, 3rd Ed. Wiley, New York, 1968.
• 3: Gaston Gonnet , Ian Munro, The analysis of an improved hashing technique, Proceedings of the ninth annual ACM symposium on Theory of computing, p.113-121, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803401]
• 4: 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]
• 5: GUIBAS, L. J., AND SZEMERFDI, E. The analysis of double hashing. J. Comput. Syst. Sci. 16, 2 (1978), 226-274.
• 6: 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
• 7: George Lueker , Mariko Molodowitch, More analysis of double hashing, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.354-359, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62246]
• 8: PATERSON, M.S. Unpublished manuscript, see Chapter 3 ir} GREENE, D. H., AND KNUTH, D. E. Mathematics for the Analysis of Algorithms, 2nd Ed. Birkll~laser, Boston, Mass., 1982, pp. 35-45.
• 9: 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]
• 10: Jeanette P. Schmidt , Eli Shamir, An Improved Program for Constructing Open Hash Tables, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.569-581, July 14-18, 1980
• 11: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Theory