How do hash tables handle collisions? (chaining vs open addressing)

Deep dive

A hash table maps keys to buckets using hash(key) mod capacity. Collisions are normal: different keys can map to the same bucket.

Two major strategies:

1) Chaining

• Each bucket holds a small collection (linked list or sometimes a tree) of entries.
• Performance stays reasonable even at higher load factors, but pointer chasing can hurt cache locality.

2) Open addressing

• All entries live inside the main array.
• On collision you probe other slots (linear / quadratic / double hashing).
• Very cache-friendly, but performance drops quickly when the table gets too full, and deletions require tombstones.

Examples

Chaining insert(key, value):
  i = hash(key) % m
  bucket[i].append((key, value))

Linear probing insert:
  i = hash(key) % m
  while table[i] occupied and table[i].key != key:
    i = (i + 1) % m
  table[i] = (key, value)

What matters in practice

• Load factor and resize policy (bigger tables => fewer collisions).
• Hash quality (bad hashes create clusters and worst cases).
• For open addressing: how you handle delete (tombstones) and clustering.

Common pitfalls

• Using mutable keys (hash/equality changes after insertion).