1. Hash table (20 pts) You have a hash table of size m and two hash functions hl and h2: h1(x)-(sum of the values of all the letters in x) % 1 1 h2(x)-5-(value of the first letter in x) % 5, where the value of a letter is its position in the alphabet (e.g., value(a) 0, value(b) 1, .., valuelz) 25) For each of the following techniques, Linear probing with h as the hash function. Quadratic rehashing with hI as the hash function. Double hashing with hl as 1st hash function and h2 as 2nd hash function. - Separate chaining with hI as the hash function. Draw a picture of the resulting hash table after inserting, in order, the following words: koala, dog, carp, ape, mud, stork, hare, ibex, bat, bird Record the number of collisions for linear probing, quadratic probing, and double hashing. Highlight cells that are looked at when trying to find "bird". a) b) c) 2. Collision avoidance (9 pts) (3 pts) One problem with linear probing is "primary clustering." Please explain what this problem is. (3 pts) Quadratic probing was proposed to overcome the disadvantage of primary clustering. However, it may create a new problem called "secondary clustering." Please explain what this problem is. a) b) c) (3 pts) In double hashing, if we choose the second hash function hash2(x) R-(x mod R) to resolve the collision, why we would like to make R a prime number? 3. Online questions (please logon to Blackboard). (5 pts)