Hash Maps, Explained

A hash map (also called a dictionary, hash table, or associative array) is a way to store facts so you can find them again almost instantly.

It's the same idea everywhere — just a different name

This is one of the most common data structures in programming, so nearly every language has its own name for it. If you've used any of these, you've used a hash map:

Different name, same contract: store a key, get back a value, and do it fast.

Example Javascript Object:

{ apple: "macintosh", banana: "applebanana" }

Ordinary lists vs. hash maps

If your data lives in a list, answering a simple question — Have I already seen this value? What index was it at? How many times did it appear? — usually means walking the list from the start. That works for a handful of items. It falls apart when the list is long and you ask the same kind of question over and over. Every ask can cost another full walk.

A hash map changes the contract. Instead of "search the collection," you say "look up this key." The key is the thing you will ask about again — a word, an ID, a number you have already processed. Attached to that key is a value: whatever you need to remember about it (an index, a count, a leftover amount, a pointer to more data).

How the key becomes a location

This is the part that makes the speed possible, so it's worth slowing down on.

When you store a key, the hash map runs it through a hash function — a formula that converts the key into a number. That number is called a hash. Critically, the function is deterministic: the same key always produces the same number, every time you run it.

A rough mental model: take each character in the key, convert it to a numeric code, combine those numbers with some math (multiply, add, shift), then squeeze the result down to fit the size of the table — often with % table_size (the remainder after division). So something like:

hash("peach") → some large number → % 100 → 42

That final number, 42, is a slot index in an underlying array. So:

• Storing peach → "georgiapeach": compute hash("peach") → 42 → put "georgiapeach" in slot 42.
• Looking up peach later: compute hash("peach") again → same formula, same input → 42 again → go straight to slot 42 → the value is right there.

No comparison against other keys happens at all. The hash map isn't searching for "peach" among everything it holds — it's recomputing the same address it used the first time and walking straight there. That's the entire trick: the key is not a label to search for, it's a formula that computes a location.

This is why a hash map lookup takes roughly the same effort whether the map holds 10 items or 10 million — you're not comparing against the others, you're computing one address and jumping to it.

(One wrinkle: two different keys can occasionally hash to the same slot — a "collision." Hash maps handle this with strategies like storing a small list at that slot, or moving to the next open one. As long as collisions are rare, which a good hash function ensures, this doesn't meaningfully slow things down.)

Why this shows up constantly

Hash maps are the standard tool whenever the bottleneck is repeated membership or retrieval:

• Have I seen this before? (deduplicating, detecting repeats)
• What did I store for this key? (indexes, previous results, running totals)
• How many times has this appeared? (frequencies, anagrams, counting)
• What pairs with this? (complements — "I need target − x; is it already here?")

The cost of that speed is memory. You keep a table large enough to hold the keys you care about. In exchange, typical lookups stay roughly the same effort as the data set grows — you're not paying "walk the whole list" on every question. When people say a hash map gives average O(1) lookup, they mean exactly that: one hop to the right place, not a search that grows with every new item.

What "O(1)" means in plain English

O(1) is a nerdy way of saying: "the work doesn't really grow when the pile gets bigger."

Picture a vinyl shop. The slow way to find Miles Davis is flipping every sleeve and reading artist names. The fast way turns the name into a number with a hash, then opens the one bin that number points to — whether the shop holds 10 records or 10,000.

That filing system is the hash map idea again: text → number → address. You spend some space up front building the bins so you never have to dig through the whole stack later.

The skill to build: recognizing when a problem is really "I will need this fact again," and storing it the first time you see it so you never have to hunt for it twice..

The shape

1. Choose the key. What must you find again?
2. Store value. Index, count, or remnant
3. Probe once. Lookup instead of nested loops
4. Handle collisions. Trust the language map; know the cost
5. State the tradeoff. O(n) time, O(n) space typical

Worked example: Two Sum

For each number, ask whether target − x already sits in the map. If yes, return both indices; if not, record x → index and continue. One pass replaces the O(n²) double loop.

Use it when

You need fast membership, frequency counts, or complements — and a nested scan is the naive first draft.