Hash Map
Medium+85 XPStore key→value pairs and fetch any of them almost instantly — by letting a hash function pick the slot.
No visualization loaded.
Watch
—
Press Run to begin.
A hash map (also called a dictionary or hash table) stores PAIRS: a key and its value, like "cat" → 5. The magic is how it finds a pair fast. Instead of searching one-by-one, it runs the key through a little machine called a HASH FUNCTION that turns the key into a number — a bucket index. The pair goes into that bucket, and to find it later you just hash the key again and jump straight to that bucket. No scanning the whole map. Sometimes two different keys get the same bucket number; that's a COLLISION, and we handle it by hanging both pairs in a little chain under that bucket.
▸What's a hash function?
It's a recipe that turns a key into a number. In our demo the recipe is: add up the letter codes of the key, then take the remainder when you divide by the number of buckets. Same key in → same number out, every time. That number is the bucket where the pair lives, so the map knows exactly where to look without checking everything.
▸What's a bucket, and what's chaining?
A bucket is just one slot in a row of slots — like numbered cubbies. The hash number says which cubby a pair belongs in. When two pairs are sent to the SAME cubby, we don't throw one away — we clip the second one onto the first like links on a keychain. That little keychain is called a chain, and looking inside means checking just those few links, not the whole map.
▸What's a collision, and why doesn't it break things?
A collision is when two different keys hash to the same bucket number. It happens because there are way more possible keys than buckets, so some have to share. It doesn't break anything because of chaining: both pairs sit in that one bucket as a short chain. To find one, you hash to the bucket, then walk its tiny chain. As long as chains stay short, it's still fast.
▸Why is lookup O(1) on average?
Because hashing jumps you DIRECTLY to the right bucket in one step — it doesn't depend on how many pairs you've stored. If the hash function spreads keys out evenly, each bucket holds only a couple of pairs, so the chain you walk is tiny. One jump plus a glance at a short chain is constant work on average, no matter if the map has 10 pairs or 10 million.
▸How is this different from an array or a list?
In an array you look things up by a NUMBER position (slot 0, slot 1...). A hash map lets you look things up by ANY key — a word, a name, anything — by secretly turning that key into a slot number for you. A plain list would make you scan item by item to find a key (slow, O(n)). The hash map's trick of computing the slot is what makes it jump straight there instead.
How the work grows
O(1) average is instant — doesn't grow at all. Hashing jumps straight to a bucket in one step, independent of how many pairs are stored, and a good hash keeps each chain tiny — so insert and lookup are constant work on average. (Worst case, if every key collides into one bucket, it degrades to O(n), which is why a good hash function matters.) Space grows with the number of pairs you keep.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.