The maximum displacement for linear probing hashing
2013 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 3, 455-476 p.Article in journal (Refereed) Published
In this paper we study the maximum displacement for linear probing hashing. We use thestandard 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 withdisplacement 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.
Place, publisher, year, edition, pages
2013. Vol. 22, no 3, 455-476 p.
IdentifiersURN: urn:nbn:se:uu:diva-98027DOI: 10.1017/S0963548312000582ISI: 000317130400010OAI: oai:DiVA.org:uu-98027DiVA: diva2:173187