Question 5 ... COMP1927 14s2 Final Exam

A.  (hashing complexity)

O(1)


B.  (chaining)

min = 0 (hash to an empty slot, no key to compare)
max = 4 (hash to slot with length-4 chain, scan to end)


C.  (linear probing)

After
Inserting    [0]  [1]  [2]  [3]  [4]  [5]  [6]
(initial)    --   --   --   --   --   --   --
11           --   --   --   --   11   --   --
21           21   --   --   --   11   --   --
31           21   --   --   31   11   --   --
32           21   --   --   31   11   32   --
12           21   --   --   31   11   32   12
22           21   22   --   31   11   32   12
24           21   22   24   31   11   32   12


D.  (double hashing)

After
Inserting    [0]  [1]  [2]  [3]  [4]  [5]  [6]
(initial)    --   --   --   --   --   --   --
11           --   --   --   --   11   --   --
21           21   --   --   --   11   --   --
31           21   --   --   31   11   --   --
32           21   --   --   31   11   --   32
12           21   --   --   31   11   12   32
22           21   22   --   31   11   12   32
24           21   22   24   31   11   12   32