2
$\begingroup$

If you can make no assumptions about the hash function, how can you find the expected number of slots of certain size k in a hash table? Looking more for a theoretical proof type of answer than a programming answer.

$\endgroup$

migrated from stackoverflow.com Oct 13 '14 at 12:26

This question came from our site for professional and enthusiast programmers.

5
$\begingroup$

I assume under "size of slot" you mean length of chain in hash table with separate chaining collision resolution.

From Knuth, TAoCP, Vol. 3, 6.4, ex. 34 probability of k-length chain in hash table with $M$ slots and $N$ entries is

$\binom{N}{k} \left ( M-1 \right )^{N-k} / M^N$

Assuming "ideal" hash function, however practical real-world hash functions are often very good and could be considered as "ideal" for applying theoretical results.

Applying famous $e$ representations via limits and Stirling's approximation, I derived that the probability in terms of $α=N/M$ (load factor) is approximately equal to k-th value in Poisson distribution with parameter $λ=α$, i. e.

$\alpha^k e^{-\alpha}/k!$

Seems reasonable and was my first assumption before analysing the formula from TAoCP, because average chain length is obviously $α$, which correspond Poisson distribution expected value.

If $α$ (load factor) is equal to 0.75, then probabilities of slot chains to be of the specific length are:

k = 0 -- 0.47
k = 1 -- 0.35
k = 2 -- 0.13
k = 3 -- 0.03
k > 3 -- 0.01
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy