Analysis of hashing algorithms and a new mathematical transform
Ian Munro, Patricio V. Poblete, Alfredo Viola · 1996
The main contribution of this thesis is the introduction of a new mathematical tool that we call the Diagonal Poisson Transform, and its application to the analysis of some linear probing hashing schemes. We also present what appears to be the first exact analysis of a linear probing hashing scheme with buckets of size b. First, we present the Diagonal Poisson Transform. We show its main properties and apply it to solve recurrences, find inverse relations and obtain several generalizations of Abel's summation formula. We follow with the analysis of LCFS hashing with linear probing. It is known that the Robin Hood linear probing algorithm minimizes the variance of the cost of successful searches for all linear probing algorithms. We prove that the variance of the LCFS scheme is within lower order terms of this optimum. Finally we present the first exact analysis of linear probing hashing with buckets of size b. From the generating function for the Robin Hood heuristic, we obtain exact expressions for the cost of successful searches when the table is full. Then, with the help of Singularity Analysis, we find the asymptotic expansion of this cost up to $O((bm)\sp{-1})$, where m is the number of buckets. We also give upper and lower bounds when the table is not full. We conclude with a new approach to study certain recurrences that involves truncated exponentials. A new family of numbers that satisfies a recurrence resembling that of the Bernoulli numbers is introduced. These numbers may prove helpful in studying recurrences involving truncated generating functions.