# Double hashing - probe count probabilities

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?

• 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." – Wandering Logic Jul 25 '13 at 21:29

## 1 Answer

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