How do hash tables handle collisions, load factor, and resizing?

Question

Accepted Answer

Two distinct keys can hash to the **same bucket** — a **collision**. Hash tables stay O(1) on average by resolving collisions and **resizing** before buckets get crowded, controlled by the **load factor**.

## Collision resolution

```text
Separate chaining: each bucket holds a list
  [3] -> ("cat",9) -> ("rat",2)   # both hashed to 3

Open addressing: probe to the next free slot
  hash=3 taken -> try 4 -> try 5 ... (linear probing)
```

## Load factor and resizing

```text
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
  -> allocate a bigger array (usually 2x)
  -> REHASH every existing key into new buckets
```

```python
# Conceptual resize
def _resize(self):
    old = self.buckets
    self.buckets = [None] * (len(old) * 2)
    for entry in all_entries(old):
        self._insert(entry.key, entry.value)   # rehash into new array
```

## Complexity

| Operation | Average | Worst |
|---|---|---|
| lookup / insert / delete | O(1) | O(n) |
| single resize | — | O(n) |
| insert (amortized, with resizing) | O(1) | — |

A resize is O(n) but happens rarely, so it **amortizes to O(1)** per insert.

## Trade-offs

- **Chaining:** simple, degrades gracefully, but uses extra pointers and has poor cache locality.
- **Open addressing:** cache-friendly and compact, but sensitive to high load factor and needs careful deletion (tombstones).

## Why it matters

These internals explain *why* hash maps are fast on average yet can spike to O(n) — crucial for performance-sensitive code and adversarial-input (hash-flooding) defenses.

Understanding load factor also explains memory/speed tuning knobs exposed by real libraries.

Operation	Average	Worst
lookup / insert / delete	O(1)	O(n)
single resize	—	O(n)
insert (amortized, with resizing)	O(1)	—