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 – {alphaover2}$, ${alphaover2} – {alpha^2over3}$, ${alpha^2over3} – {alpha^3over4}$, …
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13445 Ask a Question Download Related Notes/Documents
