The GATE Grind

GATE 2022 CS – Question 16

Algorithms · Searching, Sorting and Hashing · 1 mark · Multiple choice

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?

  1. $\frac{m}{n}$
  2. $\frac{n}{m}$
  3. $\frac{2n}{m}$
  4. $\frac{n}{2m}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\frac{n}{m}$

Explanation

Each key lands in any given slot with probability $1/m$ under simple uniform hashing, regardless of which function is used. The expected number per slot is therefore $n/m$.