Say, I want to put N objects into a hash table. How do I figure out how big the size of the table needs to be to have K comparisons on average when the table is: half full? three quarters full? all but last full?
Basically, this is due to me not really understanding the theory. I tried googling it, but didn't get it either. Can I have an explanation even a monkey would understand?
This explanation is for the Homo sapiens sapiens subspecies of Cercopithecidae (old world monkeys). For an explanation suitable for other subspecies you'll have to try Knuth.
I'll assume you are talking about collision resolution by open addressing, and double hashing to determine the probe sequence. Further we'll assume that the hash functions are good (that is: that they are essentially producing uniformly distributed, independent random integers.)
We will use $N$ for the number of objects already in the hash table, $M$ for the total number of buckets in the hash table and $\alpha = N/M$ as the load factor. The load factor is the fraction of buckets that are already taken, and is really the important thing here.
If I try to insert a new item in a hash table with load factor $\alpha$ what is the probability that I will get a collision on my first probe? Answer: $\alpha$. Thus the probability that I find an open bucket on my first probe is $1-\alpha$.
What is the probability that I will find an open bucket on exactly my second probe? Well the probability that I failed to find an open bucket on my first probe is $\alpha$ and the probability that I succeed on my second probe is $1-\alpha$, which gives a total probability of $\alpha (1-\alpha)$.
What is the probability that I will find an open bucket on exactly my third probe? Well the probability that I failed to find an open bucket on my first and second probes is $\alpha^2$, and the probability that I succeed on my third probe is $1-\alpha$ so I have a total probability of $\alpha^2 (1-\alpha)$.
I'm an engineer, not a mathematician, so that's good enough for me to assume that the pattern holds for all positive integers. That is I've just "proved" that the probability I will take $k$ probes to find an open bucket is $$ p(k) = \alpha^{k-1} (1-\alpha). $$
(Exercise: make sure that this is a good probability by showing that $\sum_{k=1}^\infty \alpha^{k-1}(1-\alpha)=1$.) Now what's the expected number of probes to find an open bucket?
$$ \begin{eqnarray} E[\mathrm{number\ of\ probes}] &=& \sum_{k=1}^\infty k p(k) \\ &=& \sum_{k=1}^\infty k \alpha^{k-1}(1-\alpha) \\ &=& (1-\alpha)\sum_{k=1}^\infty k \alpha^{k-1} \\ &=& \frac{1-\alpha}{\alpha}\sum_{k=1}^\infty k \alpha^k. \end{eqnarray}$$
I look up this series on Wikipedia and see that $\sum_{k=1}^\infty k \alpha^k = \alpha / (1-\alpha)^2$ so
$$ E[\mathrm{number\ of\ probes}] = \frac{1}{1-\alpha}. $$
