collision

Two different keys producing the same hash, or the same slot in a hash table.

In more detail

Collisions are unavoidable, since there are more possible keys than slots, so every hash table needs a way to resolve them. Occasional collisions cost little; many keys in one slot turn O(1) lookups into O(n) scans. Unequal objects may share a hash, but equal objects must always share one.

Related terms

Taught in

References