If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n ≤ m, the expected number of…

Explanation

Let Xᵢ = 1 if key x collides with the i-th other key, else 0. For a universal hash family, a given pair collides with probability 1/m, so E(Xᵢ) = 1/m. Summing over the other (n – 1) keys, the expected number of collisions involving x is (n – 1)/m. Since n ≤ m, this is less than 1.