3.4.3 Another Example:

Let m be the number of slots.

Assume :	$\bullet$ every even numbered slot occupied and every odd
	numbered slot empty
	$\bullet$ any hash value between 0 . . . m-1 is equally likely
	to be generated.
	$\bullet$ linear probing

 

empty

occupied

empty

occupied

empty

occupied

empty

occupied

Expected number of probes for a successful search = 1

Expected number of probes for an unsuccessful search

$$\left(\vphantom{\frac{1}{2}}\right. {\textstyle\frac{1}{2}} \left.\vphantom{\frac{1}{2}}\right) \left(\vphantom{\frac{1}{2}}\right. {\textstyle\frac{1}{2}} \left.\vphantom{\frac{1}{2}}\right)$$ =

= 1.5