On Search Times for Early-Insertion Coalesced Hashing
Boris G. Pittel, Jenn-Hwa Yu · SIAM Journal on Computing · 1988
The distributions of the search times for an early-insertion form of coalesced hashing (first proposed by Vitter [11], [12]) are studied. It is demonstrated, in particular, that the largest search time is very close, in probability, to the one for the late-insertion coalesced hashing [8]. In addition, a formula for the expected successful search time obtained by Chen and Vitter [1] and, independently, by Knott [7] is shown to follow directly from the presented analysis.