Hash Tables Aren't Magic

Every data structures textbook says hash tables are O(1). Every engineer who has profiled a hot hash map knows that O(1) is a lie told with constants. A hash table lookup can cost 50 nanoseconds or 500 — and the difference is not the hash function, not the collision count, but the cache. The constant factor in O(1) is where hash tables live or die, and understanding it separates someone who uses hash tables from someone who engineers them.

The three operations, decomposed

A hash table lookup is actually three operations in sequence:

1. Hash — compute the hash code from the key.
2. Index — map the hash to a bucket index (modulo the table size).
3. Probe — look at the bucket, handle collisions, find the key.

Each operation has its own cost model:

hash(key)           → O(1) but depends on key size and hash quality
index % table_size  → O(1), one division instruction
probe(buckets[i])   → O(1) average, O(n) worst case, BUT cache behavior varies wildly

The bottleneck is almost always the probe. Not because of collisions — modern hash functions distribute keys well — but because of where the probe touches memory.

The load factor: the only knob that matters

The load factor α = n/m (elements / buckets) is the single most important parameter of any hash table:

For separate chaining (linked lists per bucket), the average probe length is roughly 1 + α/2. At α = 0.75, you average 1.375 probes. At α = 0.9, you average 1.45. The degradation is gentle.

For open addressing (all entries in the array), the average probe length is roughly 1/(1 - α). At α = 0.75, you average 4 probes. At α = 0.9, you average 10. The degradation is exponential.

This is why Java's HashMap resizes at α = 0.75 and Python's dict resizes at 2/3. The threshold is chosen to keep probe lengths short — not for asymptotic reasons, but for cache reasons.

Collision strategies and their cache behavior

Separate chaining (linked lists)

Each bucket points to a linked list of entries. Collisions append to the list.

bucket 0: → [keyA] → [keyD] → null
bucket 1: → [keyB] → null
bucket 2: → [keyC] → [keyE] → [keyF] → null

The average case is fine. The worst case is when many keys hash to the same bucket — the list grows long, and traversal is sequential. Linked list nodes are scattered across the heap, so every pointer chase is a cache miss.

Java 8+ improved this by converting linked lists to balanced trees when a bucket exceeds 8 entries. Tree traversal is O(log n) instead of O(n), and the tree nodes are allocated contiguously (in modern JVMs with escape analysis), improving cache behavior.

Open addressing (linear probing)

All entries live in the array itself. When a collision occurs, the next bucket is probed sequentially:

hash("keyA") = 5   → table[5] = keyA
hash("keyB") = 5   → table[5] occupied → table[6] = keyB
hash("keyC") = 5   → table[5,6] occupied → table[7] = keyC

The advantage: no pointer chasing. The probe accesses adjacent array elements, which hit the same cache line (typically 64 bytes = 8 pointers). Linear probing with a good hash function achieves cache-line locality — the dominant factor in real-world performance.

The disadvantage: clustering. Consecutive occupied buckets form clusters, and new insertions into a cluster extend it, creating longer probes. The "birthday paradox" applies: with a table of size m and n entries, the probability of at least one collision is 1 - e^(-n²/2m). Clusters grow faster than the load factor alone suggests.

Robin Hood hashing mitigates this by stealing from the rich: during insertion, if the new element's probe distance is longer than the existing element's, they swap. Every element ends up at approximately equal probe distance from its ideal bucket, reducing variance.

Cuckoo hashing

Two (or more) hash tables with different hash functions. A key is always in one of two buckets — lookup checks both. If both are occupied by other keys, the displaced key kicks the existing key to its alternate position, potentially triggering a chain of displacements.

The advantage: worst-case O(1) lookup. You always check exactly two locations. The disadvantage: insertions can cascade, and the table may need to be rebuilt when no empty slot is found.

The real cost: cache misses

A modern CPU can do a hash computation in ~5 nanoseconds. But a cache miss — where the bucket is not in L1, L2, or L3 cache — costs 50–100 nanoseconds. The probe is O(1), but the memory access is not.

operation           L1 hit     L2 hit     L3 hit     main memory
hash computation    1 ns       1 ns       1 ns       1 ns
pointer chase       1 ns       4 ns       12 ns      50–100 ns
array index         1 ns       1 ns       1 ns       50–100 ns

This is why open addressing with linear probing beats separate chaining in practice: linear probing touches adjacent memory, which is likely in the same cache line. Linked list traversal touches arbitrary heap locations, which are likely in different cache lines.

The data is unambiguous: for small tables (< 1000 entries), the difference is negligible. For large tables (> 100,000 entries), cache behavior dominates everything else. The "O(1) hash table" on a million entries is either 10 ns (cache-friendly) or 200 ns (cache-hostile), and no amount of algorithmic cleverness closes that gap without addressing the memory hierarchy.

Hash functions: good enough is good enough

The hash function's job is to distribute keys uniformly across the table. A perfect hash function (no collisions) exists for known key sets but is impractical for dynamic tables. The practical requirement is uniform distribution — each bucket is equally likely to receive any key.

For small keys (integers, short strings), the cost of the hash function is negligible compared to the probe. murmurhash3 processes 4 bytes per cycle on modern CPUs. For large keys (long strings, objects), the hash function cost is amortized by caching the hash code in the object header — most runtimes do this automatically.

The quality of the hash function matters most for adversarial inputs. If an attacker can choose keys that all hash to the same bucket, they can degrade your O(1) lookup to O(n). This is called a hash denial-of-service (HashDoS) attack. The defense is randomized hash functions (Python, Ruby, Java 8+ all use per-process random seeds).

What this means for your code

1. Hash tables are not O(1) — they are O(cache miss). The constant factor is dominated by the memory hierarchy, not the algorithm. Design for cache, not for theory.

2. Resize aggressively. A hash table at α = 0.5 uses 2× memory but probes half as long. Memory is cheap; latency is expensive.

3. Prefer open addressing for small keys. Linear probing with a good hash function achieves near-optimal cache behavior. Separate chaining is only better for large entries or unknown load factors.

4. Cache the hash code. If your keys are large, store the hash code in the key object to avoid recomputing it on every probe.

5. Watch for clustering. If your workload has keys with patterns (sequential integers, similar strings), linear probing degrades. Use a secondary hash (Robin Hood, cuckoo) or a Fibonacci hash to break the pattern.