Part II: HASHING FOR STORAGE: DATA MANAGEMENT
CHAPTER 13
Hashing with Linear Probing
13.1 FORMULATION AND PRELIMINARIES
W. Wesley Peterson (1924–2009) evaluated the collision-resolution performance using a simulation of linear open addressing, which is also referred to as scatter storage and linear probing (LP).
We use the statistical model defined in Chapter 9, §9.1 to analyze linear probing; the cells of the m keys k = (k0, k1, … , km−1) are inserted by LP in a hash table (HT) of size n cells using a hash function h. The model postulates the independence and uniform distribution of hashing sequences; that is, the pair (h, k) produces nm equally likely hash sequences h(k) = (h(k0), h(k1), … , h(km−1)). Although most performance analysts question the assumption of a uniform distribution, there is little prognosis for success in modeling performance of LP if the assumption were replaced by another specific distribution, whose appropriateness would certainly be questioned. Furthermore, the results of McKenzie et al. [Mckenzie, Harries and Bell 1990] described in Chapter 9, §9.6 suggests the uniform distribution assumption is not unreasonable.
Hash-table cell HTj contains a flag (F = 0/1); if F = 1, a key k* and a pointer ADD[k*] are stored at HTj. LP involves a procedure by which the calculated hash-table cell 
of key ki is translated into the actual hash-table cell . For example, ...
