Consider a hash table of size 11 with hash function h(x) = x mod 11. Draw...

Transcribed Image Text:

Consider a hash table of size 11 with hash function h(x) = x mod 11. Draw the table that results after inserting, in the given order, the following values: 76, 67, 92, 51, 87, 80, 108, 95, 91 for each of the three scenarios below: a) When collisions are handled by separate chaining; b) When collisions are handled by linear probing; (5 marks) (5 marks) c) When collisions are handled by double hashing using a second hash function h'(x) = (x mod 10) + 1. Hint, the overall (combined) hash function is H(x) = (h(x) + i x h'(x)) mod 11, where i = 0, 1, 2, 3, ... (5 marks) d) When collisions are handled by quadratic probing with a quadratic probe function h'(x, i) = (h(x) + 0.5 i + 0.5 i²) mod 11 where i = 1, 2, 3, .... (5 marks) Consider a hash table of size 11 with hash function h(x) = x mod 11. Draw the table that results after inserting, in the given order, the following values: 76, 67, 92, 51, 87, 80, 108, 95, 91 for each of the three scenarios below: a) When collisions are handled by separate chaining; b) When collisions are handled by linear probing; (5 marks) (5 marks) c) When collisions are handled by double hashing using a second hash function h'(x) = (x mod 10) + 1. Hint, the overall (combined) hash function is H(x) = (h(x) + i x h'(x)) mod 11, where i = 0, 1, 2, 3, ... (5 marks) d) When collisions are handled by quadratic probing with a quadratic probe function h'(x, i) = (h(x) + 0.5 i + 0.5 i²) mod 11 where i = 1, 2, 3, .... (5 marks)