Hash Tables: O(1) at the Cost of Order

A hash table maps keys to values via a hash function that turns a key into a table index, giving average O(1) insert, delete, and lookup. The trade: ordering is destroyed — you get direct access instead of sorted traversal. That single trade is why hash tables sit behind symbol tables, caches, dictionaries, and deduplication.

Hash Functions: Keys In, Indices Out

The hash function computes index = hash(key) % capacity. A good hash function is:

• Deterministic — the same key always yields the same index.
• Uniform — keys spread evenly across all buckets.
• Fast — O(1) to compute, so hashing never dominates the lookup.
• Diffusing — keys that differ slightly produce very different hashes.

A bad hash function clusters keys. If hash(key) % 10 uses only the last decimal digit, every key ending in the same digit collides. A slow hash is equally fatal: an O(1) data structure whose hash function takes linear time is an O(n) data structure in disguise.

Collisions: Inevitable, But Manageable

Two distinct keys hashing to the same index is a collision. By the pigeonhole principle, more keys than slots guarantees one. The only design question is how you resolve it — and that choice determines worst-case behavior, memory layout, and cache performance.

Chaining vs Open Addressing

Probe strategies for open addressing:

• Linear probing — try index+1, index+2, … Simple, but primary clustering: runs of filled slots grow, and inserts into the run get progressively slower.
• Quadratic probing — try index+1², index+2², … breaks primary clustering, but with some capacities (e.g. powers of two) it fails to probe every slot.
• Double hashing — a second hash function picks the step size, so even colliding keys diverge immediately. Best distribution; requires the step to be coprime with the table size.

Chaining’s tree upgrade is real-world relevant: Java’s HashMap converts a bucket’s chain to a red-black tree past 8 entries, capping worst case at O(log n) and defusing hash-flooding attacks.

Load Factor and Resizing

The load factor α = entries ÷ buckets measures how full the table is.

• Chaining: α can exceed 1.0; average search cost is O(1 + α).
• Open addressing: performance collapses as α approaches 1 — linear probing degrades past ~0.7.
• Resize: when α crosses a threshold (0.75 is typical), double the capacity and rehash every entry. The copy is O(n), but amortized across the O(n) inserts since the last resize, each insert stays O(1).

Resizing is also the defense against hash flooding: an attacker who controls keys can aim them all at one bucket. Randomizing the hash seed per process makes the attack impossible to target.

Applications

• Caches — memcached, Redis, browser caches: O(1) get/put with O(1) LRU eviction.
• Symbol tables — compilers and interpreters map identifiers to types, addresses, and values.
• Database indexing — hash indexes serve exact-match lookups (WHERE id = 7) but not ranges.
• Counting — frequency histograms and deduplication: map[k] = (map[k] ?? 0) + 1.
• Associative arrays — Python dict, JavaScript Map, and Java HashMap are hash tables underneath.
• Membership — a hash set answers “is x present?” in O(1); see Bloom filters for space-critical variants.

Worked Example: Counting Frequencies

Count character frequencies in a string in one pass — O(n) time, O(k) space for k distinct characters:

map = {}
for ch in "banana":
    map[ch] = (map[ch] ?? 0) + 1
# → { b: 1, a: 3, n: 2 }

Now detect a duplicate with a hash set:

seen = {}
for ch in "abcda":
    if ch in seen: return true   # 'a' repeats
    seen.add(ch)
return false

Both problems collapse to O(n) time and O(k) space because hashing is O(1) per key — the algorithm is dominated by hash lookups, not comparisons. This is the pattern behind every “hash table makes the hard case easy” interview move: an extra O(k) memory buys a linear-time solution.

Practice Trajectory

1. Implement a hash table with separate chaining; force collisions and watch lookups degrade.
2. Reimplement with linear probing and observe primary clustering on a clustered key set.
3. Write a frequency counter and a duplicate detector — both O(n) hash-table solutions.
4. Tune the load factor and resize threshold; measure the resize-cost versus lookup-speed trade-off.
5. Explain why a randomized hash seed defeats hash flooding.

When It’s the Right Tool