# Expected Lookup Length in Open Addressing Hash Table with Simple Uniform Hashing

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...

• 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.
– Bob
Oct 17, 2021 at 20:25
• @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. Oct 17, 2021 at 20:40

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$$
• @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. Oct 19, 2021 at 11:28