If we store n keys in a hash table of size m=n^2 , then what is the probability of any collision ?

Question

The hash function is randomly chosen from a universal class of hash functions , then what is the probability of any collision ?

Comments

A doubt in question..
Are you asking the probability of collision while storing the n keys.
OR
The probability of collision once those n keys are already there and a new key is going to be added.

---

In general scenario , we always consider the case when we are in the process of inserting the keys , i.e. some keys are inserted and some new keys are in the process of being added ,But I would like to know both cases .

Answer 1

Scenario 1 : When n keys are already stored and new key is added
Here we are using Universal Hashing, so we can assume that a key can go to each of the m hash table slots with equal probability, i.e. 1/m.
Now given, n keys are already stored out of m=n² slots.
now if a new key comes, it can go to any of the m slots with equal probability. Collision will occur only if it chooses one of the n slots which already has a key
Probability of collision would be = n/m
                                               = n/n²
                                               = 1/n

Scenario 2 : When we are adding those n keys
X - Collision occurs
X' - Collision doesnot occur
P(X)=1 - P(X')
We try to find P(X') because that is easier
Now, for the first key to be added we can add it any of the m slots, so m choices
Now, one of the m slots is occupied. we try to add second key, to avoid collision we have m-1 choices
Similarly, for third key we have m-2 choices..

P(X') = $\frac{m}{m} * \frac{m-1}{m} * \frac{m-2}{m} * \frac{m-3}{m} * . . . . .* \frac{m-n+1}{m}$
Substitute m= n² and get P(X')
Then you get your answer by P(X) = 1 - P(X')

PS: The above solutions assume no chaining, otherwise the method becomes more complex

Answer 2

Theorem: In hashing $n$ items into a hash table with $m$ locations, the expected number of collisions is $n-m+m(1 − \frac{1}{m} )^n$.

Here we have $n$ keys to hash and number of available locations is $m=n^2$. Therefore,

$E(collision) = n-n^2+n^2(1 − \frac{1}{n^2} )^n$

Maybe this can be simplified, but this is anyways the answer to this question.

To know more about this theorem and it's proof, here is the source.

Here is the link to a very similar and interesting problem discussed on math.exchange.

Comments

But the question is for probability- not expectation..