Question

The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are inserted into a hash table using the
hash function ℎ(𝑘) = 𝑘 𝑚𝑜𝑑 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 \bmod 9$ for every key and group them by bucket; keys 28, 19 and 10 all map to bucket 1, giving the longest chain with a length of 3.

Answer 1

Correct Answer: 3

We insert the keys \(5, 28, 19, 15, 26, 33, 12, 17, 10\) into a hash table of size 9 using \(h(k) = k \bmod 9\), with collisions resolved by chaining.

Step 1: Compute the hash value for every key.

• \(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(26) = 26 \bmod 9 = 8\)
• \(h(33) = 33 \bmod 9 = 6\)
• \(h(12) = 12 \bmod 9 = 3\)
• \(h(17) = 17 \bmod 9 = 8\)
• \(h(10) = 10 \bmod 9 = 1\)

Step 2: Group keys by bucket, in insertion order.

• Bucket 1: \(28 \to 19 \to 10\) (chain length 3)
• Bucket 3: \(12\) (chain length 1)
• Bucket 5: \(5\) (chain length 1)
• Bucket 6: \(15 \to 33\) (chain length 2)
• Bucket 8: \(26 \to 17\) (chain length 2)

Step 3: Find the maximum chain length. Bucket 1 holds three keys (28, 19, 10), the longest chain among all buckets; every other bucket has at most 2 keys.

Final Answer: The length of the longest chain is \(\boxed{3}\)