Question

The keys \(5, 28, 19, 15, 26, 33, 12, 17, 10\) are inserted into a hash table using the hash function \(h(k) = k \bmod 9\). The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is _____. (answer in integer)

Hint:

Compute k mod 9 for every key and group the keys that land in the same slot; the longest chain is the largest such group.

Answer 1

Correct Answer: 3

Step 1: List the slots available.
Since the hash function is $h(k) = k \bmod 9$, there are exactly $9$ slots, numbered $0$ through $8$. We insert the keys one at a time, in the order given, and drop each one into its slot's chain.

Step 2: Insert the keys in order and track the table.
Insert $5$: $5 \bmod 9 = 5$. Slot 5 now holds $[5]$.
Insert $28$: $28 \bmod 9 = 1$. Slot 1 now holds $[28]$.
Insert $19$: $19 \bmod 9 = 1$. Slot 1 now holds $[28, 19]$.
Insert $15$: $15 \bmod 9 = 6$. Slot 6 now holds $[15]$.
Insert $26$: $26 \bmod 9 = 8$. Slot 8 now holds $[26]$.
Insert $33$: $33 \bmod 9 = 6$. Slot 6 now holds $[15, 33]$.
Insert $12$: $12 \bmod 9 = 3$. Slot 3 now holds $[12]$.
Insert $17$: $17 \bmod 9 = 8$. Slot 8 now holds $[26, 17]$.
Insert $10$: $10 \bmod 9 = 1$. Slot 1 now holds $[28, 19, 10]$.

Step 3: Read off the final table.
Slot 1: $[28, 19, 10]$, length $3$.
Slot 3: $[12]$, length $1$.
Slot 5: $[5]$, length $1$.
Slot 6: $[15, 33]$, length $2$.
Slot 8: $[26, 17]$, length $2$.
All other slots, 0, 2, 4, 7, stay empty.

Step 4: Spot the longest chain.
Slot 1 has grown the longest, holding three keys, more than any other slot.
\[ \boxed{3} \]