I am having a hard time understanding the numbers of probing which might occur due to using different collision prevention method such as separate chaining, Linear Probing, double probing, which is given here.
Let $\alpha = N/M$ (the load factor: average number of keys per array index). Analysis is probabilistic, rather than worst-case.
Expected number of probes:
$$\begin{eqnarray*} &\text{not found} & \quad\text{found}\\ \text{chaining}\quad & 1+\alpha &\quad1+\frac\alpha2\\ \text{linear probing}\quad & \frac12 + \frac1{2(1-\alpha)^2} &\quad \frac12 + \frac1{2(1-\alpha)} \\ \text{double hashing}\quad &\frac1{1-\alpha} &\quad \frac1\alpha \ln\frac1{1-\alpha} \end{eqnarray*}$$
A clarification of why the numbers are as they are would be appreciated. :)