Hashing

Question

Consider an open address hash table with uniform hashing. Out of 10 locations, 8 are occupied. What are the expected number of probes in an unsuccessful and successful search respectively?

Comments

for successful search $\frac{2}{10}$

unsuccessful search $\frac{8}{10}$

---

unsuccessful searches = 5

successful searches = 2 (approx)

Answer 1

10/8 ln 5 and 5 for successful and unsuccessful search respectively.

If X is load factor.

Successful search = $(1/X) log (1/(1-x))$

Unsuccessful search = $1/(1-x)$