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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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
