What is a hash collision and two common collision resolution strategies?

• A. Collision occurs when two keys map to different indices; separate chaining and open addressing are common strategies.
• B. Collision occurs when two keys map to the same index; separate chaining and open addressing are common strategies.
• C. A hash collision occurs when a key is not found.
• D. Open addressing is the only collision resolution strategy.

Answer: (B)

A hash collision happens when two different keys end up mapping to the same index in the hash table. This is the situation hash tables must handle because multiple keys sharing one bucket is the normal case as the table fills up or as hash functions distribute keys unevenly.

To deal with collisions, two common strategies are separate chaining and open addressing. Separate chaining keeps a list (or another structure) of all keys that hash to the same index, so the bucket stores multiple entries. When you search, you go to that bucket and scan the list to find the exact key. Open addressing keeps all entries inside the table itself and, if a collision occurs, probes other slots according to a rule (linear probing, quadratic probing, or double hashing) until it finds an empty slot for insertion or the requested key for lookup. Both methods resolve collisions, whereas describing collisions as mapping to different indices is incorrect, and claiming a key not found equals a collision confuses a miss with a collision. It’s also false that open addressing is the only strategy.