Imagine that you have a linear probe hashtable, with M=13. Draw the final hashta

Question

Imagine that you have a linear probe hashtable, with M=13. Draw the final hashtable after adding these keys: 13,11,4,0,14,18,43,33. Use the hash function hash(k,i)= (k mod 13 + i) mod13, where i is number of times the algorithm has tried to insert the key. Your drawing should include the main size M array. Do not worry about including the values that would be paired with the keys in a real hashtable.(I am confused what is value of i. Plesae provide detailed explaination/each step since I have answer but want to know how we got it pls)

Explanation / Answer

Linear Probing: In linear probing, we linearly probe for next slot.let hash(x) be the slot index computed using hash function and S be the table size

13

Index 0 1 2 3 4 5 6 7 8 9 10 11 1 Pass(13 mod 13) = 0 13 2 Pass(11 mod 13) = 11 13 11 3 pass (4 mod 13) = 4 13 4 11 4 pass (0 mod 13) = 0 --> (0+1)mod 13= 1 13 0 4 11 5 pass (14 mod 13) = 1--> (1+1),=mod 13 = 2

13

0 14 4 11 6 pass (18 mod 13) = 5 13 0 14 4 18 11 7 pass (43 mod 13)--> (4+1) mod 13 --> (5+1)mod 13 = 6 13 0 14 4 18 43 11 8 pass (33 mod 13) =7 13 0 14 4 18 43 33 11

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---