GATE 2024 DA – Question 21
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.
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}$.
More Stacks, queues, linked lists, trees and hash tables questions
- GATE 2024 DA Q28
- GATE 2024 DA Q32
- GATE 2024 DA Q52
- GATE 2026 DA Q25
- GATE 2025 DA Q18
- GATE 2025 DA Q64
All Stacks, queues, linked lists, trees and hash tables questions →