DATA STRUCTURE

PART 1:

Hashing with Collision Resolution Use the hash function h(key) = key % 10 to insert the following sequence of keys into the following hash table. 22, 3, 12, 1, 18, 36, 33, 9 0 1 2 3 4 5 6 7 8 9 Use the following methods:

a) Chaining (link colliding nodes onto root nodes)

b) Linear rehashing (step by 1)

c) Generalized Linear rehashing (step by 4 with roll-around)

d) Double hashing with h2(key) = (key % 3) + 1

You MUST show all your work.

Turn in: Computer drawn paper diagrams for each of the above methods. Indicate the final state of the hash table for each hashing method. Draw arrows to show collision resolutions.