1. (20 points) (a) Fill in the contents of the hash table below after inserting

Question

1. (20 points) (a) Fill in the contents of the hash table below after inserting the items shown. To insert the item k, use the hash function k mod TableSize and resolve collisions with quadratic probing Insert: 13, 44, 103, 113,2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 78 9 113 13 44 2 103 (b) We now consider looking up some items that are not in the table after doing the insertions above. For each, give the list of table locations that are looked at in order before determining that the item is not present. Include all the table locations examined, whether or not they contain an item. Note: these items are only being looked up, not inserted (1) 57 (i) 42 ii. 2 3, 6, 1 (c) Give the load factor for the hash table. (c) =0.5 (d) Is this sentence True or False? Justify For quadratic probing if the table is half empty and the table size is prime, then we are always guaranteed to be able to insert a new element True by Theoremm

Explanation / Answer

Hash Table :

TABLE_SIZE = 10

In Quadratic Hashing ,

H(x) = [ h(x) + f(i) ] mod TABLE_SIZE

whare , h(x) = x mod TABLE_SIZE

f(i) = i^2 ................... i = 0,1,2,..

Insert (13 ) :

H(13) = [ ( 13 mod 10 ) + 0] mod 10 = 3 mod 10 = 3

Insert (44 ) :

H(44) = [ ( 44 mod 10 ) + 0] mod 10 = 4 mod 10 = 4

Insert (103 ) :

H(103) = [ ( 103 mod 10 ) + 0] mod 10 = 3 mod 10 = 3 ...... with i=0 -> collisiion

H(103) = [ ( 103 mod 10 ) + 1^2] mod 10 = 4 mod 10 = 4 ...... with i=1 -> collisiion

H(103) = [ ( 103 mod 10 ) + 2^2] mod 10 = 7 mod 10 = 7 ...... with i=2 -> NO collisiion

Insert (113 ) :

H(113) = [ ( 113 mod 10 ) + 0] mod 10 = 3 mod 10 = 3 ...... with i=0 -> collisiion

H(113) = [ ( 113 mod 10 ) + 1^2] mod 10 = 4 mod 10 = 4 ...... with i=1 -> collisiion

H(113) = [ ( 113 mod 10 ) + 2^2] mod 10 = 7 mod 10 = 7 ...... with i=2 -> collisiion

H(113) = [ ( 113 mod 10 ) + 3^2] mod 10 = 12 mod 10 = 2 ...... with i=3 -> NO collisiion

Insert (2 ) :

H(2) = [ ( 2 mod 10 ) + 0] mod 10 = 2 mod 10 = 2 ...... with i=0 -> collisiion

H(2) = [ ( 2 mod 10 ) + 1^2] mod 10 = 3 mod 10 = 3 ...... with i=1 -> collisiion

H(2) = [ ( 2 mod 10 ) + 2^2] mod 10 = 6 mod 10 = 6 ...... with i=1 -> NO collisiion

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

b) To find the list of locations looked we can use the same formulla

1) 57

Insert (57) :

H(57) = [ ( 57 mod 10 ) + 0] mod 10 = 7 mod 10 = 7 ...... with i=0 -> collisiion -----> location Looked = 7 th

H(2) = [ ( 57 mod 10 ) + 1^2] mod 10 = 8 mod 10 = 8 ...... with i=1 -> NO collisiion   -----> location Looked = 8 th

2) 42

Insert (42) :

H(42) = [ ( 42 mod 10 ) + 0] mod 10 = 2 mod 10 = 2 ...... with i=0 -> collisiion -----> location Looked = 2 th

H(42) = [ ( 42 mod 10 ) + 1^2] mod 10 = 3 mod 10 = 3 ...... with i=1 -> collisiion ----> location Looked = 3 th

H(42) = [ ( 42 mod 10 ) + 2^2] mod 10 = 3 mod 10 = 6 ...... with i=2 -> collisiion ----> location Looked = 6 th

H(42) = [ ( 42 mod 10 ) + 3^2] mod 10 = 11 mod 10 = 1 ...... with i=3 ->NO collisiion ----> location Looked = 1 st

0 1 2 113 3 13 4 44 5 6 6 7 103 8 9

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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