We are performing the following operations on a hash set implemented using open

Question

We are performing the following operations on a hash set implemented using open addressing which follows the linear probing collision resolution scheme. The initial capacity is 8. The table automatically doubles and elements are rehashed when an insert would cause the load factor to be greater than 0.5 (equal to 0.5 does not trigger a rehash). When a rehash is triggered, all the existing elements are rehashed into the new array in the order they are encountered when iterating over the array. Then the element that triggered the rehashing is inserted. Show the state of the array right before resizing and the final resized state after rehashing. Elements that are in the array but are deleted should be shown on the array as crossed out (legibly so). The hash function is h = val % arrSize. + == insert, - == delete 22, 12, 20, 13, -22, -20, 32, 12, 14, 13, 16, 29, -32

Explanation / Answer

Initial array with size = 8

Here load factor is 0.5 which means that when the array is half full and when the next element comes in, rehashing happens.

Insert 22: hash = 22%8 = 6

Insert 12:  hash = 12%8 = 4

Insert 20:  hash = 20%8 = 4, collision occurs. Insert at next free slot

Insert 13:  hash = 13%8 = 5, collision occurs. Insert at next free slot

delete 22:  hash = 22%8 = 6.

delete 20:  hash = 20%8 = 4. If value is not found, probe till you find it.

insert 32:  hash = 32%8 = 0.

insert 12:  hash = 12%8 = 4.

insert 14:  hash = 14%8 = 6.

Rehashing should happen here since the the table is already half full and another insert operation has come up.

Creating a table of size 16 (double 8) .

Inserting all the elements in the new array starting from the first index.

Insert 32, 12, 12, 13 , 14

hash = val % 16

insert 13:  hash = 13%16 = 13

insert 16:  hash = 16%16 = 0.

insert 29:  hash = 29%16 = 13.

delete 32:

So in the first array values were => 32, --, --, --, 12, 12, --, 13

In the next array values were => --,13, 16, 29, --, --, --, --, --, --, --, --, 12, 12, 13, 14

0 1 2 3 4 5 6 7 22

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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