0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 13 '14 at 17:44
  • 1
    $\begingroup$ Explain what $M,N$ are! $\endgroup$ – Yuval Filmus Dec 13 '14 at 17:47
1
$\begingroup$

To give you a test of the analysis, here it is for chaining.

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.

If we are more careful then we will probably get the formulas stated at the first row of the table, or at least something very close.

The other rows of the table result from similar analysis. Each case is different. If you want to know more, I suggest you look for other online or offline resources rather than probing us here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.