Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-10T10:42:46.573Z Has data issue: false hasContentIssue false
  • English
  • Français

Individual Displacements in Hashing with Coalesced Chains

Published online by Cambridge University Press:  01 November 2008

SVANTE JANSON
SVANTE JANSON*
Affiliation:
Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden (e-mail: svante.janson@math.uu.sehttp://www.math.uu.se/~svante/)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study the asymptotic distribution of the displacements in hashing with coalesced chains, for both late-insertion and early-insertion. Asymptotic formulas for means and variances follow. The method uses Poissonization and some stochastic calculus.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 6 , November 2008 , pp. 799 - 814
Copyright
Copyright © Cambridge University Press 2008

References

[1]Athreya, K. B. and Ney, P. E. (1972) Branching Processes, Springer, Berlin.CrossRefGoogle Scholar
[2]Billingsley, P. (1968) Convergence of Probability Measures, Wiley, New York.Google Scholar
[3]Chen, W. C. and Vitter, J. S. (1983) Analysis of early-insertion standard coalesced hashing. SIAM J. Comput. 12 667–676.CrossRefGoogle Scholar
[4]Janson, S. (2005) Individual displacements for linear probing hashing with different insertion policies. ACM Trans. Algorithms 1 177–213.CrossRefGoogle Scholar
[5]Knott, G. D. (1984) Direct-chaining with coalescing lists. J. Algorithms 5 7–21.CrossRefGoogle Scholar
[6]Knuth, D. E. (1998) The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd edn, Addison-Wesley, Reading, MA.Google Scholar
[7]Protter, P. E. (2004) Stochastic Integration and Differential Equations, 2nd edn, Springer, Berlin.Google Scholar
[8]Viola, A. (2005) Exact distributions of individual displacements in linear probing hashing. ACM Trans. Algorithms 1 214–242.CrossRefGoogle Scholar
[9]Vitter, J. S. and Chen, W. C. (1987) Design and Analysis of Coalesced Hashing, International Series of Monographs on Computer Science, Oxford University Press, New York.Google Scholar
[10]Williams, F. A. (1959) Handling identifiers as internal symbols in language processors. Comm. Assoc. Comput. Mach. l2 21–24.Google Scholar