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?

  • 2
    $\begingroup$ He derives the expectations for uniform probing from the probabilities just a few pages later. I have second edition (1998), and the derivation starts on pg 534 under the section titled "Analysis of the algorithms." $\endgroup$ Jul 25 '13 at 21:29

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}$, ...


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.