Question 50

Hash function: $h(k) = k \bmod 9$ on 9 slots (0 to 8).

Compute hash slot for each of the 9 keys in order:

• $h(5) = 5 \bmod 9 = 5$
• $h(28) = 28 \bmod 9 = 1$
• $h(19) = 19 \bmod 9 = 1$
• $h(15) = 15 \bmod 9 = 6$
• $h(20) = 20 \bmod 9 = 2$
• $h(33) = 33 \bmod 9 = 6$
• $h(12) = 12 \bmod 9 = 3$
• $h(17) = 17 \bmod 9 = 8$
• $h(10) = 10 \bmod 9 = 1$

Distribution of keys across the 9 slots:

• Slot 0: empty (length 0)
• Slot 1: $\{28, 19, 10\}$ (length 3)
• Slot 2: $\{20\}$ (length 1)
• Slot 3: $\{12\}$ (length 1)
• Slot 4: empty (length 0)
• Slot 5: $\{5\}$ (length 1)
• Slot 6: $\{15, 33\}$ (length 2)
• Slot 7: empty (length 0)
• Slot 8: $\{17\}$ (length 1)

Analyzing chain lengths:

• Maximum chain length: $\max(0, 3, 1, 1, 0, 1, 2, 0, 1) = 3$.
• Minimum chain length: $\min(0, 3, 1, 1, 0, 1, 2, 0, 1) = 0$.
• Average chain length: $\frac{\text{Total keys}}{\text{Total slots}} = \frac{9}{9} = 1$.

Thus, the maximum, minimum, and average chain lengths are 3, 0, and 1.