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.
index = hash(key) % number_of_buckets
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
load factor = keys stored / number of buckets
As the load factor climbs, collisions become common and performance decays toward O(n). Implementations therefore resize — typically doubling the bucket count and rehashing every key — once the load factor passes a threshold (0.75 in Java's HashMap, around 0.66 in Python's dict).
Rehashing is an expensive O(n) operation, but it happens rarely enough that the amortised cost of insertion stays O(1). Add keys here and watch the load-factor warning appear.
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.
Interactive Exploration Guide
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).
Key Takeaway
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.
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.