Skip to main content

Hashing as a Randomized Model: Expected (O(1)) and When It Fails

What This Concept Is​

A hash table stores (key, value) pairs in an array of m buckets using a hash function h that maps each key to a bucket index (h(\text{key}) \in [0, m-1]).

The advertised performance is:

  • search, insert, delete: expected (O(1))
  • all three become (O(n)) in the worst case if all keys collide

The expected bound rests on a modeling assumption usually called simple uniform hashing: each key is equally likely to hash to any bucket, independently of other keys. Real hash functions approximate this by spraying bits, but the guarantee depends on the keys not being adversarially chosen against the function.

In short: hashing is a randomized algorithm whose runtime depends on a probability model of the hash-key interaction. This is why the hash table is the canonical example, along with randomized quicksort, of "expected-time analysis with indicator random variables" in CLRS.

Distinguish three flavors of hash to avoid later confusion:

  • Non-cryptographic hash (FNV, xxHash, SipHash, MurmurHash) -- fast, good distribution, not collision-resistant. Use for hash tables.
  • Universal hash family ((h(x) = ((ax + b) \bmod p) \bmod m)) -- parameterized; picking (a, b) at random gives provable collision probability (\leq 1/m). Use when you need provable expected bounds without assuming uniform keys (see concept 13).
  • Cryptographic hash (SHA-256, BLAKE3) -- collision-resistant, preimage-resistant, slow. Use for fingerprinting, signatures, content addressing -- never for hash-table buckets.

The worst-case bound for lookup is tied to the maximum bucket size. Under simple uniform hashing with (n = m), the expected max bucket size is (\Theta(\log n / \log \log n)) -- this is the "balls in bins" theorem, and it is why Java 8 tree-ified hash buckets exceeding size 8.

Why It Matters Here​

Hash tables are the workhorse "dictionary" in practical programming -- dict in Python, Map in JavaScript, HashMap in Java, std::unordered_map in C++, HashMap in Rust. Most systems code uses them without thinking.

Treating them as a randomized algorithm, rather than a magical (O(1)) box, earns you:

  • an explanation of expected (O(1)) in terms of the linearity-of-expectation arguments from probability
  • a correct picture of when hash tables degrade (bad hash function, adversarial input, high load factor)
  • an honest comparison against balanced trees (which give (O(\log n)) without requiring probabilistic assumptions)
  • a language to reason about HashDoS attacks, cache-friendly alternatives (SwissTable, F14), and why hashmap.get() is fast on average but slow on p99.9

Real systems fall back from hash tables to BST-based structures exactly when the probabilistic assumption fails -- for example, Java 8 switched HashMap buckets to red-black trees under high collision load, and Python's dict randomizes the hash seed at interpreter startup.

Concrete Examples​

Example 1 -- expected load via linearity of expectation. Insert 100 keys into a hash table with (m = 128) buckets using a hash function that spreads keys uniformly.

Let (X_j) be the indicator that bucket (j) is non-empty. By linearity of expectation:

[ \mathbb{E}[\text{non-empty buckets}] = \sum_j \mathbb{P}(\text{bucket } j \text{ is hit at least once}) = m \left(1 - \left(1 - \tfrac{1}{m}\right)^n\right) \approx 128 \cdot (1 - (127/128)^{100}) \approx 128 \cdot 0.544 \approx 69.6. ]

Expected load (average chain length) is (n / m = 100/128 \approx 0.78). Expected cost of a lookup is therefore roughly (1 + 0.78 \approx 1.78) probes, i.e. (O(1)).

If instead an adversary gave us 100 keys that all hash to bucket 0, lookup degrades to (O(n)). The mathematics did not lie -- the keys stopped satisfying uniformity.

Complexity derivation -- expected lookup cost under chaining. For (n) keys in (m) buckets, the expected number of keys colliding into the same bucket as a query (q) is [ \mathbb{E}[|\text{bucket}(h(q))|] = \sum_{i=1}^{n} \Pr[h(k_i) = h(q)] = n \cdot \tfrac{1}{m} = \alpha, ] the load factor. Expected lookup cost is therefore (1 + \alpha) -- constant when (\alpha = O(1)). This is not a statement about worst cases; it is the expectation over the randomness in the hash function (universal hashing, concept 13) or the keys (simple uniform hashing). A single lookup can still be slow; the p99 tail is bounded separately by the max-load bound (\Theta(\log n / \log \log n)).

Example 2 -- the birthday paradox applied to hash tables. With (m = 10^6) buckets and uniformly random hashing, how many inserts before we expect the first collision?

By the birthday paradox, the first collision occurs at roughly (n = \sqrt{\pi m / 2} \approx 1253) keys -- far earlier than intuition suggests. This is why hash-table implementations allow collisions rather than trying to avoid them; avoidance would require (m \gg n^2), which is wasteful. It is also why 64-bit hash codes are generally safe for use as identity keys (collision probability (\sim 10^{-10}) at (n = 10^5)) and 32-bit hash codes are not.

Common Confusion / Misconceptions​

"Expected (O(1)) is a property of the algorithm." It is actually a property of the algorithm plus an assumption about how keys interact with the hash function. Three failures ruin the assumption:

  • adversarial input against a known hash (e.g., HTTP parameter flooding attacks against hash-map web frameworks -- the 2011 "HashDoS" wave against PHP, Java, Python, Ruby)
  • non-uniform real-world keys passed through a bad hash function (e.g., using id(x) % m where id has pattern)
  • high load factor -- once (n) approaches (m), collisions pile up even for good hashes

"Hash tables are always faster than trees." They are faster only for exact-match queries. Trees win for ordered iteration, range queries, and predictable worst case. They also win for small (n) where cache dominates -- std::map beats std::unordered_map for (n \leq \sim 100) on most CPUs.

"Iteration order is stable or insertion-ordered." In most modern hash-table implementations, insertion order and iteration order are unrelated. Python 3.7+ guarantees insertion order by contract (CPython implementation detail promoted to language spec); most others do not. Do not write tests or business logic that depends on iteration order unless your language spec guarantees it.

"(O(1)) expected means constant (p99) latency." It does not. Expected cost averages over all operations; any single lookup can be slow because of a long chain, a resize pause, or a rehash. Production systems that need predictable (p99) use open addressing with bounded probe sequences, incremental resizing (Go's map does this), or fall back to BST under load (Java's HashMap post-8).

How To Use It​

When using a hash table:

  1. Pick a hash function that mixes bits well -- modern libraries do this for you, but if you write your own, use a proven one (SipHash, xxHash, FNV for small cases).
  2. Keep the load factor bounded. Good rule: resize when (n / m > 0.75) (chaining) or (n / m > 0.5) (open addressing).
  3. Never assume iteration order unless your language guarantees it.
  4. For adversarial input (user-controlled keys, web requests), use randomized / keyed hashing to prevent collision attacks.
  5. For write-once-read-many keys, consider perfect hashing (FKS scheme) for guaranteed worst-case (O(1)) lookup.
  6. Measure p99 latency in production -- rehashing pauses are a common "mystery latency spike" source.
  7. For small (n), benchmark against a sorted-array-with-binary-search; below ~100 entries, arrays usually win.

For analysis, use linearity of expectation on indicator variables: "bucket (j) nonempty," "keys (i) and (j) collide," "probe sequence for (i) goes past position (t)." This is exactly the expectation machinery from the probability module applied to a data structure.

Transfer / Where This Shows Up Later​

  • S2 M2 (this module). Concept 12 (collision resolution) and concept 13 (universal hashing, load factor) are the concrete mechanisms that realize the expected bound.
  • S2 M3 (graphs). Graph representations with edge lookup use hash-set-of-edges for (O(1)) contains; BFS visited-set is always a hash table for modest graphs.
  • S2 M4 (dynamic programming). Memoization tables are hash tables from state to value; state hashability is the key engineering concern.
  • S3 (software design). "Keyed lookup" is the most common data-access pattern in clean code; the hash table is the default container, with a BST as fallback when order is needed.
  • S4 (systems programming). CPU-cache-friendly hash maps (Google SwissTable, Facebook F14, Rust hashbrown) rely on SIMD to probe 16 slots per cache line. Kernel dcache/inode caches are bucketed hash tables with RCU-based readers.
  • S5 (OS). Page-cache lookups by (file, offset), PID-to-task hash maps, and route-table lookups all use hashing; the adversarial-input concern shows up in network stacks as "hash-table DoS via crafted flows."
  • S6 (databases). Hash indexes for equality predicates, hash joins, hash partitioning in distributed query engines, Bloom filters for existence checks. LSM-trees use Bloom filters to avoid SSTable reads on missing keys -- a direct application of randomized hashing.
  • S7 (architecture). "Key-value store as a pattern" -- DynamoDB, Redis, memcached -- is a hash table as an architectural primitive.
  • S8 (system design). Consistent hashing (concept revisited in S8) is hashing made distribution-friendly for partitioned systems -- ring-based, rendezvous, or jump-hash variants all derive from the randomized-hashing model.

Check Yourself​

  1. Why is (O(1)) for hash tables expected rather than worst case?
  2. What assumption does the expected bound depend on, and how can it fail?
  3. When is a balanced BST the better choice than a hash table?
  4. Why does the expected max bucket size go to (\Theta(\log n / \log \log n)) under simple uniform hashing, and how does Java 8 exploit that threshold?
  5. Why is 64-bit hash generally collision-safe for (n = 10^5) but 32-bit hash is not?
  6. Under the load factor (\alpha = n/m), derive the expected cost of an unsuccessful lookup in a chained hash table and compare it to the successful-lookup expectation.
  7. If your language's hash table iterates in insertion order but the spec does not guarantee it, name two specific changes a runtime could make that would silently break your tests.

Mini Drill or Application​

  1. Using linearity of expectation, compute the expected number of empty buckets when (n) keys hash uniformly into (m) buckets.
  2. Given a bad hash h(k) = k mod 10, construct 10 input keys that all land in the same bucket and measure the lookup cost.
  3. Explain in two sentences why a hash-table-backed dictionary should not be used for a "range query" like "find all keys between 100 and 200."
  4. Implement a toy hash table with separate chaining; measure average chain length empirically on 1M random strings and verify it matches the predicted load factor.
  5. Demonstrate a HashDoS attack against a hash function of your choice (non-keyed). Then switch to a keyed / randomized hash and show the attack fails.
  6. Production scenario. Your Flask/Express API accepts arbitrary JSON payloads from the public internet and deserializes them into Python/JavaScript dicts. A penetration tester claims she can freeze the service with a 4 KB POST body. Walk through the HashDoS mechanism, then verify your runtime's defense (SipHash key rotation in CPython 3.3+, V8 hash seed randomization, etc.) by reading the relevant source comment and designing an integration test that would catch regression if a future release disabled the keyed hash.

Read This Only If Stuck​