# How does these Probing time occurs for hash tables

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. :)

• The link that you give is dead. There is no super short explanation of these numbers, but they are proved in many textbooks. They are not pulled out of the hat, but rather calculated and found to be what's in the table. – Yuval Filmus Dec 13 '14 at 17:44
• Explain what $M,N$ are! – Yuval Filmus Dec 13 '14 at 17:47

When the load factor is $\alpha$, the length of the list at each cell is distributed $\mathrm{Bin}(N,1/M)$, and its expected value is $N/M = \alpha$. When the probe is not found, we have to go over the entire list, and thus we have something like $\alpha$ probes in expectation. When the probe is found, the length of the list is $\mathrm{Bin}(N,1/M)$ conditioned on being positive, which is somewhat larger than $\alpha$ (and can be calculated exactly). In this case, assuming that the probed element is chosen at random from the set of all elements, its position in the list is uniformly random, and so in expectation it is found at the middle of the list, and therefore we have something like $\alpha/2$ probes.