THE DIAGONAL POISSON TRANSFORM AND ITS APPLICATION TO THE ANALYSIS OFA HASHING SCHEME

We present an analysis of the effect of the last-come-first-served heu ristic on a linear probing hash table. We study the behavior of succes sful searches, assuming searches for all elements of the table are equ ally likely. It is known that the Robin Hood heuristic achieves minimu m variance over all linear probing algorithms. We show that the last-c ome-first-served heuristic achieves this minimum up to lower-order ter ms. An accurate analysis of this algorithm is made by introducing a ne w transform which we call the Diagonal Poisson Transform as it resembl es the Poisson Transform. We present important properties of this tran sform, as well as its application to solve some classes of recurrences , find inverse relations, find asymptotics, and obtain several general izations of Abel's summation formula. We feel the introduction of this transform is the main contribution of the paper. (C) 1997 John Wiley & Sons, Inc.