Consider a hash function that distributes keys uniformly. The hash table size…

The probability that a new key does not collide with any existing key after k keys have been hashed is (19/20)^k, assuming uniform distribution.

Therefore, the probability that the new key collides with at least one existing key is 1 - (19/20)^k.

We want this probability to exceed 0.5:

1 - (19/20)^k > 0.5

Rearranging:

(19/20)^k < 0.5

Take the natural logarithm of both sides:

k * ln(19/20) < ln(0.5)

Since ln(19/20) is negative, divide both sides and reverse the inequality:

k > ln(0.5) / ln(19/20)

Calculate:

ln(0.5) ≈ -0.6931

ln(19/20) ≈ ln(0.95) ≈ -0.0513

k > (-0.6931) / (-0.0513) ≈ 13.5

Therefore, the smallest integer k is 14.

After hashing 14 keys, the probability that a new key collides exceeds 0.5.