Please Show me how to do this problem. Your Help is greatly appreciated. Conside

Question

Please Show me how to do this problem. Your Help is greatly appreciated.

Consider a hash table with 5 buckets, integer keys, and hash function H(K) = K mod 5. Keys 22,14, 7, 3, 27 are inserted, in that order, using linear probing. Show the contents of the hash table: Suppose all keys are equally likely to be searched for. What is the exact average case number of probes required to perform a successful find in this table? Show your work. Often, data added recently to a data structure is more likely to be searched for than old data. Suppose that true in this case. In particular, suppose that the search probabilities of keys in this table are: What is the exact average case number of probes required to perform a successful find in the table? Show your work.

Explanation / Answer

a.

22mod5=2---in poition 2

14mod5=4---in position 4

7mod5=2 --- in position 3 as position 2 is filled and we are using linear probing so we go to next bucket

3mod5=3--in position 0 as position 3,4 are filled we go to 0

27mod5=2--position 1 as 2,3,4,0 are filled

b.

for 22 -- 1 we search at position 2 as 22mod5=2

for 14--1 we search at position 4 as 14mod5=4

for 7 --2 we search at position 2 as 7mod5=2 but we do not have our value there so then we check at position 3

for 3 --3 we search at position 3 as 3mod5=3 but we do not have our value there so then we check at position 4 and then    at position 0 and we find it there

for 27-5 we search at positions 2,3,4,0 and then finally at 1

average=1+1+2+3+5/5 = 2.4

c.number of search * its probability

1*1/16 + 1*1/16 + 2*1/8 + 3*1/4 + 5*1/2 = 3.625

3 27 22 7 14 0 1 2 3 4

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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