Consider performing uniform hashing on an open address hash table with load…
2024
Consider performing uniform hashing on an open address hash table with load factor \(\alpha = \frac{n}{m} < 1 \), where 𝑛 elements are stored in the table with 𝑚 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.
- A.
\(\ln\left(\frac{1}{1 - \alpha}\right)\) - B.
\(\frac{1}{1 - \alpha}\) - C.
\(1 + \frac{\alpha}{2}\) - D.
\(\frac{1}{1 + \alpha}\)
Attempted by 208 students.
Show answer & explanation
Correct answer: B
Key idea: an insertion probes until it finds an empty slot; each probe finds an empty slot with probability 1 - α.
Step 1: On any probe, the probability the probed slot is occupied is α, so the probability it is empty is 1 - α.
Step 2: Probing continues independently until the first empty slot is found, so the number of probes follows a geometric distribution with success probability 1 - α and mean 1/(1 - α).
Therefore the expected number of probes required to insert an element is 1/(1 - α).