Hash Tables Explained: Hashing, Collisions & Why Lookup Is O(1)

A courier has a letter for "Ravi Kumar, Patna". Does India Post search 140 crore citizens one by one? Of course not. The pincode tells them which sorting office, the office knows the area, the postman knows the street. Nobody ever searches — the address itself says where to go.

Now the computing version of that problem. You have 1 crore order IDs and a stream of new orders arriving; for each one you must answer: has this ID been seen before? Thousands of times per second.

This lesson builds the structure that answers in O(1) — the hash table, the machinery inside Python's dict and set — and, just as importantly, the fine print of when its promise breaks.

What would we naturally do?

Store the IDs in a list, and for each new order, scan:

seen = []                 # 1 crore ids
def is_repeat(order_id):
    return order_id in seen    # scans the list: O(n)

Correct — and doomed. Each check scans up to 1 crore entries; thousands of checks per second means lakhs of crores of comparisons. Even the sorted-list upgrade (binary search, O(log n) per check) stumbles: keeping the list sorted costs O(n) per insert, and orders never stop arriving.

Notice what all the searching has in common: we keep asking "where is this ID?" and paying to find out. What if the ID itself could tell us where it lives — like the pincode?

The observation: compute, don't search

Here is the whole idea. Keep an array of, say, 8 buckets. When a key arrives, feed it to a hash function — any deterministic recipe that turns the key into a number — and take that number modulo 8:

bucket_index = hash(key) % number_of_buckets

# store:  put (key, value) in bucket[bucket_index]
# lookup: recompute the SAME index, check that ONE bucket

Lookup never scans the table. It recomputes the index — one arithmetic step — and checks one bucket. The cost of finding a key does not depend on how many keys are stored. Ten entries or ten crore: same three steps. Watch it hold in practice:

import time

small = {i: i for i in range(1_000)}
big   = {i: i for i in range(10_000_000)}

for d, name in [(small, "1 thousand"), (big, "1 crore")]:
    t = time.perf_counter()
    for _ in range(100_000):
        _ = d.get(999)
    print(name, round((time.perf_counter() - t) * 1000, 1), "ms")

1 thousand 4.1 ms
1 crore 4.3 ms

The hash function

For the trick to work, the hash function must keep two promises:

Promise 1 — same key, same number, always. If hash("ravi") gave a different number tomorrow, yesterday's stored entry would be unfindable. Determinism is non-negotiable.

Promise 2 — different keys spread out evenly. If every key landed in bucket 3, we'd have rebuilt the list we were escaping.

print(hash("ravi"))     # some big integer - stable within a run
print(hash("ravi"))     # the SAME integer
print(hash("ravj"))     # tiny change in key -> totally different number
print(hash(42), hash(3.14), hash(("a", 1)))   # many types are hashable

You will almost never write a hash function — languages ship excellent ones. What you must own is the two promises, because every failure mode of hash tables is one of them breaking.

Collisions: the problem we created

Pause and find the flaw yourself: infinitely many possible strings, only 8 buckets. What must eventually happen?

Two different keys land in the same bucket — a collision. Not bad luck; mathematical certainty (the pigeonhole principle: more pigeons than holes means some hole gets two). So a hash table's design is really a collision-handling design, and there are two classic answers:

Separate chaining — each bucket holds a small list. Colliding entries append to it; a lookup walks that short list comparing actual keys. (This is why tables store the key alongside the value — the bucket alone doesn't prove identity.)

Open addressing — no lists. A colliding entry probes for the next free bucket by some rule and lives there. Python's dict uses a clever variant of this. Deletions get tricky (a hole can break a probe chain), which implementations solve with tombstone markers.

💡 In interviews, naming both schemes plus one practical difference — "chaining degrades gently; open addressing is cache-friendly but hates crowded tables" — is the difference between a memorised answer and an understood one.

Load factor and resizing

As entries pile up, buckets crowd, chains lengthen, and the O(1) starts leaking. The crowding has a number: load factor = entries ÷ buckets. At 0.1 the table is airy; at 5.0 every lookup wades through a five-entry chain.

So real tables watch the load factor and resize when it crosses a threshold (Python: about 2/3): allocate more buckets, then re-place every key — because hash(key) % buckets changes when the bucket count does. A resize is O(n).

Student question: doesn't that O(n) resize destroy the O(1) promise? You've seen this movie — it's the doubling list from lesson 2 wearing a new shirt. Doubling the bucket count makes resizes exponentially rare, so inserts stay amortised O(1). Same trick, second structure. It won't be the last time.

What if everything lands in one bucket?

Time for the fine print. Everyone says "dict lookup is O(1)" — let's find out when that's a lie.

What if the hash function breaks promise 2? Imagine hashing users by their country code: 100-odd buckets for crores of users. One bucket holds a crore-long chain, and lookup inside it is a linked-list scan — O(n). That's the worst case, and it comes from bad custom hash functions...

...and from attackers. If an adversary can craft keys that all collide (hash-flooding), they can turn your web server's dict into a linked list and your response times into syrup — a real attack class, which is why Python randomises string hashing per process.

What if the key is huge? Hashing a string reads all its characters — O(L) in key length. Invisible for normal keys; real for 1-MB keys.

So the honest sentence — say it exactly like this in interviews: "O(1) average, O(n) worst case, assuming a decent hash function — and here's when the worst case actually happens."

Why keys must be immutable — a detective story

Try this and Python refuses:

d = {}
d[[1, 2]] = "value"     # TypeError: unhashable type: 'list'
d[(1, 2)] = "value"     # tuple: works fine

Why the discrimination? Play detective — imagine lists WERE allowed. You insert with key [1, 2]; the entry is filed under hash([1, 2]), say bucket 5. Then you append: the key becomes [1, 2, 3]. Now every future lookup computes hash([1, 2, 3]) — bucket 2, maybe — and finds nothing. The entry still sits in bucket 5, alive but unfindable, forever.

A mutable key can silently break promise 1 (same key → same number) after insertion. Python prevents the entire failure class by refusing mutable keys: lists and dicts no; strings, numbers, tuples yes. Not an arbitrary rule — a rescue.

The four dict/set patterns that win interviews

A huge share of "optimise this" answers are one of four moves — all of them trading O(n) memory for O(1) lookups:

# 1. SEEN-SET - "have I met this before?" O(n^2) -> O(n)
seen = set()
for x in arr:
    if x in seen: ...
    seen.add(x)

# 2. FREQUENCY MAP - "count everything, then answer"
counts = {}
for x in arr:
    counts[x] = counts.get(x, 0) + 1

# 3. COMPLEMENT LOOKUP - two-sum's trick:
# store what you've seen; for each x ask "is target - x stored?"

# 4. CANONICAL KEY - group things equal "under a rule":
# anagrams -> key = "".join(sorted(word))

Watch move 3 work on the classic two-sum (find two numbers summing to 9 in [2, 7, 11, 15]). The naive way checks all pairs, O(n²). The observation: when I stand at 7, I don't need to search for a 2 — I need to ask "have I already seen a 2?" That's a membership question, and membership is what hash structures sell:

def two_sum(arr, target):
    seen = {}                      # value -> index
    for i, x in enumerate(arr):
        need = target - x
        if need in seen:           # O(1): "did my partner already pass?"
            return [seen[need], i]
        seen[x] = i                # check FIRST, insert after
    return None

i=0  x=2   need=7   seen? no    store {2:0}
i=1  x=7   need=2   seen? YES at 0  ->  [0, 1]

One pass, O(n). And a small landmine defused: we check before inserting — insert first, and with target 8 the element 4 would happily "find" itself as its own partner.

Common mistakes

• Saying "hash lookup is O(1), full stop" — the honest answer names average AND worst, with the why.
• Thinking collisions mean a broken hash function — they are guaranteed by counting; handling them IS the design.
• Trying to use a list (or any mutable object) as a key or set member — the lost-entry story above is the reason.
• Iterating the dict when the ORIGINAL order matters (first non-repeating character walks the string, not the dict).
• Inserting before checking in two-sum — an element matches itself.
• Expecting sorted iteration from a dict — insertion order is kept (Python 3.7+), sorted order never; ordered queries want a tree (lesson 7).

How do I recognise hashing problems?

• "seen before / exists / duplicate / unique" → seen-set.
• "count / frequency / most common" → frequency map (often finished with a heap for top-K).
• "pair/partner that satisfies a relation" → complement lookup (two-sum family).
• "group items that are equal under some rule" → canonical-form key (anagrams, normalised phone numbers).

And the counter-clues, equally valuable: the problem needs order (ranges, nearest, sorted output) → tree or sorted array; it needs prefixes → trie (lesson 10). Hashing scatters — that's its power and exactly its blindness.

Quick revision

One thing to remember

A hash table never searches — it computes where things live, like a pincode. Trade memory for that shortcut: remember what you've seen, and never look for it again.

Practice Zone — PYQs from real selection rounds

Six MCQs, then three hash classics: first non-repeating character, one-pass two-sum, and grouping anagrams with a canonical key.

Q1Hashingeasy

How does a hash table find a key among 1 crore entries in (average) constant time?

Asked in

aIt keeps keys sorted and binary searchesbThe hash function converts the key directly into a bucket index — compute, jump, donecIt checks every key but very quicklydIt caches the most recent lookups

Q2Collisionseasy

A collision in a hash table means:

Asked in

aTwo different keys hash to the same bucketbThe same key is inserted twicecThe table is fulldThe hash function crashed

Q3Collisionsmedium

Separate chaining handles collisions by:

Asked in

aRejecting the second keybEach bucket holding a small list of entries; colliding keys append to the same bucket's listcTrying the next empty bucket (that is open addressing)dDoubling the table immediately

Q4Complexitymedium

Hash table lookup is O(1) average but O(n) worst case. When does the worst case actually happen?

Asked in

aWhen the table has more than 1,000 entriesbWhen many/all keys land in the same bucket — a terrible hash function, or adversarial keys crafted to collidecNever; it is purely theoreticaldWhen keys are strings

Q5Load factormedium

The load factor of a hash table is entries ÷ buckets. Why do tables resize when it crosses a threshold (say 0.66)?

Asked in

aTo free memorybCrowded buckets mean longer chains/probes — resizing keeps average bucket occupancy low so lookups stay O(1)cBecause the hash function stops working above 0.66dResizing sorts the keys

Q6Hash keyshard

Why can't a Python list be a dict key, while a tuple can?

Asked in

aLists are too large to hashbA list is mutable — if it changed after insertion, its hash would change and the entry would be lost in the wrong bucketcTuples are secretly stringsdIt is an arbitrary language rule

Hands-on tasks:

FAQ

You now hold the most-used tool in interview optimisation. Next, we leave flat structures behind: folders inside folders — Lesson 6: Trees & Binary Trees →