Consider a hash table of size 11 with hash function () = (11 + 4) 11. Draw the

table that results after inserting, in the given order, the following values: 65, 13, 49,

27, 89, 32, 46, 73, 33 for each of the three scenarios below:

i.

When collisions are handled by separate chaining;

ii.

When collisions are handled by linear probing;

iii.

When collisions are handled by double hashing using a second hash function

() = ( 9) + 1. Hint, the overall (combined) hash function is () =

( () + () ) 11, where i = 0, 1, 2, 3,

iv.

When collisions are handled by quadratic probing with a quadratic probe

function (, ) = (() + 0.5 + 0.5 2 ) 11 where = 1, 2, 3, .