What is a key difference between chaining and open addressing in hash tables?

• A. Open addressing stores multiple items per bucket via linked lists.
• B. Chaining probes for the next available slot within the table.
• C. Chaining stores multiple items at each bucket via linked lists; open addressing probes for the next available slot within the table.
• D. Open addressing uses separate chaining.

Answer: (C)

Collision resolution in hash tables. Chaining stores multiple items at the same bucket by keeping a linked list (or another collection) of entries attached to that bucket, so many keys can hash to the same bucket. Open addressing stores only one item per bucket and resolves collisions by probing the table to find the next available slot, using a probe sequence. The correct description is that chaining uses linked lists at each bucket to hold multiple items, while open addressing probes for the next open slot within the table. The other statements mix up the methods: open addressing isn’t about per-bucket linked lists, chaining doesn’t involve probing to other slots, and open addressing doesn’t use separate chaining.