uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The maximum displacement for linear probing hashing
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
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
Abstract [en]

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.
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-98027DOI: 10.1017/S0963548312000582ISI: 000317130400010OAI: oai:DiVA.org:uu-98027DiVA: diva2:173187
Available from: 2009-02-05 Created: 2009-02-05 Last updated: 2013-05-23Bibliographically approved
In thesis
1. The Maximum Displacement for Linear Probing Hashing
Open this publication in new window or tab >>The Maximum Displacement for Linear Probing Hashing
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis we study the standard probabilistic model for hashing with linear probing. The main purpose is to determine the asymptotic distribution for the maximum displacement. Depending on the ratio between the number of items and the number of cells, there are several cases to consider. Paper I solves the problem for the special case of almost full hash tables. That is, hash tables where every cell but one is occupied. Paper II completes the analysis by solving the problem for all remaining cases. That is, for every case where the number of items divided by the number of cells lies in the interval [0,1].

The last two papers treat quite different topics. Paper III studies the area covered by the supremum process of Brownian motion. One of the main theorems in Paper I is expressed in terms of the Laplace transform of this area. Paper IV provides a new sufficient condition for a collection of independent random variables to be negatively associated when conditioned on their total sum. The condition applies to a collection of independent Borel-distributed random variables, which made it possible to prove a Poisson approximation that where essential for the completion of Paper II.

Place, publisher, year, edition, pages
Uppsala: Universitetsbiblioteket, 2009. viii+20 p.
Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 63
Keyword
Probabilistic analysis of algorithms, hashing, linear probing, negative dependence, Brownian motion.
National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-9545 (URN)978-91-506-2050-4 (ISBN)
Public defence
2009-02-27, Polhemsalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 13:15
Opponent
Supervisors
Available from: 2009-02-05 Created: 2009-02-05Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Department of Mathematics
In the same journal
Combinatorics, probability & computing
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 457 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf