What happens when a collision occurs in a hash table?

When a collision occurs in a hash table, it indicates that two different keys hash to the same index in the underlying array. To properly handle this situation, a collision resolution method is applied. This is essential because the integrity of the hash table must be maintained, ensuring that all key-value pairs are accessible.

Common methods for resolving collisions include:

1. Chaining: This allows multiple key-value pairs to be stored at the same index using a linked list or another data structure. If a collision occurs, the new key-value pair is simply added to the list at that index.

2. Open Addressing: This technique involves finding another empty slot within the hash table based on a probing sequence when a collision occurs. Techniques such as linear probing, quadratic probing, or double hashing can be used to find the next available slot.

By implementing one of these resolution strategies, the hash table can effectively manage collisions while still maintaining fast access to stored elements. Therefore, applying a method to resolve the collision is the correct and essential response when a collision occurs in a hash table.