Individual Displacements in Hashing with Coalesced Chains
Svante Janson · Combinatorics Probability Computing · 2008
We study the asymptotic distribution of the displacements in hashing with coalesced chains, for both late-insertion and early-insertion. Asymptotic formulas for means and variances follow. The method uses Poissonization and some stochastic calculus.