Question

Consider performing uniform hashing on an open address hash table with load factor $α = \frac{n}{m}< 1$, where n elements are stored in the table with m slots. The n m 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. $\text{ln}(\frac{1}{1-\alpha})$
• B. $\frac{1}{1-\alpha}$
• C. $1+\frac{\alpha}{2}$
• D. $\frac{1}{1+\alpha}$

Answer 1

Answer: (B)

$\frac{1}{1-\alpha}$

Answer 2

The correct option is (B) : $\frac{1}{1-\alpha}$.