1
$\begingroup$

In several proofs of the expected lookup length in an open addressing hash table, an assumption is made (which is said to follow from the "simple uniform hashing assumption":

Given a hash table with n slots and m keys in it, the probability that any particular slot is occupied is m/n.

I'm having difficulty creating a mental model involving an experiment and a sample space in which I can derive this.

I'm thinking of a sample space consisting of m-tuples of keys. The experiment is to randomly select one such tuple. The event A is the set of all such tuples that have at least 1 key in them that hashes into the given slot.

The probability of A then is 1 - (the probability that none of the m keys hash to the given slot). So 1 - ((n-1)/n)^m. But that's not equal to m/n...

$\endgroup$
2
  • $\begingroup$ I do not think your formula is right. If I have a hash table with n slots and I insert 2n keys into it then (according to your formula) the probability that a given slot is occupied is (2n)/2 = 2. The maximum value a probability can be is 1. $\endgroup$
    – Bob
    Oct 17 '21 at 20:25
  • 1
    $\begingroup$ @Bob Thanks for helping out. This is an open addressing hash table. There cannot be more keys in it than there are slots. So m < n always. $\endgroup$ Oct 17 '21 at 20:40
0
$\begingroup$

Your probability analysis is incorrect. Let $s$ be any slot in the table.

Then, the probability that none of the $m$ keys maps to the slot $s$ is:

$$\frac{n-1}{n} \cdot \frac{n-2}{n-1} \dotsc \cdot \frac{n-m}{n-m+1} = \frac{n-m}{n}$$

Note that after inserting $t$ keys in the table, there are $n-t$ empty slots in the table including the slot $s$. Therefore, the probability that $s$ is empty in the $(t+1)^{th}$ iteration is $(n-t-1)/(n-t)$ using uniform hashing. Hence, we got the above formula.

Therefore, the probability that the slot $s$ is occupied is $1- (n-m)/n = m/n$

$\endgroup$
2
  • $\begingroup$ I definitely thought about this before posting this question. It wasn't obvious to me that I shouldn't include all the slots when calculating the probability of the next key. The reason is that each key can still hash to an occupied slot. $\endgroup$ Oct 19 '21 at 9:37
  • $\begingroup$ @zagortenay333 There are two ways. One way is to choose the slot uniformly among the unoccupied slots and insert the key there. Another way is to choose the slot uniformly among $n$ slots, and if the key maps to some occupied slot choose the slot again until an unoccupied slot is obtained. The probability distribution of both ways is the same. You obviously can not store two keys in the same slot since it is open addressing. $\endgroup$ Oct 19 '21 at 11:28

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.