For a hash table implemented using the technique of Linear Probing assume that y

Question

For a hash table implemented using the technique of Linear Probing assume that you have an array size of 7 and a hash function int hash(int key) {return (3 * key % 7);} Suppose that you want to perform the following sequence of operations: insert(4); inset(3); insert(7); insert(11); insert(9); insert(2); insert(7); deleted (9); insert(4); (A) Show in the space above the result of performing these operations on an initially-empty table. Use - 1 as a sentinel for "never used" -2 used but currently empty." (B) Recall that a hash function generally has the form (P * key % M) for suitable primes P and M. What would be the effect on the hash table's performance if P = M? Be specific and five theta (....) cost for looking up an item in such a table. (C) Precisely how many slots in the array do you have to examine in each of the following tests for the hash table you got at the end of (A)? member(9) member(2) member(5) [unsuccessful test]

Explanation / Answer

Given hash table size:7

hash function:3*key%7

insert(4):(3*4)%7=5

insert(3):(3*3)%7=2

insert(7):(3*7)%7=0

insert(11):(11*3)%7=5 slot is already filled with 4 so,we have to search for next empty slot as per linear probing.so,11 inserted at position 6

insert(9):(3*9)%7=6,it get flled at slot 1

insert(2):(6%7)=3,it get filled at slot 3

delete(7) so,we have 0 slot

delete(9).so,we have 2 slot empty as well.

insert(9):available slot 0,so, 9 filled at slot 0

slot number 4 not used,slot number 2 busy lot unadu..

B)if P=M then slot =key,

c)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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