Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Individual displacements for linear probing hashing with different insertion policies

Individual displacements for linear probing hashing with different insertion policies We study the distribution of the individual displacements in hashing with linear probing for three different versions: First Come, Last Come and Robin Hood. Asymptotic distributions and their moments are found when the the size of the hash table tends to infinity with the proportion of occupied cells converging to some α, 0 < α < 1. (In the case of Last Come, the results are more complicated and less complete than in the other cases.)We also show, using the diagonal Poisson transform studied by Poblete, Viola and Munro, that exact expressions for finite m and n can be obtained from the limits as m,n → ∞.We end with some results, conjectures and questions about the shape of the limit distributions. These have some relevance for computer applications. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Individual displacements for linear probing hashing with different insertion policies

Janson, Svante
ACM Transactions on Algorithms (TALG) , Volume 1 (2) – Oct 1, 2005
Download PDF
37 pages

Loading next page...
 
/lp/association-for-computing-machinery/individual-displacements-for-linear-probing-hashing-with-different-uPOLW8Nf9J
Publisher
Association for Computing Machinery
Copyright
Copyright © 2005 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1103963.1103964
Publisher site
See Article on Publisher Site

Abstract

We study the distribution of the individual displacements in hashing with linear probing for three different versions: First Come, Last Come and Robin Hood. Asymptotic distributions and their moments are found when the the size of the hash table tends to infinity with the proportion of occupied cells converging to some α, 0 < α < 1. (In the case of Last Come, the results are more complicated and less complete than in the other cases.)We also show, using the diagonal Poisson transform studied by Poblete, Viola and Munro, that exact expressions for finite m and n can be obtained from the limits as m,n → ∞.We end with some results, conjectures and questions about the shape of the limit distributions. These have some relevance for computer applications.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Oct 1, 2005

There are no references for this article.