The Maximum Displacement for Linear Probing Hashing

Sammanfattning: 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.