On Probabilistic Analysis of a Coalesced Hashing Algorithm
Pittel, B.
Ann. Probab., Tome 15 (1987) no. 4, p. 1180-1202 / Harvested from Project Euclid
An allocation model [$n$ balls, $m (\geq n)$ cells, at most one ball in a cell] related to a hashing algorithm is studied. A ball $x$ goes into the cell $h(x)$, where $h(\cdot): \{1,\cdots, n\} \rightarrow \{1, \cdots, m\}$ is random. In case the cell $h(x)$ is already occupied, the ball $x$ is rejected and moved into the leftmost empty cell. This empty cell is found via the sequential search from left to right starting with the cell occupied by the last (before $x$) rejected ball. Denote $T_2(x)$ the number of the necessary probes. In the end, due to a resulting system of references, the $n$ occupied cells form a disjoint union of ordered chains, and to locate a ball $x$ it suffices to search only the cells of a subchain originating at the cell $h(x)$. Denote $T_1(x)$ the length of this subchain. The main result of the paper is: in probability, $\max T_1(x) = \log_bn - 2\log_b\log n + O(1),$ $\max T_2(x) = \log_bn - \log_b\log n + O(1),$ as $n \rightarrow \infty$, if $n/m$ is bounded away from $0, b = (1 - e^{-n/m})^{-1}$.
Publié le : 1987-07-14
Classification:  Search algorithm,  hashing,  probabilistic analysis,  limiting distributions,  largest search time,  60C05,  60F99,  68P10,  68P20,  68R05,  05C80
@article{1176992090,
     author = {Pittel, B.},
     title = {On Probabilistic Analysis of a Coalesced Hashing Algorithm},
     journal = {Ann. Probab.},
     volume = {15},
     number = {4},
     year = {1987},
     pages = { 1180-1202},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176992090}
}
Pittel, B. On Probabilistic Analysis of a Coalesced Hashing Algorithm. Ann. Probab., Tome 15 (1987) no. 4, pp.  1180-1202. http://gdmltest.u-ga.fr/item/1176992090/