# Hash Tables: The Real Cost of a Collision

> Hash tables promise O(1) lookups, and then a benchmark shows them losing to a plain array. The gap between the textbook and reality is collisions, cache misses, and the resize you forgot about.

URL: https://harshith.in/blog/hash-table-collisions/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: algorithms, performance

"Hash tables are O(1)" is true in the same way "the average human has one
testicle" is true. The constant factor and the worst case are where programs
actually live, and both are governed by how you handle collisions — two keys
landing in the same slot.

## Why Collisions Are Inevitable

A hash function maps a huge key space into a small array of buckets. By the
pigeonhole principle, distinct keys *will* share buckets. With even a decent hash,
the birthday paradox means collisions start appearing far earlier than intuition
suggests — you don't need the table to be full.

The fraction of slots used is the **load factor** (`α = entries / buckets`), and
it's the single number that governs collision rate.

## Two Ways to Resolve Them

**Chaining** — each bucket holds a linked list of entries:

```text
   [0] → (key1) → (key4)
   [1] →
   [2] → (key2) → (key7) → (key9)   ← collisions chain here
```

Simple and degrades gracefully, but each chain hop is a pointer chase to a random
address — a likely **cache miss**. A "found in 3 comparisons" lookup can mean
three cache misses, which dwarfs the comparisons.

**Open addressing** — entries live in the array itself; on collision you probe to
the next slot:

```text
   [0][k1][k4][ ][k2][ ][ ]   ← k4 wanted slot 1, probed to slot 2
```

Everything stays in contiguous memory, so probes are cache-friendly. The price:
performance falls off a cliff as the table fills, because probe sequences get
long. Open addressing needs a lower load factor (often kept under ~0.7).

## The Cost You Forgot: Resizing

When the load factor crosses a threshold, the table doubles and **every entry is
rehashed** into the new array — an O(n) operation. It's rare, so amortized cost
stays O(1), but any single insert can stall:

```text
   insert, insert, insert, ... , INSERT(resize: rehash all n) , insert, ...
                                  └─ one slow op hidden in the average
```

For latency-sensitive code, that occasional spike matters. Preallocate with the
expected size to dodge it.

## What Actually Makes Them Fast

- **Keep the load factor sane.** High `α` means long chains or long probes.
- **Mind cache behavior.** Open addressing usually beats chaining in practice
  purely because it stays in contiguous memory.
- **Use a good hash.** A weak hash clusters keys into the same buckets and turns
  your O(1) table into an O(n) linked list — the basis of algorithmic-complexity
  denial-of-service attacks.

## Takeaways

- Collisions are unavoidable; the load factor controls how often they happen.
- Chaining degrades gracefully but pays cache misses; open addressing is
  cache-friendly but needs a lower load factor.
- Resizing rehashes everything — amortized O(1) hides a real per-op spike, so
  preallocate when latency matters.
- A bad hash collapses O(1) into O(n); pick a strong one.