Hashing 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 3 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)s (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 Given a set of keys and a hash function, generate by hand a 26 element lookup table g. to create a perfect hash. Also create the final data table. The keys are auto, break, case, const, for, switch, struct, while, static, continue The hash function is: hokey,-( g(first-letter-of key] + glast-letter of key] + length-of-key ) % 10 Hint: Although this assignment is a hand execution, not a program implementation, you may still wish to write some code to help you generate and display the indexes programmatically, so that you can check for collisions more easily. You could also use Excel, your choice Turn in: 1) Paper print out of your look-up table g. similar to that shown below value index char 2) Paper diagram of your final data table, similar to that shown below, but with key values