Hash Maps & Sets: O(1) Lookups Explained

Searching an array for a value means walking it element by element, O(n), as the last lesson showed. The hash map's entire reason to exist is to make that question instant: "is kabir in here, and what's mapped to him?" answered in roughly constant time no matter how many keys you've stored. The trick behind it is one of the most satisfying ideas in computer science.

The trick: turn a key into an address

An array is fast because positions have addresses. list[7] jumps straight there. The catch is you can only look things up by number. A hash map asks: what if we could look things up by anything (a name, a word, a URL) and still get that direct jump?

The answer is a hash function. You feed it a key, and it spits out a number, a position in an underlying array of slots called buckets. Same key in, same number out, every time. So storing "kabir" -> "Mumbai" means: hash "kabir" to get, say, bucket 2, and drop the pair there. Later, looking up "kabir" hashes to bucket 2 again and you go straight to the slot. No scanning. You converted a meaningful key into an array index, and inherited the array's O(1) jump.

That's the whole idea. A set is the same machinery storing only keys, no values. Its job is membership: "have I seen this?" A dictionary (Python's hash map) stores key-and-value pairs. Both get their speed from hashing keys to buckets.

Collisions, and what to do about them

There's a problem hiding in "hash the key to a bucket." There are infinitely many possible keys and only a fixed number of buckets, so sooner or later two different keys hash to the same bucket. That's a collision, and it's not a rare edge case. It's guaranteed once you store enough keys.

The common fix is chaining: each bucket holds a little list. When two keys land in the same bucket, they both live there, side by side. To look one up, you go to its bucket and scan that short chain for the exact key. As long as the chains stay short (which a good hash function and enough buckets keep them), that scan is tiny and the lookup is still effectively constant.

Watch it happen. The visualizer below inserts five keys into four buckets. Each key gets hashed to a bucket, and when two collide, you'll see them chain together in the same slot.

Five keys, four buckets. By the pigeonhole principle at least one bucket must hold more than one key, so you're seeing a real collision and how chaining absorbs it. Notice the keys don't land in the order you typed them, and that's not a bug.

Why order isn't the point

Because position is decided by the hash, not by insertion order, a hash map has no inherent ordering. "sam" might sit in bucket 0 and "maya" in bucket 3 even though you added "maya" first. The structure is built for finding by key, not for remembering sequence.

A wrinkle worth knowing: Python's dict happens to preserve insertion order when you iterate it (guaranteed since Python 3.7), as a convenience layered on top. But set does not, and you should never rely on a hash structure's ordering for your logic. If order matters, that's a job for a list. If fast lookup by key matters, that's a hash map. Picking the structure to match the question is the recurring DSA skill.

Frequency counts and dedup in practice

Two everyday wins fall straight out of this: counting how often things occur (a dict mapping thing → count) and removing duplicates or testing membership (a set). The block below does both: a character frequency count, then dedup and an O(1) membership check.

The counts.get(char, 0) + 1 line is the frequency-count idiom: get the current tally for a key (defaulting to 0 the first time you see it) and bump it. The set turns six names into the four distinct ones, and "rohan" in unique answers without touching every element. It hashes "rohan" and checks one bucket. That same check on a 100,000-name list would scan up to all 100,000.

Where to go next

A hash map trades a bit of memory for the array's missing power: finding things by an arbitrary key in constant time instead of scanning. Collisions are unavoidable, chaining handles them, and the price you pay is giving up order, a fair deal when the question is "is this here?" or "what's mapped to this?"

Next: Two Pointers & Sliding Window, two array techniques that, together with the hash map, crack a huge share of real coding problems. If the dictionary syntax above was new, the dictionaries lesson in the Python series walks through it from scratch.