hash5

6) Hashing (10 marks) For an open-address hash table, double hashing is adopted. Let the table size be 11, we set the two functions as follows: a) h1(k)k mod 11; h2(k)-1+ (k mod 10); The hash function is given by h(k,) (h(h2(k)) mod 11, where i is the probe number. Suppose initially we enter two keys 89, 18 into the hash table, the result is shown in the following: 89 18 Next we enter the following keys into the hash table in sequence: 45, 29, 40, 111,23. Show the final resulting hash table. b) Given an open-address hash table with load factor a N/M1, where N is the number of data entries and M is the table size, give a bound on the expected number of probes in an unsuccessful search. Briefly explain your answer. 6) Hashing (10 marks) For an open-address hash table, double hashing is adopted. Let the table size be 11, we set the two functions as follows: a) h1(k)k mod 11; h2(k)-1+ (k mod 10); The hash function is given by h(k,) (h(h2(k)) mod 11, where i is the probe number. Suppose initially we enter two keys 89, 18 into the hash table, the result is shown in the following: 89 18 Next we enter the following keys into the hash table in sequence: 45, 29, 40, 111,23. Show the final resulting hash table. b) Given an open-address hash table with load factor a N/M1, where N is the number of data entries and M is the table size, give a bound on the expected number of probes in an unsuccessful search. Briefly explain your