Which collision resolution technique involves maintaining a linked list of…

Correct answer: Chaining.

Explanation: Chaining handles hash table collisions by storing all elements that hash to the same index in a secondary data structure at that index, commonly a linked list.

• How it works: Each bucket contains a list. When multiple keys map to the same bucket, they are appended to that bucket's list, so the bucket holds all collided keys.

• Advantages: Insertions and deletions are simple and fast (no need to probe other buckets), and the table can handle load factors greater than 1 by growing lists.

• Comparison with open addressing methods: Methods like linear probing, quadratic probing, and double hashing resolve collisions by searching for another empty slot in the table (probing). They do not maintain per-bucket linked lists.

Complexity notes:

• Average-case search/insert/delete: O(1 + load factor) because operations examine a small number of items in the bucket's list when the load factor is low.

• Worst-case: O(n) if all keys hash to the same bucket (pathological hash function), but a good hash function and resizing keep this unlikely.