beginnerintermediateadvanced

Algorithms · Hashing

Hashing — Hash Maps and Sets

Trading space for time — the single most common optimization trick in this whole roadmap

Space for timeO(n) memory buys back an O(n) inner loop
Check before insertstops Two Sum from pairing an element with itself
Set vs dictmembership only vs membership + payload
Hashable keys onlytuple works, list never does

1.Using a hash map to trade space for time

Storing what you have already seen in a hash map or set turns a repeated linear search into a single O(1) lookup — spending O(n) extra memory to cut an O(n²) scan down to O(n).

Key features

This is the first question to ask when a brute force is O(n²): "can a hash map or set remember something to avoid the inner loop?"
The trade is real, not free: it costs O(n) extra memory to buy back the time
The pattern repeats everywhere: Two Sum, grouping anagrams, detecting duplicates, and counting frequencies are all this same trade applied to a different question

Before writing a nested loop, ask whether a hash map or set can remember what you have seen — that one question turns most O(n²) brute forces into O(n).

2.Two Sum via hash map (canonical example)

To find two numbers that add up to a target, check whether target minus the current number has already been seen — one pass, one dict, O(n) instead of comparing every pair.

Key features

The map must hold values seen BEFORE the current index — checking the complement before inserting the current value is what stops an element from pairing with itself
The map stores index, not just presence, because the answer needs positions, not just values
This is the same space-for-time trade as algorithms.hashing-hash-maps-and-sets.trading-space-for-time, applied to "find a pair" instead of "find a duplicate"

Check whether the complement is already in the map before inserting the current value — that ordering is what stops an element from pairing with itself.

3.Grouping (e.g. group anagrams) via hash map of lists

To group items that share some property, map that shared property to a list of items — compute one key per item, and append it to the list stored under that key.

Key features

The key must be something that looks identical for every item in the same group — sorted(word) turns every anagram of a word into the same string
collections.defaultdict(list) removes the need to check "does this key exist yet?" before appending to it
The final groups.values() gives every group, in the order each group's first member was seen

A grouping problem is a hash map from "shared signature" to "list of matches" — defaultdict(list) removes the need to check whether a group already exists.

4.What a hash function does and why collisions happen

A hash function turns a key into a fixed-size integer, which a dict or set uses to pick which internal bucket to store it in. A collision is two different keys landing in the same bucket.

Key features

hash(key) always returns the same integer for the same object within one run — but str/bytes hashes are randomized per process (PYTHONHASHSEED), so they differ across runs
A collision does not lose data — dict/set resolve it internally (open addressing) — it only costs extra work to walk past the collision
Too many collisions degrade get/insert/delete from average O(1) toward worst-case O(n)
Only hashable objects can be hashed at all — see python.fundamentals.hashability

A hash function maps a key to a bucket index; a collision is two keys sharing a bucket, and too many collisions are what turn O(1) average into O(n) worst case.

5.Using a set for "seen before" checks

When a problem only needs to know whether something has already appeared — not how many times, and not where — a set is the right structure, not a dict.

Key features

x in a_set is O(1) average, the same as x in a_dict — both beat x in a_list, which is O(n)
A set stores no extra information per item — if you need a count or an index too, use a dict instead
set.add(x) is silently a no-op if x is already present — no error, no duplicate

If the question is "have I seen this before?" and nothing more, reach for a set — a dict is for when you also need to store something about it.

6.Using a hash map as a frequency counter

A dict from item to how many times it has appeared turns "how often does this occur?" into an O(1) update per item, instead of re-scanning the whole collection for every count.

Key features

counts.get(key, 0) + 1 avoids a KeyError on the first occurrence of a key — the default 0 stands in for "not seen yet"
max(counts, key=counts.get) finds the key with the highest count without a separate sort
collections.Counter and collections.defaultdict(int) both do this same job with less code — see the Python tools below

counts.get(key, 0) + 1 is the whole pattern — a hash map that counts occurrences as it goes, instead of scanning the input again for every question about frequency.

7.Hashing tuples/frozensets for composite keys

When a key is naturally more than one value — a grid coordinate, an unordered pair — a tuple or frozenset of hashable values is itself hashable, so it can be used as a dict key or set member directly.

Key features

A tuple is hashable only if every element inside it is hashable — (1, [2, 3]) is not, because the list inside is not
(2, 3) and (3, 2) are different keys — a tuple is ordered, so position matters
frozenset({"A", "B"}) and frozenset({"B", "A"}) are the SAME key — a frozenset ignores order, useful for undirected pairs
A plain set cannot be a dict key or set member — it is mutable, so unhashable; frozenset is the immutable, hashable version

A tuple of hashable values makes an ordered composite key; a frozenset makes an unordered one — a plain list or set cannot be a key at all.

8.`collections.defaultdict`

defaultdict(factory) is a dict that runs factory() to create a value the first time a key is touched, instead of raising KeyError — pass int to count, list to group.

Key features

defaultdict(int) starts every new key at 0 — perfect for counting
defaultdict(list) starts every new key at [] — perfect for grouping
A defaultdict silently creates an entry just by being READ, not only written — checking `key in d` before touching d[key] avoids surprise entries

defaultdict(int) for counting, defaultdict(list) for grouping — pick the factory that matches the starting value you would have written by hand.

9.`collections.Counter` (`.most_common()`, arithmetic on counters)

Two Counters support + and - directly, combining or subtracting their counts key by key — and .most_common(n) reads off the n highest counts from the result, no separate sort step.

Key features

counter_a - counter_b keeps only keys left with a POSITIVE count — a key that hits zero or goes negative disappears entirely
counter_a + counter_b adds matching keys together and keeps every key that appears in either counter
.most_common(n) works the same after arithmetic as it does on a fresh Counter — it just ranks whatever counts are currently there

Counter arithmetic (+, -) combines or subtracts by key and silently drops non-positive results — chain .most_common(n) on the result to rank what is left.

10.Using tuples as dict keys (must be hashable — no lists inside)

Only hashable objects can be dict keys — a tuple qualifies, but a list never does, even wrapped in nothing else, because Python cannot hash a mutable container.

Key features

dict[key] = value raises TypeError the instant key is unhashable — the failure is immediate, not delayed
A tuple of only hashable elements is hashable; a tuple containing a list, dict, or set inside it is not
The fix is almost always to convert the mutable container to its immutable equivalent first: list to tuple, set to frozenset

A tuple can be a dict key only if everything inside it is also hashable — a list can never be a key; convert it to a tuple first if it needs to be one.

Spotted a mistake on this page? Tell us.

Read Sheet