The previous lesson ended with a wall: searching an array by value costs O(n). The formula base + i × size only works when you already know i. So here is the question this entire lesson sits on:
How could you turn any value into a valid index — without scanning, without sorting, without remembering where you put things?
Below is a hash table with 8 slots and a palette of keys. Tap a key. Whatever the table does to compute a slot, watch it carefully — you will need to predict the next one yourself.
A table has 8 slots (0-7). Key 100 needs a slot. Which operation maps 100 to a valid slot?
Each key went straight to a slot — no scanning, no guessing. The table computed key % tableSize and jumped there in one step. The remainder of dividing any number by N is always between 0 and N - 1, which is exactly the range of valid indices. Key 45 mapped to 45 % 8 = 5. Key 1000045 would map to the same slot, because both leave remainder 5 when divided by 8. The keys do not need to be small, sorted, or consecutive — modulo squashes any integer into the table's range.
That is the leap from O(n) to O(1). Memorize the two lines: slot = key % tableSize; table[slot] = key. They are the foundation of every hash map implementation. But seeing the formula and feeling it are different skills — what does the slot map LOOK like as you change the table size?
The formula has one trap: the slot is the remainder, not the quotient. When you read 20 ÷ 8, your instinct says 2 — that is how many full 8s fit. But the hash function does not care about the wraps. It needs the leftover: 20 = 2 × 8 + 4. The 4 is the slot. The 2 is irrelevant.
The only way to build this intuition is to drag the system around and feel where the arrow lands. Below, two sliders let you set the table size and the key. The dial draws as many ticks as there are slots and an arrow sweeps live to key % tableSize. Watch what happens when the key crosses an exact multiple of the table size. Watch how the slot map redraws when the table grows or shrinks.
You watched the arrow sweep around the dial. Every key landed somewhere in 0..tableSize-1. But hash tables have finite slots — the modulo function with table size N can produce only N distinct outputs. If two different keys leave the same remainder, they want the same slot.
This is not a flaw in the hash function. It is a mathematical certainty called the pigeonhole principle: more items than containers means at least one container holds multiple items. With 8 slots, any set of 9 or more keys MUST include a collision. The birthday paradox sharpens the warning — even with just 4 or 5 random keys and 8 slots, a collision is more likely than not. Each new key only needs to share a slot with ONE of the keys already present, and the probability grows faster than you expect as the table fills.
Together they explain why every serious hash table must have a collision-handling strategy — not as an edge case, but as a core design requirement. Keep inserting below. It is not a question of if, but when.
You have seen the modulo hash in action. It computes an index, it causes collisions, and it does both in O(1). But key % 8 is the simplest possible function. Is it good enough? What separates a good hash function from a broken one?
A few candidate properties matter — determinism, speed, uniform distribution. Below is a lab with four hash function variants. Three are broken in different ways; one is key % tableSize. You can drag the number of keys and the table size, then toggle between functions and watch the chain-length histogram redraw in real time. The good function spreads keys evenly across slots; the broken ones pile keys into one or two slots and leave the rest empty.
O(n) — you have a linked list with extra steps.Tap each function above. Drag the sliders. Watch the chains balloon — only one variant keeps the bars even.
930, 497, 310, 324, 517, 964, 242, 241, 8, 374, 811, 348, 517, 648, 125, 775, 531, 869, 326, 704, 811, 327, 618, 582, 457, 176, 956, 154, 812, 788 … +20 more