Individual displacements in hashing with coalesced chains

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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

Keywords

Probability, Data Structures and Algorithms, 68P10 (Primary); 60F05, 60G35, 68W40 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/74157

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0502232
 http://arxiv.org/abs/math/0502232

Collections

arXiv