A hash function collision occurs when two distinct keys map to the same bucket. Which are common resolution strategies?

• A. Chaining
• B. Open addressing with linear probing
• C. Open addressing with double hashing
• D. All of the above

Answer: (D)

When two distinct keys map to the same bucket, a collision occurs and you need a strategy to store both items. One common approach is chaining, where each bucket holds a list (like a linked list) of all keys that hash to that bucket. This keeps insertions simple and works well even as the table fills, since the number of elements grows outside the single bucket’s capacity without affecting other buckets.

Another approach is open addressing with linear probing. If the initial bucket is taken, you inspect the next bucket, then the next, and so on, wrapping around as needed, until you find an empty slot for the new item. This keeps all items in a single array and can be efficient at moderate load factors, though performance degrades as the table fills.

A third common approach is open addressing with double hashing. Here a second hash function determines the step size for probing, so the sequence of slots checked is more spread out. This reduces clustering compared to linear probing and can improve performance at higher load factors.

All of these are established collision-resolution strategies, so selecting any of them is reasonable depending on the situation.