Hash Table Time Complexity: Why Lookup Is O(1) (and When It Secretly Isn't)

You call dict[key] on a dictionary with ten million entries. Same call on a dictionary with ten entries. Same runtime. That's the hash table time complexity claim: O(1) lookup, regardless of size. It's not marketing. It's not a coincidence. There's a precise mechanism behind it, and understanding that mechanism is the difference between using hash tables correctly and reaching for one at exactly the wrong moment.

A Hash Table Is an Array With a Map to the Index

An array lookup is O(1) because memory is addressable. address(i) = base + i * element_size. One multiply, one add. Done, regardless of how big the array gets.

The problem with arbitrary keys is you can't use them as indices. The string "username" isn't a number. An object reference isn't a valid array offset. A hash table solves this by adding one step before the array access: it converts the key into a valid integer index using a hash function.

The formula is:

bucket_index = hash(key) % table_size

That index goes straight into an array called the bucket array. Lookup is now two steps: compute an integer, index into the array. Both O(1).

key → hash fn → raw integer → mod table_size → bucket index → value. Two constant-time steps.

The Hash Function Has One Job

The hash function takes a key of any type and returns an integer. It needs two properties: determinism (same key, same output, every time) and uniform distribution (keys spread evenly across available buckets, no bucket hoarding everything).

Here's a classic polynomial rolling hash for strings:

def hash_key(key: str, table_size: int) -> int:
    h = 0
    for char in key:
        h = (h * 31 + ord(char)) % table_size
    return h

Each character shifts the accumulator and mixes in the new byte. The prime 31 comes from Java's String.hashCode(). It works well for typical text. Change one character in the key and the output scrambles completely, which keeps keys from clustering.

Python's built-in hash() is more sophisticated. It mixes in a secret per-process seed. That seed matters a lot, and we'll get to exactly why shortly.

Collisions Are Unavoidable

Here's a thing developers believe: hash collisions are exotic, vanishingly rare, basically theoretical.

GPT isn't wrong for 10 objects. It just hasn't met a hash table with a million keys.

The bucket array is finite. The keyspace is not. Two keys will eventually map to the same bucket. The only question is when.

The birthday paradox makes this uncomfortably concrete. If you place n keys uniformly into m buckets, the probability of at least one collision exceeds 50% once n reaches roughly sqrt(m). For a table with 1,000 buckets, that's after 38 insertions. For a million-bucket table, around 1,000 insertions.

Collisions happen constantly in any real hash table, and a correct implementation handles them gracefully. The whole structure is built around this assumption.

Two Ways to Survive a Collision

Chaining puts a linked list at each bucket. When two keys hash to the same index, both live in the list at that bucket. Lookup scans the list linearly. Insertion appends.

Both keys land in bucket 3. The list grows. Lookup scans it. Expected length stays bounded by α.

Open addressing stores everything directly in the bucket array, no separate linked lists. On a collision, it probes for the next available slot using a fixed sequence. Linear probing checks (h + 1) % m, then (h + 2) % m, and so on. Quadratic probing uses (h + i²) % m. Double hashing computes the step size with a second hash function.

Lookup follows the same probe sequence until it finds the key or hits an empty slot.

Open addressing has better cache behavior because all data lives in one contiguous array. The probe sequence touches adjacent memory, which the CPU prefetcher handles well. Chaining follows pointers to linked-list nodes scattered across the heap, which the prefetcher cannot predict. Python's dict uses open addressing with a sophisticated probe sequence. Java's HashMap uses chaining, and since Java 8 it upgrades long chains to red-black trees once a chain exceeds length 8.

Hash Table Time Complexity: Why the Average Is O(1)

The O(1) claim comes down to one variable.

Define the load factor α = n/m: keys stored divided by buckets available. This is the average number of keys per bucket.

Under the Simple Uniform Hashing Assumption, each key is equally likely to land in any bucket, independently of all others. Under this assumption, the expected chain length at any bucket is exactly α. An unsuccessful lookup goes to the right bucket (O(1)) and scans a chain of expected length α (O(α)). Total: Θ(1 + α). A successful lookup is Θ(1 + α/2), which is the same asymptotically.

If you keep m proportional to n, then α = n/m is bounded by a constant, and every lookup is O(1) on average.

That's the whole proof. No magic. You maintain O(1) expected lookup by keeping the load factor below a fixed threshold. Java's HashMap defaults to α ≤ 0.75. Python's dict targets α ≤ 2/3. Go's map grows when α hits about 6.5 (it uses a denser per-bucket representation). Each threshold is a deliberate trade-off between memory and speed.

Open addressing degrades faster as α approaches 1. The expected probes for a successful search under linear probing is (1/2)(1 + 1/(1-α)). At α = 0.5 that's 1.5 probes. At α = 0.9 it's 5.5 probes. At α = 0.99 it's 50 probes. Open-addressed tables must stay further from the limit than chained ones, or you fall off a cliff.

Chaining barely flinches. Linear probing is fine until it isn't. The dashed lines show where Java and Python draw the threshold.

Rehashing Keeps the Load Factor Honest

As you insert keys, n grows and α climbs. At some point α hits the threshold. You have two choices: accept slower lookups, or grow the table.

Every practical hash table grows. It allocates a new array, usually twice the current size, then rehashes every existing key into the new bucket positions. This costs O(n) for the rehash. But it happens infrequently. After doubling, you can insert roughly n more keys before the next rehash. The amortized cost per insertion is O(1), by the same argument as dynamic array append: the rare expensive operation is paid for by the many cheap ones before it.

The one-time O(n) rehash buys you another n insertions before the next one. Cost amortizes away.

The Worst Case Is O(n), and Attackers Know This

Everything above assumes keys distribute uniformly. When they don't, one bucket accumulates all n keys and lookup degrades to O(n). The hash table becomes a linked list. A very expensive linked list.

This can happen by accident with a poor hash function. It also happens on purpose.

At the 28C3 conference in 2011, researchers showed that PHP, Python, Java, Ruby, and ASP.NET were all vulnerable to what they called hash flooding. An attacker who knows the hash function can craft input keys that all collide into the same bucket. A single HTTP POST with 65,536 crafted parameters could tie up a PHP 5 server core for about 30 seconds. Minimal bandwidth. Catastrophic CPU. The kind of thing that ruins a Monday morning.

The fix is to randomize the hash function with a secret seed that changes each time the process starts.

Python added randomized hash seeds in version 3.3, controlled by PYTHONHASHSEED. Java applies an extra bit-mixing step on top of Object.hashCode() inside HashMap. Go generates a per-map random seed at initialization. With a secret seed, an attacker who crafts collisions for one process gets essentially random distribution on the next.

Same keys, different outcome. The secret seed is what stands between "O(1) average" and "your server is on fire."

When a Hash Table Is the Wrong Tool

Hash tables are fast at exact-match lookup. They're slow at anything involving order.

Finding the minimum key requires scanning all n buckets. Iterating in sorted order requires sorting the keys first. Range queries like "all keys between X and Y" don't map naturally to a bucket structure at all. For those operations, a balanced BST gives you O(log n) lookup while supporting minimums, sorted iteration, and range queries out of the box.

Hash tables also have a constant factor that matters at small n. Computing the hash, potentially missing the L1 cache on the bucket array, following chain pointers. For fewer than about 16 keys, a plain array with linear scan is often faster in practice. The O(1) asymptotic advantage shows up at scale, not at toy size.

Use a hash table when you need fast exact-match lookup on a large, dynamic collection and don't need ordering. Use a sorted structure when order matters. The hash map complexity analysis covers the implementation-level detail if you want to go deeper.

The Short Version

• A hash table is an array accessed by a computed index: O(1) to hash, O(1) to access.
• Collisions are unavoidable. Chaining and open addressing handle them. Neither is magic.
• Average lookup is O(1) because the expected chain length equals the load factor α = n/m. Keep α below a constant, lookups stay constant.
• Rehashing doubles the table when α hits the limit. Amortized insertion is O(1).
• Worst case is O(n). Real implementations randomize the hash seed to prevent adversarial inputs from forcing this.
• Hash tables don't support ordered operations. Use a BST when order matters.

Technical interviews ask about trade-offs and failure cases, not just complexity labels. Explaining why O(1) holds in the average case, when it breaks, and what the fix looks like is exactly the kind of reasoning interviewers want. SpaceComplexity runs voice-based mock interviews where you practice articulating this kind of mechanistic reasoning under realistic pressure, with rubric-based feedback on how clearly you communicate it.

Further Reading

• Hash table - Wikipedia
• Hash function - Wikipedia
• Open addressing - Wikipedia
• Hashing - GeeksforGeeks
• std::unordered_map - cppreference