THE ANALYSIS OF LINEAR PROBING HASHING WITH BUCKETS

present the first exact analysis of a linear probing hashing scheme wi th buckets of size b. From the generating function for the Robin Hood heuristic we obtain exact expressions for the cost of successful searc hes. For a full table, with the help of Singularity Analysis, we find the asymptotic expansion of this cost up to O((bm)(-1)). We conclude w ith a new approach to study certain recurrences that involve truncated exponentials. A new family of numbers that satisfies a recurrence res embling that of the Bernoulli numbers is introduced. These numbers may prove helpful in studying recurrences involving truncated generating functions.