beginnerintermediateadvanced

Data Structures & Algorithms · Section 5

Hashing — Hash Maps and Sets

Level: beginner
Read: 80 min
Concepts: 14

Why a hash function makes dict/set lookups average O(1), the space-for-time trade that pattern unlocks — Two Sum, grouping anagrams, seen-before checks, frequency counting, composite keys — and the Python tools (defaultdict, Counter arithmetic, OrderedDict) built around it.

What is true here

A hash map or set trades O(n) extra memory for turning a repeated linear search into an O(1) average lookup.
In Two Sum, checking for the complement before inserting the current value stops an element from pairing with itself.
A grouping problem is a hash map from a shared signature to a list of matches, built with defaultdict(list).
Only hashable objects can be dict keys or set members — a tuple of hashable values works, a list never does.

What you will be able to do

Recognize an O(n²) brute force that a hash map or set can turn into O(n)
Solve Two Sum and Group Anagrams from the underlying hash-map pattern, not from memory
Choose between a set, a dict, and a Counter based on what the problem actually needs to store
Explain why a list cannot be a dict key, and fix it with a tuple

Concepts

Why hashing gives O(1) average lookups, and the canonical patterns built on trading space for time.

What a hash function does and why collisions happen

standardbeginner

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.

Think of it as

Think of the hash function as an address generator: hash(key) % table_size points at a specific shelf. Two different keys can generate the same shelf number — that is a collision — so the table also stores enough information in that bucket to tell the colliding keys apart once it gets there.

What we're doing: Show two different integer keys colliding into the same bucket once reduced by a small table size.

hash_buckets.pypython

def bucket(key, num_buckets):
    return hash(key) % num_buckets


print(bucket(10, 4), bucket(14, 4), bucket(18, 4))

1: hash(key) % num_buckets is exactly what a hash table does internally to pick a slot.
2: For a small int, hash(n) == n, so the collision here is easy to see by hand: 10, 14, and 18 are all 2 more than a multiple of 4.

Output

2 2 2

Why this works: 10, 14, and 18 are three different keys, but 10 % 4, 14 % 4, and 18 % 4 all equal 2 — all three collide into the same bucket. A real hash table still returns the right value for each key; it just has to check more than one candidate in that bucket to do it.

Remember: 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.

Why average-case dict/set operations are O(1)

referencebeginner

A dict or set jumps straight to a key's bucket using its hash, instead of scanning every entry — that direct jump is what makes get/insert/delete O(1) on average.

Remember: A dict/set computes where a key lives instead of searching for it — that direct jump is the entire reason lookups average O(1).

Was this helpful?

Using a hash map to trade space for time

corebeginner

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).

Think of it as

A brute-force solution that compares every element to every other element is re-asking "have I seen this before?" by re-scanning, every single time. A set or dict answers that exact question in O(1) by remembering the answer as it goes — you pay for a second data structure so the algorithm never has to look backward.

What we're doing: Detect whether a list has any duplicate value in one O(n) pass using a set, instead of comparing every pair.

has_duplicate.pypython

def has_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False


print(has_duplicate([1, 2, 3, 2]))
print(has_duplicate([1, 2, 3, 4]))

1: seen starts empty — it is the "memory" that replaces the inner loop.
4: n in seen is an O(1) average check, not a scan — this one line is the entire optimization.

Output

True
False

Why this works: [1, 2, 3, 2] has 2 appear twice; by the time the second 2 is reached, it is already in seen, so the function returns True without finishing the list. [1, 2, 3, 4] has no repeats, so seen never contains the current value and the loop runs to completion, returning False.

Reaching for nested loops before asking whether a set can replace the inner one

Wrong

python

def has_duplicate_slow(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Better

python

def has_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False

What you see: has_duplicate_slow gives the correct answer on small test cases, then times out once nums has around 10⁴–10⁵ elements.

Why: The nested loop compares every element to every later element — O(n²) comparisons. Trading O(n) extra space for a set turns each "have I seen this?" check into an O(1) average lookup, dropping total time to O(n).

Contains DuplicateeasyLeetCode
Exactly the example above — insert into a set and check membership as you go.
Longest Consecutive SequencemediumLeetCode
Put every number in a set, then only start counting a run from a number whose predecessor is not in the set — each element is visited O(1) times in total.

Remember: 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).

Two Sum via hash map (canonical example)

corebeginner

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.

Think of it as

At each number, the question is "does the number that would complete this pair already exist earlier in the list?" A dict that maps every value seen so far to its index answers that in O(1), so the whole list only needs one pass instead of one pass per element.

What we're doing: Find the indices of two numbers that add up to a target in one pass.

two_sum.pypython

def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []


print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))

3: complement is the exact value that would complete the pair with n.
5: seen[n] = i only runs AFTER the check — n is recorded for future elements to find, not for itself.

Output

[0, 1]
[1, 2]

Why this works: For [2, 7, 11, 15], target 9: at n=7 (index 1), complement is 2, already in seen from index 0, giving [0, 1]. For [3, 2, 4], target 6: at n=4 (index 2), complement is 2, already in seen from index 1, giving [1, 2].

Building the whole lookup map before scanning, instead of one entry at a time

Wrong

python

def two_sum_wrong(nums, target):
    seen = {n: i for i, n in enumerate(nums)}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [i, seen[complement]]
    return []


print(two_sum_wrong([3, 2, 4], 6))

Better

python

def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

What you see: two_sum_wrong([3, 2, 4], 6) returns [0, 0] — pairing index 0 with itself, even though only one 3 exists in the list.

Why: Building the full map upfront lets an element see its own index as a valid complement (3 + 3 = 6). Checking the complement BEFORE inserting the current element, one at a time, guarantees a match only ever pairs two different positions.

Two SumeasyLeetCode
Exactly the example above — one pass, checking the complement before inserting.
4Sum IImediumLeetCode
Same trick one level up: hash every possible sum of two lists, then look up the complement sum against the other two lists.

Remember: 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.

Was this helpful?

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

corebeginner

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.

Think of it as

Every grouping problem needs two decisions: what is the key that says "these belong together", and where do matching items get collected. A dict answers both: the key is whatever signature you compute (sorted letters, a remainder, a category name), and the value is the growing list of everything that produced that same signature.

What we're doing: Group words that are anagrams of each other using a sorted-letters key.

group_anagrams.pypython

from collections import defaultdict


def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        key = "".join(sorted(word))
        groups[key].append(word)
    return list(groups.values())


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

4: defaultdict(list) means groups[key] is an empty list the first time key is ever touched.
6: sorted("eat") and sorted("tea") both produce the same three letters — the shared key that groups them.

Output

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Why this works: "eat", "tea", and "ate" all sort to the same letters ("aet"), so they land in the same list. "tan" and "nat" both sort to "ant". "bat" sorts to "abt", shared by nothing else in the input, so it stays alone.

Appending to groups[key] on a plain dict, before the key has ever been set

Wrong

python

def group_anagrams_wrong(words):
    groups = {}
    for word in words:
        key = "".join(sorted(word))
        groups[key].append(word)
    return list(groups.values())


print(group_anagrams_wrong(["eat", "tea"]))

Better

python

from collections import defaultdict


def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        key = "".join(sorted(word))
        groups[key].append(word)
    return list(groups.values())

What you see: group_anagrams_wrong(['eat', 'tea']) raises KeyError: 'aet' on the very first word.

Why: A plain dict has no entry for a key until something explicitly sets one. groups[key].append(word) assumes the list already exists at that key — defaultdict(list) is what creates that empty list automatically the first time the key is touched.

Two SumeasyLeetCode
Not a grouping problem itself, but the easiest hash-map warm-up if this pattern is your first one.
Group AnagramsmediumLeetCode
Exactly the example above — sorted(word) as the key, defaultdict(list) as the collector.

Remember: 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.

Using a set for "seen before" checks

standardbeginner

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.

Think of it as

A set is a dict with the values thrown away — it only answers "is this in here?" in O(1). Reach for it whenever the question is yes/no membership, and reach for a dict only once you also need to store a count or a position alongside that answer.

What we're doing: Find the first character in a string that repeats an earlier one.

first_repeated_char.pypython

def first_repeated_char(s):
    seen = set()
    for ch in s:
        if ch in seen:
            return ch
        seen.add(ch)
    return None


print(first_repeated_char("hashing"))
print(first_repeated_char("abcdef"))

3: seen only ever needs to answer "have I added this character before?" — no counts, no positions.
4: The function returns the moment a repeat is found — it never needs to see the rest of the string.

Output

h
None

Why this works: "hashing" repeats 'h' at its fourth character, so the function stops there. "abcdef" has no repeats at all, so the loop finishes and None is returned.

Contains DuplicateeasyLeetCode
A set that only needs to answer membership — no counts or positions required.
Longest Substring Without Repeating CharactersmediumLeetCode
A sliding window whose "shrink" condition is exactly a seen-before check against the characters currently in the window.

Remember: 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.

Using a hash map as a frequency counter

standardbeginner

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.

Think of it as

Walk the collection once. For each item, look up its current count (or 0 if it has none yet) and add one. By the end, the dict holds every item's total count, built incrementally rather than recomputed from scratch each time a count is needed.

What we're doing: Count how many times each word appears, then find the most frequent one.

frequency_counter.pypython

def most_frequent(words):
    counts = {}
    for word in words:
        counts[word] = counts.get(word, 0) + 1
    return max(counts, key=counts.get)


print(most_frequent(["a", "b", "a", "c", "a", "b"]))

3: counts.get(word, 0) reads the running total so far, defaulting to 0 the first time a word appears.

Output

Why this works: "a" appears three times, "b" twice, and "c" once — "a" has the highest count, so max(counts, key=counts.get) returns it.

Majority ElementeasyLeetCode
Count every value, then return the key whose count exceeds half the list length.
Top K Frequent ElementsmediumLeetCode
Build the same frequency map, then take its k highest counts instead of just the single maximum.

Remember: 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.

Was this helpful?

Hashing tuples/frozensets for composite keys

standardbeginner

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.

Think of it as

A dict key does not have to be a single value. Any tuple made entirely of hashable elements is hashable itself, so (row, col) works as one key for a 2D position. When order should NOT matter — an edge between two nodes, say — a frozenset of the two endpoints gives the same key regardless of which endpoint came first.

What we're doing: Use a (row, col) tuple to mark visited grid cells, and an unordered frozenset pair to key an edge weight.

composite_keys.pypython

visited = set()
visited.add((2, 3))
print((2, 3) in visited, (3, 2) in visited)

edge_weight = {frozenset({"A", "B"}): 4}
print(edge_weight[frozenset({"B", "A"})])

2: (2, 3) is a single hashable value made of two numbers — a common key shape for grid problems.
5: frozenset({"B", "A"}) looks up the same key as frozenset({"A", "B"}) — order never mattered.

Output

True False
4

Why this works: (2, 3) was added, so it is found; (3, 2) is a different tuple, so it is not. The edge was stored with frozenset({"A", "B"}), and looking it up with the endpoints reversed still finds it, because a frozenset has no order to compare.

Remember: 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.

Was this helpful?

When a dict's insertion order matters (Python 3.7+ guarantees it)

referencebeginner

Since Python 3.7, iterating a dict always visits keys in the order they were first inserted — it is a language guarantee, not an accident of one implementation.

What we're doing: Confirm that dict keys come back in the order they were inserted, not sorted order.

insertion_order.pypython

d = {}
d["z"] = 1
d["a"] = 2
d["m"] = 3
print(list(d.keys()))

4: "z" was inserted first, so it comes first — despite sorting alphabetically after "a" and "m".

Output

['z', 'a', 'm']

Why this works: The keys come back exactly in insertion order ("z", then "a", then "m"), not alphabetical order — confirming the guarantee holds rather than depending on hash placement.

Remember: A dict's iteration order is guaranteed to be insertion order in Python 3.7+ — reach for it directly instead of collections.OrderedDict unless you need order-sensitive equality too.

Python tools

The standard-library types built specifically for hashing-based problems.

`dict`, `set`, `frozenset`

referencebeginner

dict maps keys to values; set holds unique values with no mapping; frozenset is the immutable, hashable version of set — usable as a dict key or set member itself.

dict_set_frozenset.pypython

ages = {"ada": 36, "linus": 55}   # dict — key -> value mapping
langs = {"python", "go", "rust"}   # set — mutable, unique values
frozen = frozenset(langs)           # frozenset — immutable snapshot of a set
nested = {frozen: "backend team"}   # only the frozen version can be a dict key

Remember: Reach for dict when values map to something, set when you only need uniqueness, and frozenset the moment that set itself needs to be hashable.

Was this helpful?

`collections.defaultdict`

standardbeginner

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.

Think of it as

A plain dict makes you check 'does this key exist yet?' before you can add to it. defaultdict removes that check: the first time any key is read or written, it silently calls the factory function to build a starting value (0 for int, [] for list), so counts[key] += 1 and groups[key].append(x) both just work from the very first key.

What we're doing: Use defaultdict(int) to count characters and defaultdict(list) to group numbers by parity.

defaultdict_examples.pypython

from collections import defaultdict

counts = defaultdict(int)
for ch in "banana":
    counts[ch] += 1
print(dict(counts))

groups = defaultdict(list)
for n in [1, 2, 3, 4, 5, 6]:
    groups[n % 2].append(n)
print(dict(groups))

3: counts[ch] += 1 works on the very first character — no need to check if ch is already a key.
8: groups[n % 2].append(n) creates the list for key 0 or 1 the first time each remainder is seen.

Output

{'b': 1, 'a': 3, 'n': 2}
{1: [1, 3, 5], 0: [2, 4, 6]}

Why this works: "banana" has b once, a three times, n twice — counts builds that up one character at a time. Odd numbers (1, 3, 5) land under key 1 and even numbers (2, 4, 6) under key 0, in the order each remainder was first seen.

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

Was this helpful?

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

standardbeginner

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.

Think of it as

Treat a Counter like a vector of counts, one per distinct key. Adding two Counters adds matching keys' counts together; subtracting does the same with subtraction. Either way, any key that ends at zero or below is dropped — a Counter never reports a non-positive count.

What we're doing: Combine and subtract two Counters, then rank the result.

counter_arithmetic.pypython

from collections import Counter

inventory = Counter(apples=3, bananas=2)
sold = Counter(apples=1, bananas=2, cherries=1)

print(inventory - sold)
print(inventory + sold)
print((inventory + sold).most_common(1))

4: bananas hits exactly 0 (2 - 2) and cherries goes negative (0 - 1) — both are dropped from the result entirely.
5: cherries only exists in sold, but + still keeps it, since addition keeps every key from either side.

Output

Counter({'apples': 2})
Counter({'apples': 4, 'bananas': 4, 'cherries': 1})
[('apples', 4)]

Why this works: inventory - sold leaves only apples (3 - 1 = 2), because bananas nets to 0 and cherries would go negative — both dropped. inventory + sold keeps all three keys, and .most_common(1) correctly picks apples as the highest combined count (4).

Valid AnagrameasyLeetCode
Counter(s) == Counter(t) — equality compares counts key by key.
Top K Frequent WordsmediumLeetCode
Counter(words).most_common(k) ranks by count, then the tie-break (alphabetical for equal counts) needs a custom sort key on top.

Remember: 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.

Was this helpful?

`collections.OrderedDict` (when explicit intent matters)

referencebeginner

A plain dict already preserves insertion order in Python 3.7+, so OrderedDict is now mostly about signaling that order matters, plus two extras: move_to_end() and order-sensitive equality.

ordereddict_example.pypython

from collections import OrderedDict

od = OrderedDict()
od["first"] = 1
od["second"] = 2
od.move_to_end("first")   # "first" is now the LAST key, in O(1)

Remember: A plain dict already keeps insertion order — reach for OrderedDict only for move_to_end() or order-sensitive equality, most commonly to build an LRU cache.

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

standardbeginner

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.

Think of it as

A dict key's hash has to stay the same for as long as the key lives in the dict — otherwise the dict would not know which bucket to look in anymore. A list can be mutated after being used as a key, which would break that guarantee, so Python refuses to hash it at all, immediately, at the point you try.

What we're doing: Use a tuple as a dict key successfully, then see the exact error a list key produces.

tuple_keys.pypython

cache = {}
cache[(1, 2)] = "wall"
print(cache.get((1, 2)), cache.get((5, 5)))

bad = {}
bad[[1, 2]] = "wall"

3: (1, 2) and (5, 5) are both tuples of hashable ints — (1, 2) is found, (5, 5) was never added so .get returns None.

Error

wall None
Traceback (most recent call last):
  ...
TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

Why this works: The tuple key (1, 2) works because both elements inside it are hashable ints. bad[[1, 2]] fails immediately because a list is mutable — Python refuses to compute a hash for it rather than risk a key whose hash could change later.

Remember: 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.

Was this helpful?

Spotted a mistake on this page? Tell us.

Read Sheet