The Diagonal Poisson Transform and its application to the analysis of a hashing scheme

Abstract

We present an analysis of the effect of the last-come-first-served heuristic on a linear probing hash table. We study the behavior of successful searches, assuming searches for all elements of the table are equally likely. It is known that the Robin Hood heuristic achieves minimum variance over all linear probing algorithms. We show that the last-come-first-served heuristic achieves this minimum up to lower-order terms. An accurate analysis of this algorithm is made by introducing a new transform which we call the Diagonal Poisson Transform as it resembles the Poisson Transform. We present important properties of this transform, as well as its application to solve some classes of recurrences, find inverse relations, find asymptotics, and obtain several generalizations of Abel's summation formula. We feel the introduction of this transform is the main contribution of the paper. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 221–255 (1997)