Core · AlgorithmsLesson 3 of 8Free to read

Hash maps and sets · Data Structures and Algorithms

How do you find things instantly instead of searching?

Why you need it

The single most useful trick in interviews and in real code: trade a little memory for speed with a hash map (Python's dict) or a set. "Have I seen this?" and "how many of each?" go from O(n) per question to O(1).

The intuition

A hash map computes a number from the key (its hash) and uses it to jump straight to a slot, like a locker number. No scanning.

Three patterns cover most problems:

Seen set: if x in seen — duplicates, first repeat.
Counter: counts[x] = counts.get(x, 0) + 1 — frequencies, anagrams.
Complement lookup: for two-sum, ask "have I seen target − x?".

Definition

Hash map

A key → value store with O(1) average lookup, insert and delete. Python's dict. Keys must be hashable (str, int, tuple; not list).

Set

A hash map with only keys: fast membership tests, no duplicates, no order.

Examples

Two-sum with a dict

Try it yourself

Unsorted list, one pass. For each number, look up the partner it needs.

def two_sum(xs, target):
    where = {}
    for i, x in enumerate(xs):
        need = target - x
        if need in where:
            return (where[need], i)
        where[x] = i
    return None

print(two_sum([8, 3, 11, 5, 2], 7))

Step by step

L4For 8, the partner would be -1.
L7Remember each number's index.
L6At 2 (index 4), need is 5, seen at index 3.
L10Indexes 3 and 4: 5 + 2 = 7.(3, 4)

Count and compare

Try it yourself

Two words are anagrams if they have the same letter counts.

def counts(word):
    c = {}
    for ch in word:
        c[ch] = c.get(ch, 0) + 1
    return c

print(counts("level"))
print(counts("listen") == counts("silent"))

Step by step

L4get returns 0 the first time a letter appears.
L7Keys appear in the order first seen.{'l': 2, 'e': 2, 'v': 1}
L8Dicts compare equal when they hold the same pairs, in any order.True

Common mistakes

A list as a key

{[1, 2]: 'x'} raises TypeError: lists can change, so they can't be hashed. Use a tuple: {(1, 2): 'x'}.

Looking up a missing key

counts['z'] raises KeyError. Use counts.get('z', 0) or check 'z' in counts first.

Quick quiz

1. What does this print?

words = ["red", "blue", "red", "green", "blue", "red"]
seen = set()
first = None
for w in words:
    if w in seen:
        first = w
        break
    seen.add(w)
print(first, len(seen))

A
```
red 2
```
B
```
blue 3
```
C
```
red 3
```

Show the answer

Answer: A

red, blue are added; the second red is the first repeat. seen has 2 items at that point.

2. Checking `x in my_list` inside a loop over n items is O(n²). What makes it O(n) overall?

AMake my_list a set
BSort my_list first
CUse a while loop

Show the answer

Answer: A

Set membership is O(1) on average, so n checks cost O(n).

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictCount the votes
Type exactly what this program prints.
ModifyFaster common items
common(a, b) returns the items of a that are also in b, in a's order. x in b scans the whole list each time. Turn b into a set first so the function is O(len(a) + len(b)).
WriteGroup anagrams
Write group_anagrams(words) that returns a dict mapping each word's sorted letters (as a string) to the list of words with those letters, in the order they appear. For example "eat" and "tea" both go under "aet".

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Hash map	哈希表	A key → value store with fast lookup; Python's dict.
Hash	哈希值	A number computed from a key to find its slot quickly.