Hash Tables: O(1) Lookup, Collisions & Load Factor

Q: How are collisions handled?

Two main strategies. Chaining stores a small list (or, for long chains, a tree) at each bucket, so colliding keys are appended there. Open addressing keeps everything in the array and, on collision, probes for the next available slot (linear, quadratic, or double hashing). Chaining is simpler and degrades gracefully; open addressing is more memory- and cache-efficient but more sensitive to high load factors. Both keep operations near O(1) when the table isn't too full.

Hash Tables

A hash table is the data structure behind dictionaries, maps, sets, and caches — and it's arguably the most important one in everyday programming. It stores key-value pairs and gives you O(1) average insert, lookup, and delete by hashing a key to compute where it lives, instead of searching. When you write dict[key] in Python or map.get(key) in Java, a hash table is doing the work.

The magic is the hash function: it turns a key into an array index in constant time, so the table jumps straight to the right spot rather than scanning. The complications — collisions, load factor, worst-case behavior — are all about keeping that jump fast and correct as the table fills up.

TL;DR

Stores key→value pairs with O(1) average insert/lookup/delete.
A hash function maps keys to buckets (array slots).
Collisions (two keys → same bucket) are handled by chaining or open addressing.
Resizes when the load factor gets high; worst case is O(n) under bad hashing.

Quick Example

In most languages a hash table is the built-in dictionary/map:

How It Works

Hash the key — a hash function turns the key into a number.
Map to a bucket — reduce that number to an index in the backing array (e.g. hash % capacity).
Store/retrieve at that bucket.

Because steps 1–3 are constant time, lookups don't depend on how many items are stored — that's the O(1) average.

Collisions

Two different keys can hash to the same bucket — a collision. Tables handle this with:

Chaining — each bucket holds a small list (or tree) of entries; collisions append to it. Simple and common.
Open addressing — on collision, probe for the next free slot (linear/quadratic probing). More cache-friendly, but sensitive to load.

With a good hash function and reasonable load, collisions are rare and chains stay tiny, preserving O(1).

Load Factor & Resizing

The load factor is items ÷ buckets. As it rises, collisions increase and performance degrades, so hash tables resize (typically double capacity and rehash everything) when the load factor crosses a threshold (often ~0.7). Resizing is O(n), but it happens rarely, so insertion stays O(1) amortized (see Big-O).

Worst Case & Security

If many keys collide into one bucket — a poor hash function, or adversarial input crafted to collide — operations degrade to O(n) as the table effectively becomes a linked list. This enables hash-collision denial-of-service attacks. Modern languages mitigate it with randomized hashing (hash seeds) and by switching long chains to trees.

⚠️ Keys must be hashable and immutable — mutating a key after insertion changes its hash, and the table can no longer find it.

Best Practices

Use your language's built-in dict/map/set — they're well-optimized.
Use immutable, hashable keys (strings, numbers, tuples) — never mutate a key in place.
Reach for a set for membership/dedup, a dict for key→value.
Pre-size the table if you know the count, to avoid repeated resizing.
Remember there's no order — use an ordered structure (or a sorted view) if you need it.

Common Mistakes

Linear scanning instead of a hash lookup

Using a mutable object as a key

FAQ

Why are hash tables O(1) on average but O(n) in the worst case?

On average, a good hash function spreads keys evenly across buckets, so each lookup touches only a couple of entries regardless of table size — O(1). The O(n) worst case happens when many keys collide into one bucket (a bad hash function or maliciously crafted inputs), turning that bucket into a linear scan. In practice, quality hash functions and resizing keep collisions rare, so you rely on the average case while staying aware the worst case exists — especially for adversarial input.

What is a load factor and why does it trigger resizing?

The load factor is the ratio of stored items to available buckets. As it climbs, more keys share buckets, collisions rise, and the O(1) average degrades. To prevent this, hash tables resize — usually doubling the bucket array and rehashing all entries — when the load factor exceeds a threshold (commonly around 0.7). Resizing is O(n), but because it happens infrequently (capacity doubles each time), the amortized cost of insertion remains O(1).

How are collisions handled?

Two main strategies. Chaining stores a small list (or, for long chains, a tree) at each bucket, so colliding keys are appended there. Open addressing keeps everything in the array and, on collision, probes for the next available slot (linear, quadratic, or double hashing). Chaining is simpler and degrades gracefully; open addressing is more memory- and cache-efficient but more sensitive to high load factors. Both keep operations near O(1) when the table isn't too full.

Why must hash table keys be immutable?

A key's bucket is determined by its hash, computed when it's inserted. If you mutate the key afterward, its hash changes, but the entry stays in the old bucket — so future lookups compute the new hash, look in the new bucket, and fail to find it. To avoid this, languages require keys to be hashable and effectively immutable (strings, numbers, tuples in Python; objects with stable hashCode/equals in Java). Use immutable keys, or a stable identifier, as the key.