🧩 Data Structures & Algorithms · Chapter 3

Hashing and hash maps

A list makes you ask every item 'are you the one?'. A hash map computes where the answer lives and goes straight there — which is why it turns so many O(n²) solutions into O(n).

Study this lesson free in the app →

The basics

A hash map (Python dict, Java HashMap, JavaScript Map) stores key → value pairs and finds any key in about the same time no matter how many it holds. A hash set (set) is the same thing with keys only.

The problem it solves: checking "have I seen this?" or "what's stored under this name?" in a list means scanning — O(n). A hash map instead runs the key through a hash function that turns it into a number, and uses that number to pick a bucket directly: bucket = hash(key) % number_of_buckets. No scanning, so lookups, inserts and deletes are O(1) on average.

The mental model: a cloakroom. You hand in your coat and get ticket 47; to collect it, the attendant walks straight to hook 47. Nobody searches the racks.

Explained

Find two prices in a list of 100,000 that add up to exactly your gift-card balance.

Compare every pair: about 5 billion checks.

Walk the list once and, for each price, ask a hash set "have I already seen the price that would complete this?": 100,000 checks.

Same answer. The hash map is the difference between minutes and milliseconds.

The cloakroom

A theatre cloakroom has 100 hooks. When you hand in your coat, the attendant looks at your surname, does a quick calculation, and hangs it on hook 47. When you come back, the same calculation sends them straight to hook 47.

That calculation is the hash function. The hooks are buckets.

Sometimes two guests compute to the same hook. The attendant just hangs the second coat on top — a collision, handled by chaining. Finding your coat now means checking two coats on one hook, not walking all 100.

On a sold-out night, hooks hold five coats each and service slows. So the theatre installs a second rack and re-hangs every coat by the new calculation — a resize. Painful once, then fast again.

Precisely

Insert key → value:

1. Compute h = hash(key) — any integer, possibly huge.
2. Choose a bucket: i = h % capacity.
3. If the bucket is empty, store the pair. If not, a collision:

- Chaining (Java's HashMap): append to that bucket's list. - Open addressing (Python's dict): probe other slots in a fixed sequence until a free one turns up.

1. If entries ÷ capacity passes a threshold (about 2/3 in CPython, 0.75 in Java), resize: allocate a larger array and re-insert everything, because h % capacity changes when capacity does.

Lookup repeats steps 1–2, then compares keys in that bucket with == until it finds a match.

| Operation | Average | Worst | | --- | --- | --- | | insert / lookup / delete | O(1) | O(n) | | iterate all entries | O(n) | O(n) | | space | O(n) | O(n) |

The worst case needs many keys in one bucket. A decent hash function plus resizing makes that vanishingly rare on ordinary data.

Plenty of buckets: every key on its own hook

Five keys, ten buckets — a load factor of 0.5. Watch each key turn into a bucket number. With this much room, keys rarely share a bucket, so a lookup is one hash and one comparison: O(1).

Too few buckets: collisions pile up

Seven keys, three buckets — a load factor of about 2.3. At least one bucket must hold three or more keys, and chains form. Finding a key at the end of a long chain means walking it item by item — a little linear search. This is why real tables resize long before they look like this.

The three patterns you'll use weekly

from collections import Counter, defaultdict

# 1. Count frequencies — O(n) time, O(k) space for k distinct items
Counter("mississippi").most_common(2)     # [('i', 4), ('s', 4)]

# 2. Seen-before / dedupe — O(n) time, O(n) space
def first_repeat(items):
    seen = set()
    for x in items:
        if x in seen:
            return x
        seen.add(x)
    return None

# 3. Group by a computed key — O(n · k log k) for n words of length k
def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)    # 'tea' -> 'aet'
    return list(groups.values())

group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Keys must be hashable: use a tuple (row, col), never a list [row, col].

When hashing gets expensive

• Resizing — growing a table with 10 million entries re-places all 10 million. Amortised it's still O(1) per insert, but that one insert can pause for a noticeable moment. Pre-size when you know the count.
• Memory — a hash table keeps spare empty buckets on purpose. A Python dict often uses several times the memory of a plain list of the same items. For hundreds of millions of keys, people reach for compact structures or a database.
• Hash flooding — an attacker who knows your hash function can send keys that all collide, turning every lookup into O(n) and stalling a web server. That's why Python randomises string hashes per process (hash("abc") changes between runs) and why Java turns very long buckets into small balanced trees.
• Across machines — the same hash(key) % n idea decides which server or partition owns a key. Change n and most keys move; consistent hashing is the fix you'll meet in system design.

Gotchas

• Mutable keys — d[[1, 2]] = 'a' raises TypeError: unhashable type: 'list'. Use a tuple.
• __eq__ without __hash__ — if two objects are equal they must hash equally, or a set will happily hold "duplicates".
• A constant __hash__ — return 1 is legal and makes every key collide: O(1) quietly becomes O(n).
• Expecting order by key — dicts keep insertion order (Python 3.7+), not sorted order. Need min/max quickly? That's a heap or a sorted structure.
• Calling it O(1) without saying "average" — the worst case is O(n); interviewers listen for the word.
• Iterating while inserting — changing a dict's size during a loop over it raises RuntimeError.

Words to know

In two minutes

• A hash map turns a key into a bucket index with hash(key) % buckets, so insert, lookup and delete are O(1) on average. Space is O(n).
• Collisions are normal: chaining keeps a list per bucket, open addressing (what Python's dict does) probes for another slot.
• Keep chains short by keeping the load factor low: the table resizes — roughly doubling and re-placing every key — when it gets too full. Resizes are O(n) but rare, so inserts stay amortised O(1).
• Worst case is O(n) per lookup, when many keys share a bucket — from a bad hash function or deliberately crafted keys.
• Keys must be hashable and must not change: tuples and strings work, lists and dicts raise TypeError.
• Hash maps don't keep keys sorted; finding the min or max key is O(n).
• The big patterns: count frequencies, 'have I seen the complement?' (two-sum), dedupe, and group by a computed key (anagrams).

Test yourself

There are 9 questions, 4 puzzles and 6 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.