Skip to content
BENIBIX Learn

Hash Collision

Development🧮 Algorithms & Data StructuresData Structures

Also known as Collision (Hashing), Hash Clash, Collision Resolution

Two keys that land in the same slot of a hash table.

Think of it like

It is like two kids given the same coat hook. The school needs a plan, or one coat falls.

Example

The keys "cat" and "act" both hash to slot 3. The table keeps both in a little list at slot 3.

Why it matters

Too many collisions make a fast table slow. Good hash functions spread keys out so most slots hold one item.

Definition

A hash collision happens when two different keys get the same slot from a hash function. There are more possible keys than slots, so this always happens sooner or later. A hash table must handle it. One way is to keep a short list in each slot, called chaining. Another is to try the next free slot, called open addressing.
cat and act both land in slot 3. A short chain keeps both.

Common mistake

Thinking a good hash function never collides. It always can; the table just has to cope.

Key takeaways

  1. 1
    Always possible. More keys than slots.
  2. 2
    Chaining. Keep a list in the slot.
  3. 3
    Open addressing. Try the next free slot.