Turn a key into an array index with a hash function and lookup becomes O(1) — until two keys land in the same bucket. Watch collisions happen, then watch two different strategies resolve them.
Controls
buckets8
Buckets
step 0
Insight
A hash function converts a key into an array index. Because array indexing is O(1), lookup is O(1) — provided collisions stay rare.
keys stored0
buckets8
load factor0.00
collisions0
Complexity
Average lookupO(1)
Worst lookupO(n)
SpaceO(n)
Hash Tables and Hashing
Constant-time lookup by turning a key into an address — and what happens when two keys want the same one.
Quick Context
A hash table stores key–value pairs in an array. A hash function converts each key into an array index, so finding a key requires no searching at all — you compute where it must be and go straight there.
What Makes a Good Hash Function
Deterministic — the same key must always give the same index, or you could never find anything again.
Uniform — keys should spread evenly across buckets. A function that sends everything to bucket 0 turns your O(1) table into an O(n) list.
Fast — it runs on every single operation, so it must be cheaper than the search it replaces.
The lab uses a simple polynomial rolling hash, shown live above the buckets. Real implementations use stronger functions, but the mechanism is identical.
Collisions Are Inevitable
There are infinitely many possible keys and only a finite number of buckets, so two keys will eventually hash to the same index. This is not a flaw to be engineered away — it is a certainty to be handled. Press Force collision to see one.
Two Ways to Resolve Them
Separate chaining — each bucket holds a small list. Colliding keys simply join the list. Simple, degrades gracefully, but costs extra memory for the pointers and loses cache locality.
Open addressing — on a collision, probe forward to the next free slot. Everything stays in one contiguous array, which is cache-friendly and faster in practice — but deletion becomes awkward (you need tombstones) and performance collapses as the table fills.
Switch between the two with the same keys and watch where the colliding entries end up.
Load factor and resizing
The load factor is entries divided by slots. As it rises, collisions become more frequent and operations slow down.
So hash tables resize: when the load factor crosses a threshold (0.66 in CPython, 0.75 in Java), a larger table is allocated and every entry is rehashed into it.
That resize is O(n), which means an individual insertion can be expensive. Averaged over many insertions it is O(1) — this is what amortised constant time means, and it is the same mechanism behind Python list append.
The practical consequence: if you know roughly how many entries you will store, pre-sizing avoids repeated rehashing. In Python that is rarely exposed; in other languages the constructor takes a capacity.
The worst case remains O(n) per operation, when every key collides. That requires either a terrible hash function or adversarially chosen keys — which was a real denial-of-service vector until languages began randomising their hash seeds per process. That is why Python's string hashes differ between runs unless PYTHONHASHSEED is fixed.
Why This Matters to You
Python's dict, JavaScript's Map and object, Java's HashMap, Go's map — all hash tables. When someone says "just use a dictionary for O(1) lookup", this is the machinery they are invoking. It is also why dictionary keys must be hashable and immutable: mutating a key after insertion changes its hash, and the entry becomes permanently unreachable.
Turning a key into an address
A hash table stores key-value pairs and finds any of them in roughly constant time, whatever the size.
The mechanism: a hash function converts the key into an integer, that integer is reduced modulo the table size to give an index, and the pair is stored there.
"apple" → hash() → 1839274 → % 16 → slot 10
Lookup does the same computation and goes straight to slot 10. No scanning, no comparison against other keys — one calculation and one memory access.
That is the whole idea, and it is why dictionaries are the workhorse of practical programming:
Operation
Hash table
Sorted array
Linked list
Lookup
O(1)
O(log n)
O(n)
Insert
O(1)
O(n)
O(1)
Delete
O(1)
O(n)
O(n) to find
Ordered traversal
Insertion order
Sorted
Insertion order
The trade is that nothing is sorted. If you need range queries or ordered iteration by key, a tree structure is the right choice.
Collisions, and the two ways to handle them
Two different keys can hash to the same slot. With 16 slots and 10 keys, collisions are not unlikely — they are near-certain, by the same reasoning as the birthday problem.
Chaining stores a list at each slot. Colliding keys are appended, and lookup walks the short list comparing keys. Simple, and it degrades gracefully.
Open addressing stores everything in the table itself: on collision, probe for the next free slot by a defined rule. Better cache behaviour, and deletion is awkward — a removed entry must leave a tombstone, or probe sequences break.
Chaining
Open addressing
Extra memory
Pointers per entry
None
Cache behaviour
Poorer — pointer chasing
Better — contiguous
Deletion
Straightforward
Needs tombstones
Behaviour when full
Degrades gradually
Degrades sharply
Python's dict uses open addressing with a randomised probe sequence. Java's HashMap uses chaining, switching a long chain to a tree above a threshold to bound the worst case.
Load factor, collisions, and the moment O(1) stops being true
A hash table is O(1) on average and O(n) in the worst case, and the distance between those two is decided by the load factor and the quality of the hash. Both are measurable, so rather than take the averages on trust, build a table and watch the chains grow.
example_01.pyPython
class Table:
def __init__(self, buckets, hashfn):
self.b = [[] for _ in range(buckets)]
self.hashfn = hashfn
self.n = 0
def put(self, key):
i = self.hashfn(key) % len(self.b)
if key not in self.b[i]:
self.b[i].append(key)
self.n += 1
def probes(self, key):
# comparisons needed to find (or fail to find) this key
i = self.hashfn(key) % len(self.b)
chain = self.b[i]
for pos, k in enumerate(chain):
if k == key:
return pos + 1
return len(chain)
def stats(self):
lens = [len(c) for c in self.b]
return (self.n / len(self.b), max(lens),
sum(lens) / max(1, sum(1 for x in lens if x)))
keys = ["key%d" % i for i in range(200)]
print("200 keys, a good hash, table grown to keep the load factor down")
print("%9s %8s %14s %14s %14s" % (
"buckets", "load", "longest chain", "avg chain", "probes for last"))
for buckets in (16, 64, 256, 512):
t = Table(buckets, lambda k: hash(k))
for k in keys:
t.put(k)
load, longest, avg = t.stats()
print("%9d %8.2f %14d %14.2f %14d" % (
buckets, load, longest, avg, t.probes(keys[-1])))
# Load factor is items per bucket. The average-chain column is measured
# over OCCUPIED buckets, so it cannot fall below 1 -- but watch it track
# the load down as the table grows: 12.5, 3.3, 1.5, 1.3. Four times the
# buckets, roughly a quarter of the chain. That is the whole reason
# implementations resize: keep the load near 1 and a lookup stays a
# constant number of probes whatever n is. Probes for the last key falls
# from 13 to 1 across these four rows, and n never changed.
#
# Now break the hash instead of the load factor.
def terrible(k):
return len(k) # collides every key of the same length
def bad(k):
return ord(k[0]) # collides on the first character
def good(k):
return hash(k)
print()
print("200 keys, 256 buckets, three hash functions")
print("%-22s %14s %14s %16s" % (
"hash", "buckets used", "longest chain", "probes for last"))
for name, fn in (("len(key)", terrible), ("first char", bad),
("Python's hash", good)):
t = Table(256, fn)
for k in keys:
t.put(k)
used = sum(1 for c in t.b if c)
print("%-22s %14d %14d %16d" % (
name, used, max(len(c) for c in t.b), t.probes(keys[-1])))
# The table has 256 buckets in all three rows. With len(key) as the hash
# there are only three distinct key lengths, so 253 buckets sit empty and
# a lookup walks a chain of 100. Hashing on the first character is worse
# still: every key starts with "k", so all 200 land in a single bucket and
# the table has degenerated into a linked list -- 200 probes, the O(n)
# worst case exactly. Nothing about the table is wrong; the hash is.
#
# This is also the shape of a real attack. If an attacker can predict your
# hash function and choose the keys -- form fields, JSON keys, HTTP
# headers -- they can send a few thousand colliding keys and turn every
# lookup quadratic. That is a hash-flooding denial of service, and it is
# why Python randomises string hashing per process:
print()
print("hash('a') differs between runs unless PYTHONHASHSEED is fixed:")
print(" this run:", hash("a"))
Output
Experiments to try
Insert a few keys and watch each one compute its own index — no searching involved at any point.
Press Force collision. Two keys land in the same bucket; the strategy selector decides what happens next.
Switch to open addressing with a collision present. The second key moves to the next free slot rather than sharing.
Reduce the bucket count to 4 and keep inserting. The load factor rises, collisions multiply, and lookups start needing several probes.
Look up a key after several collisions. The probe count is exactly how far O(1) has drifted toward O(n).
What to remember
Hashing replaces searching with computing an address. Collisions are unavoidable and must be resolved by chaining or probing; the load factor governs how often they happen. Keep it low and lookups stay effectively constant — let it climb and a hash table quietly becomes a linked list.
What makes a valid key
A key must be hashable, which means two things: it has a hash value that never changes, and it can be compared for equality.
If a list could be a key, mutating it after insertion would change its hash, and the entry would become unreachable — stored in a slot the new hash does not point to.
The contract between hashing and equality has two rules, and breaking the first causes genuinely confusing bugs:
Equal objects must have equal hashes. Otherwise two objects that compare equal land in different slots and both exist in the table.
Unequal objects may share a hash. That is just a collision, handled normally.
For a custom class, implement both together:
class Point:
def __init__(self, x, y):
self.x, self.y = x, y
def __eq__(self, other):
return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)
def __hash__(self):
return hash((self.x, self.y)) # hash the same fields as __eq__
Defining __eq__ without __hash__ makes the class unhashable in Python 3 — a deliberate safeguard against exactly this inconsistency.
Where hash tables show up
Dictionaries and sets in every modern language.
Caches and memoisation — a dictionary from arguments to results.
Deduplication — set(items) in one pass.
Counting and grouping — Counter, defaultdict(list).
Database indexes for equality lookups (though B-trees dominate, because they also support ranges).
Symbol tables in compilers and interpreters — the objects in a Python program are themselves stored in dictionaries.
The pattern that matters most in everyday code:
# O(n^2): for each order, scan every customer
for order in orders:
for c in customers:
if c.id == order.customer_id: ...
# O(n): build the index once
by_id = {c.id: c for c in customers}
for order in orders:
c = by_id[order.customer_id]
Building a dictionary to replace a repeated scan is the most common and most effective optimisation available in ordinary code.
Questions people ask
Why is lookup O(1) if collisions exist? Because with a good hash function and a bounded load factor, the expected chain length is a small constant. The worst case is O(n) and is not encountered in practice.
Are Python dictionaries ordered? They preserve insertion order, guaranteed since 3.7. That is not the same as sorted.
Why can a list not be a dictionary key? Mutating it would change its hash and orphan the entry. Use a tuple.
How much memory does a dictionary use? More than a list of the same values — it stores hashes and keeps spare slots. Lookup speed is what you are buying.
What is hash randomisation? Per-process randomisation of string hashes, added to prevent denial-of-service attacks that deliberately collide keys.
When should I not use a hash table? When you need sorted order, range queries, or a nearest-key lookup. Use a tree.
Recap in one screen
A hash function maps a key to a slot, so lookup is one computation and one access.
Collisions are inevitable and are handled by chaining or open addressing.
Load factor drives resizing, which is O(n) occasionally and O(1) amortised.
Keys must be immutable, and __eq__ and __hash__ must agree.
Replacing a repeated scan with a pre-built dictionary is the standard way to turn quadratic code linear.
Run it in Python
A hash table built from a plain list of buckets, with the collision chains printed so you can see them form. The last block deliberately picks a terrible hash function to show what the structure degrades into.
hash_table.pyPython 3
# A hash table with separate chaining: buckets of (key, value) pairs.
class HashTable:
def __init__(self, size=8, hash_fn=None):
self.buckets = [[] for _ in range(size)]
self.size = size
self.count = 0
self.hash_fn = hash_fn or (lambda k: hash(k))
def _index(self, key):
return self.hash_fn(key) % self.size # fold the hash into range
def put(self, key, value):
bucket = self.buckets[self._index(key)]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value) # update in place
return
bucket.append((key, value))
self.count += 1
if self.count / self.size > 0.75: # load factor
self._resize()
def get(self, key):
bucket = self.buckets[self._index(key)]
for k, v in bucket: # scan the chain
if k == key:
return v
raise KeyError(key)
def _resize(self):
old = self.buckets
self.size *= 2
self.buckets = [[] for _ in range(self.size)]
for bucket in old:
for k, v in bucket: # every key rehashed
self.buckets[self._index(k)].append((k, v))
print(f" ** resized to {self.size} buckets and rehashed everything")
def show(self):
for i, bucket in enumerate(self.buckets):
if bucket:
print(f" bucket {i:>2}: {[k for k, _ in bucket]}")
table = HashTable(size=8)
for word in ["apple", "banana", "cherry", "date", "elder", "fig", "grape"]:
table.put(word, len(word))
print("buckets:")
table.show()
print("get('cherry') ->", table.get("cherry"))
print(f"load factor: {table.count}/{table.size} = {table.count / table.size:.2f}")
print()
print("Now the same keys with a deliberately awful hash:")
bad = HashTable(size=8, hash_fn=lambda k: 1) # everything to one bucket
for word in ["apple", "banana", "cherry", "date"]:
bad.put(word, len(word))
bad.show()
print("Every lookup now scans a list. O(1) was never about hashing being magic -")
print("it was about the keys being spread out.")
Output
How the code works
self.hash_fn(key) % self.sizeTwo separate jobs: the hash turns a key into a number, the modulo folds that number into a valid index. Changing the table size changes every index, which is why resizing has to rehash.
for i, (k, _) in enumerate(bucket):The chain has to be scanned even on a hit, because two different keys can land in the same bucket. Comparing keys, not hashes, is what makes the answer correct rather than probable.
if self.count / self.size > 0.75:The load factor. Past roughly three-quarters full, collisions rise sharply, so the table doubles before that happens rather than after. CPython's own dicts resize on the same principle.
for bucket in old: ... self._index(k)A resize is O(n) and touches every key. Amortised over the n inserts that caused it that is O(1) each — but any single insert can be the expensive one, which matters for latency.
hash_fn=lambda k: 1Every key in one bucket. The structure still works and every operation is now O(n): a hash table's guarantee is entirely conditional on the hash spreading keys evenly.
Change one thing
Run it twice. The bucket numbers move, because Python randomises string hashing per process — a defence against deliberately collided input, and a reason never to rely on dictionary order across runs.
Insert enough keys to trigger two resizes and watch the bucket layout reshuffle completely each time.
Use hash_fn=len. Words of the same length collide, which is a much more realistic bad hash than the constant one.
Swap chaining for open addressing: on a collision, step to the next free slot. Deletion becomes the hard part — and that is why tombstones exist.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
The program replaces the hash function with 'lambda k: 1'. What happens?
The structure still works perfectly and every guarantee evaporates. O(1) was always conditional on the hash spreading keys out.
Why does a resize have to rehash every key?
The hash is stable; the fold into a bucket index is not. Doubling the table moves nearly everything.
The load factor threshold exists because:
Past about three-quarters full the chains get long fast. Resizing is O(n), but amortised over the inserts that caused it it is O(1) each.
Cheat sheet
Hash Tables and Hashing
Turn a key into an array index with a hash function and lookup becomes O(1) — until two keys land in the same bucket. Watch collisions happen, then watch two different strategies resolve them.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.