GATE 2022 CS Q.16: solution and answer

Official answer: BSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

1. Let the n keys be split into two disjoint groups by parity: n/2 keys hashed via h1 (a simple uniform hash function into m slots) and n/2 keys hashed via h2 (also simple uniform into the same m slots).

2. By definition of a simple uniform hash function, each key it processes lands in any fixed slot with probability 1/m, independently of the other keys in its own group.

3. Fix any one slot. For the h1-group: the expected number of its keys landing in this slot is $\frac{n}{2}\times \frac{1}{m}=\frac{n}{2m}$, since each of the n/2 keys contributes probability 1/m via the indicator-expectation argument (linearity of expectation over indicator variables).

4. Similarly, for the h2-group: the expected number of its keys landing in this same slot is also $\frac{n}{2}\times \frac{1}{m}=\frac{n}{2m}$.

5. By linearity of expectation, the total expected number of keys (from both groups combined) landing in the fixed slot is the sum of the two group expectations: $\frac{n}{2m}+\frac{n}{2m}=\frac{n}{m}$.

6. This is exactly the same result as using a single simple uniform hash function on all n keys directly ($n\times \frac{1}{m}=\frac{n}{m}$) — splitting the keys across two independent uniform hash functions by any fixed partition does not change the expected per-slot load, because linearity of expectation only requires that each individual key be uniformly distributed across slots, not that all keys share one hash function.

7. Hence the expected number of keys in a slot is $\frac{n}{m}$, which is option (B).