Individual displacements in hashing with coalesced chains
arXiv:math/0502232
Abstract
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.
17 pages