[Solved]: Double hashing - probe count probabilities

Problem Detail: 

From TAoCP, Vol. 3 by Knuth we know that expected (mean) probe counts for hash tables with open adressing and double hashing collision-resolution are:

• $1 \over 1 - \alpha$ - for unsuccessful search

• ${1 \over \alpha} ln({1 \over 1 - \alpha})$ - for succesful search

Where $\alpha$ is load factor.

Are there expressions for probabilities of making exactly $i$ = 1,2,3,.. probes?

Asked By : leventov

Answered By : leventov

As Wandering Logic noted, there are approximate expressions for probabilities of probe count in unsuccessful search case in TAoCP, a few pages later expressions for expected probe count:

$1-\alpha$, $\alpha(1-\alpha)$, $\alpha^2(1-\alpha)$, ... - probabilities of making 1, 2, 3, ... probes respectively.

In successful search case I derived approx. expressions myself, relying on explanation of expected probe count formula in the book:

$1 - {\alpha\over2}$, ${\alpha\over2} - {\alpha^2\over3}$, ${\alpha^2\over3} - {\alpha^3\over4}$, ...

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13445

 Ask a Question

 Download Related Notes/Documents