11. Hash Tables (Just give me the equations for these with the right load factor

Question

11. Hash Tables (Just give me the equations for these with the right load factor plugged in.) 11a. Suppose you have a hash table that uses open addressing with linear probing for the next open slot. It is 50 % full. How many slots can we expect to examine in a search for a key? 11b. Suppose you have instead a hash table that uses open addressing with double hashing. It is 50 % full. How many slots can we expect to examine in a search for a key? 11c. Now, consider the hash table with chained hashing. Suppose it?s 50% full. How many slots will you inspect?

Explanation / Answer

For open addressing;

The number of probes to search a key from the hash table is 1/(1-alpha)

where alpha is percentage fraction filled.

Since hash table is filled by 50%, the fraction is 1/2.

Hence number of probes to search a key is = 1/(1-1/2) = 1/(1/2) = 2

----------------------------------------------------------------------------------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.