GATE CS 2022 Q.16: Hash Tables and Collision Resolution

Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_1$ and $h_2$ . Further suppose our hashing scheme uses $h_1$ for the odd keys and $h_2$ for the even keys. What is the expected number of keys in a slot?

$\frac{m}{n}$

$\frac{n}{m}$

$\frac{2n}{m}$

$\frac{n}{2m}$

Official answer and solution

Official answer: B
From: Official GATE 2022 answer key

Solution

Apply indicator random variables and linearity of expectation under simple uniform hashing.

Let $S_1$ be the set of odd keys and $S_2$ be the set of even keys, with $|S_1| = n_1$ and $|S_2| = n_2$ such that $n_1 + n_2 = n$ .

Under simple uniform hashing:

Each key $k \in S_1$ is hashed by $h_1$ into any slot $j \in \{1, \dots, m\}$ with probability $\frac{1}{m}$ .
Each key $k \in S_2$ is hashed by $h_2$ into any slot $j \in \{1, \dots, m\}$ with probability $\frac{1}{m}$ .

Let $X_j$ be the number of keys hashed into slot $j$ . Defining indicator variables $I_{k,j} = 1$ if key $k$ hashes to slot $j$ and $0$ otherwise:

E[X_j] = \sum_{k \in S_1} E[I_{k,j}] + \sum_{k \in S_2} E[I_{k,j}] = n_1 \left(\frac{1}{m}\right) + n_2 \left(\frac{1}{m}\right) = \frac{n_1 + n_2}{m} = \frac{n}{m}

Thus, regardless of the distribution of odd and even keys, the expected number of keys in any given slot is $\frac{n}{m}$ .

Final answer

Option (B)

Common trap

Dividing by $2m$ believing that two hash functions double the effective table size or halve the expected load.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2022 Computer Science and Information Technology (CS)
Question: 16 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source