Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5?

To answer this question, we need to understand the concept of the Birthday Paradox, which is a probability theory. It states that the probability of at least two people sharing a birthday is more than 50% even in a small group of 23 people. This is because the number of possible pairs is not linear, but quadratic.

In the context of a hash table, the Birthday Paradox applies to hash collisions. A hash collision occurs when two different keys hash to the same index in an array.

Here's how we can calculate it:

1. The hash table size is 20, so there are 20 different "slots" a key can hash to.

2. When the first key is hashed, there are no existing keys, so the probability of collision is 0.

3. When the second key is hashed, there is 1 existing key, so the probability of collision is 1/20.

4. For the third key, the probability of collision is 2/20, and so on.

5. We want to find out after how many keys the probability of collision exceeds 0.5. This means we need to solve for n in the equation n/20 > 0.5.

Solving for n gives us n > 10. However, since we can't hash a fraction of a key, we round up to the nearest whole number.

So, after hashing 11 keys, the probability that any new key hashed collides with an existing one will exceed 0.5.