3.6 Analysis of Closed Hashing

Load factor $\alpha$

$$\alpha$$$$\;\stackrel{\Delta}{=}\;$$ $${\frac{n}{m}}$$ = $${\frac{\char93 \space \mbox{of elements stored the table}}{\mbox{total \char93 of elements in the table}}}$$

Assume uniform hashing. In this scheme, the probe sequence

< h(k, 0),..., h(k, m - 1) >

for each key k is equally likely to be any permutation of
< 0, 1,..., m - 1 >