The GATE Grind

GATE 2024 DA – Question 21

Programming, Data Structures and Algorithms · Stacks, queues, linked lists, trees and hash tables · 1 mark · Multiple choice

Consider performing uniform hashing on an open address hash table with load factor $\alpha = \frac{n}{m} < 1$, where $n$ elements are stored in the table with $m$ slots. The expected number of probes in an unsuccessful search is at most $\frac{1}{1 - \alpha}$. Inserting an element in this hash table requires at most ______ probes, on average.

  1. $\ln\left(\frac{1}{1 - \alpha}\right)$
  2. $\frac{1}{1 - \alpha}$
  3. $\frac{1 + \alpha}{2}$
  4. $\frac{1}{1 + \alpha}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\frac{1}{1 - \alpha}$

Explanation

To insert an element, the table is probed until an empty slot is found, which is the same sequence of probes as an unsuccessful search for that key. So the expected number of probes for an insertion is also at most $\frac{1}{1 - \alpha}$.