Which collision resolution strategy uses linked lists at each bucket?

• A. Chaining
• B. Open addressing
• C. Linear probing
• D. Double hashing

Answer: (A)

Separate chaining handles collisions by attaching a linked list to each bucket in the hash table. When multiple keys hash to the same index, they’re stored in that bucket’s list, so a single bucket can hold many entries instead of just one. Insertion adds a node to the list, while searching hashes to the bucket and then traverses the list to find the key. Deletion likewise traverses and relinks as needed. This approach lets the table accommodate more elements without resizing the table itself, since each bucket can grow with a linked list.

In contrast, open addressing resolves collisions by placing the colliding item in another slot within the same table, using probing strategies. Linear probing moves to the next slot, and double hashing uses a second hash function to compute the step size. Neither of these uses a per-bucket linked list, which is why linked lists at each bucket point to separate chaining.