GATE CS 2022 Q6 — Searching, Sorting, Hashing

Under the simple uniform hashing assumption, each key is equally likely to hash to any of the $m$ slots, independent of where other keys have hashed.

Let the total number of keys $n$ be divided into:

• $n_o$ odd keys, which are hashed using $h_1$
• $n_e$ even keys, which are hashed using $h_2$

where $n_o + n_e = n$.

Let $X_j$ be the random variable representing the total number of keys in a specific slot $j$ (where $1 \le j \le m$). We can express $X_j$ as the sum of two components:

where:

• $X_{o, j}$ is the number of odd keys hashing to slot $j$.
• $X_{e, j}$ is the number of even keys hashing to slot $j$.

By the definition of simple uniform hashing:

• Each of the $n_o$ odd keys has a probability of $\frac{1}{m}$ of hashing to slot $j$. Thus, the expected number of odd keys in slot $j$ is: $$E[X_{o, j}] = \frac{n_o}{m}$$
• Each of the $n_e$ even keys has a probability of $\frac{1}{m}$ of hashing to slot $j$. Thus, the expected number of even keys in slot $j$ is: $$E[X_{e, j}] = \frac{n_e}{m}$$

Using the linearity of expectation, the expected total number of keys in slot $j$ is:

Thus, the expected number of keys in any slot is $\frac{n}{m}$.