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)
Overview
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.
Quick Context
That is the core trade-off: a hash table uses more memory than a sorted array or a tree.
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 the same.
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.
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.
Experiments to try with Hash Tables and Hashing
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.
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.
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.
Predict, then reveal
About to run: Press Force collision. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
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
Hash a key into an array index for O(1) lookup and see how collisions, load factor and resizing keep the constant-time promise.
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.