More Web Proxy on the site http://driver.im/

article

Individual displacements for linear probing hashing with different insertion policies

Author:

Svante JansonAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 1, Issue 2

Pages 177 - 213

https://doi.org/10.1145/1103963.1103964

Published: 01 October 2005 Publication History

Abstract

We study the distribution of the individual displacements in hashing with linear probing for three different versions: First Come, Last Come and Robin Hood. Asymptotic distributions and their moments are found when the the size of the hash table tends to infinity with the proportion of occupied cells converging to some α, 0 < α < 1. (In the case of Last Come, the results are more complicated and less complete than in the other cases.)We also show, using the diagonal Poisson transform studied by Poblete, Viola and Munro, that exact expressions for finite m and n can be obtained from the limits as m,n → ∞.We end with some results, conjectures and questions about the shape of the limit distributions. These have some relevance for computer applications.

References

[1]

Billingsley, P. 1968. Convergence of Probability Measures. Wiley, New York.

[2]

Borel, É. 1942. Sur l'emploi du théorème de Bernoulli pour faciliter le calcul d'une infinité de coefficients. Application au problème de l'attente à un guichet. C. R. Acad. Sci. Paris 214, 452--456.

[3]

Carlsson, S., Munro, J. I., and Poblete, P. V. 1987. On linear probing hashing. Unpublished manuscript.

[4]

Celis, P., Larson, P.-Å., and Munro, J. I. 1985. Robin Hood hashing (preliminary report). In Proceedings 26th Annual Symposium on Foundations of Computer Science (FOCS'85) (Portland, OR). IEEE Computer Society Press, Los Alamitos, CA, 281--288.

[5]

Chassaing, P., and Louchard, G. 2002. Phase transition for parking blocks, Brownian excursion and coalescence. Random Struct. Alg. 21, 1, 76--119.

Digital Library

[6]

Dwass, M. 1969. The total progeny in a branching process and a related random walk. J. Appl. Probab. 6, 682--686.

[7]

Flajolet, P., Poblete, P., and Viola, A. 1998. On the analysis of linear probing hashing. Algorithmica 22, 4, 490--515.

[8]

Graham, R. L., Knuth, D. E., and Patashnik, O. 1994. Concrete Mathematics, 2nd ed. Addison--Wesley, Reading, MA.

Digital Library

[9]

Janson, S. 2001a. Asymptotic distribution for the cost of linear probing hashing. Random Struct. Alg. 19, 3--4, 438--471.

Digital Library

[10]

Janson, S. 2001b. Moment convergence in conditional limit theorems. J. Appl. Probab. 38, 2, 421--437.

[11]

Kemperman, J. H. B. 1950. The General One-Dimensional Random Walk with Absorbing Barriers with Applications to Sequential Analysis. Excelsiors Foto-Offset, The Hague, The Netherlands. Ph.D. thesis.

[12]

Kemperman, J. H. B. 1961. The Passage Problem for a Stationary Markov Chain. University of Chicago Press, Chicago, IL.

[13]

Kendall, D. G. 1951. Some problems in the theory of queues. J. Roy. Statist. Soc. Ser. B. 13, 151--185.

[14]

Knuth, D. E. 1963. Notes on “open” addressing. Unpublished notes, available at http://www.wits.ac.za/helmut/first.ps.

[15]

Knuth, D. E. 1998a. The Art of Computer Programming. Vol. 3: Sorting and Searching, 2nd ed. Addison-Wesley, Reading, MA.

Digital Library

[16]

Knuth, D. E. 1998b. Linear probing and graphs. Algorithmica 22, 4, 561--568.

[17]

Kolchin, V. F. 1984. Random Mappings. Nauka, Moscow. (Russian). English transl.: Optimization Software, New York, 1986.

[18]

Otter, R. 1949. The multiplicative process. Ann. Math. Statist. 20, 206--224.

[19]

Pavlov, Yu. L. 1977. The asymptotic distribution of maximum tree size in a random forest. Teor. Verojatnost. i Primenen. 22, 3, 523--533. (Russian). English transl.: Th. Probab. Appl. 22, 3 (1977), 509--520.

[20]

Pavlov, Yu. L. 1996. Random forests. Karelian Centre Russian Acad. Sci., Petrozavodsk. (Russian). English transl.: VSP, Zeist, The Netherlands, 2000.

[21]

Pitman, J. 1998. Enumerations of trees and forests related to branching processes and random walks. In Microsurveys in Discrete Probability (Princeton, NJ, 1997). Number 41 in DIMACS Ser. Discrete Math. Theoret. Comput. Sci., American Mathmatics Society, Providence, RI, 163--180.

[22]

Poblete, P. V., and Munro, J. I. 1989. Last-come-first-served hashing. J. Algorithms 10, 2, 228--248.

Digital Library

[23]

Poblete, P. V., Viola, A., and Munro, J. I. 1997a. Analyzing the LCFS linear probing hashing algorithm with the help of Maple. MapleTech 4, 1, 8--13.

[24]

Poblete, P. V., Viola, A., and Munro, J. I. 1997b. The diagonal Poisson transform and its application to the analysis of a hashing scheme. Random Struct. Alg. 10, 1--2, 221--255.

Digital Library

[25]

Takács, L. 1967. Combinatorial Methods in the Theory of Stochastic Processes. Wiley, New York.

[26]

Takács, L. 1989. Ballots, queues and random graphs. J. Appl. Probab. 26, 1, 103--112.

[27]

Tanner, J. C. 1961. A derivation of the Borel distribution. Biometrika 48, 222--224.

[28]

Viola, A. 1995. Analysis of hashing algorithms and a new mathematical transform. Ph.D. thesis, Technical report CS-95-50, Computer Science Department, University of Waterloo, Waterloo, ON, Canada.

Digital Library

[29]

Viola, A. 2005. Exact distributions of individual displacements in linear probing hashing. ACM Trans. Algorithms 1, 2, 214--242.

Digital Library

Cited By

Klein TLagnoux APetit P(2022)Deviation results for sparse tables in hashing with linear probingProbability Theory and Related Fields10.1007/s00440-021-01100-1183:3-4(871-908)Online publication date: 4-May-2022
https://doi.org/10.1007/s00440-021-01100-1
Krapivsky PRedner S(2020)Where should you park your car? The $\frac{1}{2}$ ruleJournal of Statistical Mechanics: Theory and Experiment10.1088/1742-5468/ab96b72020:7(073404)Online publication date: 14-Jul-2020
https://doi.org/10.1088/1742-5468/ab96b7
Klein TLagnoux APetit P(2019)A conditional Berry–Esseen inequalityJournal of Applied Probability10.1017/jpr.2019.756:01(76-90)Online publication date: 12-Jul-2019
https://doi.org/10.1017/jpr.2019.7
Show More Cited By

Index Terms

Individual displacements for linear probing hashing with different insertion policies
1. Information systems
  1. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
        Hashed file organization

Recommendations

Exact distribution of individual displacements in linear probing hashing

This paper studies the distribution of individual displacements for the standard and the Robin Hood linear probing hashing algorithms. When the a table of size m has n elements, the distribution of the search cost of a random element is studied for both ...
Asymptotic distribution for the cost of linear probing hashing
Special issue on analysis of algorithms dedicated to Don Knuth on the occasion of his (100)₈th birthday
Linear Probing with Constant Independence

Hashing with linear probing dates back to the 1950s and is among the most widely studied algorithms. In recent years, it has become one of the most important hash table organizations because it uses the cache of modern computers very well. Unfortunately,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 1, Issue 2

October 2005

190 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1103963

Issue’s Table of Contents

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2005

Published in TALG Volume 1, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
949
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)3

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Klein TLagnoux APetit P(2022)Deviation results for sparse tables in hashing with linear probingProbability Theory and Related Fields10.1007/s00440-021-01100-1183:3-4(871-908)Online publication date: 4-May-2022
https://doi.org/10.1007/s00440-021-01100-1
Krapivsky PRedner S(2020)Where should you park your car? The $\frac{1}{2}$ ruleJournal of Statistical Mechanics: Theory and Experiment10.1088/1742-5468/ab96b72020:7(073404)Online publication date: 14-Jul-2020
https://doi.org/10.1088/1742-5468/ab96b7
Klein TLagnoux APetit P(2019)A conditional Berry–Esseen inequalityJournal of Applied Probability10.1017/jpr.2019.756:01(76-90)Online publication date: 12-Jul-2019
https://doi.org/10.1017/jpr.2019.7
Butler SGraham RYan C(2017)Parking distributions on treesEuropean Journal of Combinatorics10.1016/j.ejc.2017.06.00365:C(168-185)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1016/j.ejc.2017.06.003
(2016)Parking functions for mappingsJournal of Combinatorial Theory Series A10.1016/j.jcta.2016.03.001142:C(1-28)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.jcta.2016.03.001
Janson SViola A(2016)A Unified Approach to Linear Probing Hashing with BucketsAlgorithmica10.1007/s00453-015-0111-x75:4(724-781)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s00453-015-0111-x
Goodrich MKornaropoulos EMitzenmacher MTamassia R(2016)More Practical and Secure History-Independent Hash TablesComputer Security – ESORICS 201610.1007/978-3-319-45741-3_2(20-38)Online publication date: 15-Sep-2016
https://doi.org/10.1007/978-3-319-45741-3_2
PETERSSON N(2013)The Maximum Displacement for Linear Probing HashingCombinatorics, Probability and Computing10.1017/S096354831200058222:03(455-476)Online publication date: 24-Jan-2013
https://doi.org/10.1017/S0963548312000582
Shutler PSim SLim W(2008)Analysis of Linear Time Sorting AlgorithmsThe Computer Journal10.1093/comjnl/bxm09751:4(451-469)Online publication date: 1-Jul-2008
https://dl.acm.org/doi/10.1093/comjnl/bxm097
Hyvonen JSaramaki JKaski K(2008)Efficient data structures for sparse network representationInternational Journal of Computer Mathematics10.1080/0020716070175362985:8(1219-1233)Online publication date: 1-Aug-2008
https://dl.acm.org/doi/10.1080/00207160701753629
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents