What is a collision in a hash table? Why are they inevitable?

A collision is a situation where two different keys produce the same hash index, that is, they land in the same slot (bucket) of a hash table.

Example:

Both keys will be written to bucket #3, this is a collision.

Why they are inevitable:

• A hash table has a finite number of slots (for example, 1000),
• while the number of possible keys is nearly infinite (strings, numbers, objects, and so on),
• so, by the pigeonhole principle, different keys will inevitably end up with the same hash.

Important: Collisions are a normal occurrence, they cannot be fully eliminated. What matters is being able to handle them efficiently (through chaining or open addressing), so that with a large number of elements the table still keeps access speed close to O(1).