What is the probability of a collision when hashing n keys into a hash table of size m, assuming that the hash function produces a uniform random distribution?

The probability of a collision when hashing n keys into a hash table of size m, assuming that the hash function produces a uniform random distribution, can be calculated using the birthday paradox concept. Here are the steps:

1. First, we need to understand that a collision occurs when two keys are hashed to the same slot in the hash table.

2. The probability of the first two keys colliding is 1/m, because after the first key is hashed, there is 1 slot (out of m) that will result in a collision for the second key.

3. For the third key, there are already 2 occupied slots, so the probability of a collision is 2/m.

4. This pattern continues, with the probability of a collision for the nth key being (n-1)/m.

5. To find the total probability of a collision, we sum up these individual probabilities. This gives us the formula (1/m) * (1 + 2 + 3 + ... + (n-1)).

6. This sum can be simplified using the formula for the sum of an arithmetic series, which is n*(n-1)/2. So, the total probability of a collision is (n*(n-1))/(2m).

7. This formula assumes that n is less than or equal to m. If n is greater than m, then a collision is guaranteed, so the probability is 1.

8. Also, this formula assumes that the hash function produces a uniform random distribution. If it doesn't, then the probability of a collision could be higher.

So, the probability of a collision when hashing n keys into a hash table of size m, assuming that the hash function produces a uniform random distribution, is (n*(n-1))/(2m), if n is less than or equal to m, and 1 if n is greater than m.