No CrossRef data available.
Article contents
The Maximum Displacement for Linear Probing Hashing
Published online by Cambridge University Press: 24 January 2013
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.
In this paper we study the maximum displacement for linear probing hashing. We use the standard probabilistic model together with the insertion policy known as First-Come-(First-Served). The results are of asymptotic nature and focus on dense hash tables. That is, the number of occupied cells n and the size of the hash table m tend to infinity with ratio n/m → 1. We present distributions and moments for the size of the maximum displacement, as well as for the number of items with displacement larger than some critical value. This is done via process convergence of the (appropriately normalized) length of the largest block of consecutive occupied cells, when the total number of occupied cells n varies.
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2013
References
[1]Barbour, A. D., Holst, L. and Janson, S. (2003) Poisson Approximation, first edition, Oxford University Press.Google Scholar
[3]Celis, P., Larson, P-Å. and Munro, J. I. (1985) Robin Hood hashing. In 26th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 281–288.Google Scholar
[4]Chassaing, P. and Janson, S. (2001) A Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0. Ann. Probab. 29 1755–1779.Google Scholar
[5]Chassaing, P. and Louchard, G. (2002) Phase transition for parking blocks, Brownian excursion and coalescence. Random Struct. Alg. 21 76–119.Google Scholar
[6]Chassaing, P. and Marckert, J.-F. (2001) Parking functions, empirical processes, and the width of rooted labeled trees. Electron. J. Combin. 8 #R14.Google Scholar
[7]Devroye, L. (1985) The expected length of the longest probe sequence when the distribution is not uniform. J. Algorithms 6 1–9.Google Scholar
[8]Devroye, L., Morin, P. and Viola, A. (2004) On worst-case Robin Hood hashing. SIAM. J. Comput. 33 923–936.CrossRefGoogle Scholar
[9]Flajolet, P., Poblete, P. and Viola, A. (1998) On the analysis of linear probing hashing. Algorithmica 22 490–515.Google Scholar
[10]Gonnet, H. (1981) Expected length of the longest probe sequence in hash code searching. J. Assoc. Comput. Mach. 28 289–304.Google Scholar
[11]Janson, S. (2005) Individual displacements for linear probing hashing with different insertion policies. ACM Trans. Algorithms 1 177–213.Google Scholar
[12]Janson, S. and Petersson, N. (2009) The integral of the supremum process of Brownian motion. J. Appl. Probab. 46 593–600.Google Scholar
[13]Johnson, N. L., Kemp, A. W. and S. Kontz, S. (2005) Univariate Discrete Distributions, third edition, Wiley.Google Scholar
[14]Kallenberg, O. (2002) Foundations of Modern Probability, second edition, Springer.Google Scholar
[15]Karatzas, I. and Shreve, S. E. (2004) Brownian Motion and Stochastic Calculus, second edition, Springer.Google Scholar
[16]Knuth, D. E. (1998) The Art of Computer Programming, Vol. 3, Sorting and Searching, second edition, Addison-Wesley.Google Scholar
[18]Perman, M. and Wellner, J. A. (1996) On the distribution of Brownian areas. Ann. Appl. Probab. 6 1091–1111.CrossRefGoogle Scholar
[19]Poblete, P. V. and Munro, J. I. (1989) Last-come-first-served hashing. J. Algorithms 10 228–248.Google Scholar
[20]Poblete, P. V., Viola, A. and Munro, J. I. (1997) The diagonal Poisson transform and its application to the analysis of a hashing scheme. Random Struct. Alg. 10 221–255.3.0.CO;2-B>CrossRefGoogle Scholar
[21]Viola, A. (2005) Exact distributions of individual displacements in linear probing hashing. ACM Trans. Algorithms 1 214–242.CrossRefGoogle Scholar
You have
Access