Linear probing with a nonuniform address distribution
Georg Ch. Pflug, Hans W. Kessler · Journal of the ACM · 1987
This paper presents a new approach to the analysis of hashing with linear probing for nonuniformly distributed hashed keys. The use of urn models is avoided. Instead, some facts about empirical processes, which are well known in statistics are used. In particular, an asymptotic formula for the expected probe length for both a successful and an unsuccessful search is obtained. The accuracy of the approximation is confirmed by simulation.