Skip to content

Hash Maps & Sets

Lesson 7 of 7 in Foundations · 35 min · Beginner

Turn a key into a bucket number and look there directly.

Introduction

A library holds 1,000,000 books. How can the librarian hand you any one of them at once, without walking the shelves to look for it?

Checking shelf after shelf could mean a million looks. Keeping the books sorted helps, but you still have to hunt for the right spot every time.

Now suppose the shelf number isn't kept in a list anywhere. The librarian works it out from the title with a fixed recipe, and the same title always gives the same shelf. Where would you walk?

Lesson overview

This lesson will show you how to:

  • Explain why a hash function turns lookups into near one-step jumps.
  • Trace how Two Sum stores each number and checks for its partner.
  • Spot problems asking "have I seen this before?" or needing counts.
  • Compare a nested-loop search with a single-pass map lookup.
  • Avoid inserting by accident when you only mean to check a key.

The picture

012346:d12:a17:c8:b8 → hash = 8 → 8 % 5 = 3key → bucket: look only herecollision chainother buckets: never touchedHash map with 5 buckets: bucket 0 empty; bucket 1 6 maps to d; bucket 2 12 maps to a, 17 maps to c; bucket 3 8 maps to b; bucket 4 empty. Hashing 8: hash 8, bucket 3. Marked: bucket 3 focus.

Mental model

Picture a library with one rule: do a little arithmetic on the title and the answer is the shelf number. Anyone can work out where a title lives without asking, so finding a book means walking to one shelf and glancing along it. If two titles land on the same shelf, they simply sit side by side.

A hash function turns a key into a bucket number, so you only ever search one small bucket, never the whole collection.

Words to know

key
The label you look things up by, like a title, a name or a number. Each key appears at most once in a map.
value
What you store under a key: a count, an index, a list, a name.
hash function
A fixed recipe that turns a key into a number. The same key always gives the same number. In our pictures it is simply key % 5.
bucket
One numbered slot in the table. The hash function says which bucket a key belongs to.
collision
Two different keys landing in the same bucket. It is normal, not an error, and every hash map has a plan for it.
chaining
Keeping a short list of entries inside each bucket, so colliding keys just sit side by side. One common plan; other tables use others.
load factor
Entries divided by buckets. As it climbs, chains get longer, so real hash maps add buckets and spread the entries out again.
set
A hash map that keeps only keys, with no values. It answers one question quickly: is this in here?

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The problem asks "have I seen this before?": duplicates, first repeat, membership.
  • Yes: You need to count how often each thing appears (frequency).
  • Yes: For each item you need a partner, a complement or an earlier value, and you can name exactly what to look for.
  • Yes: A nested loop is only there to search for a match. A map or set can replace the inner loop.

Not this when

  • No: You need the keys in order, or the next larger key. A hash scatters keys on purpose, so reach for sorting or a binary search tree.
  • No: You need to ask about ranges, like everything between 10 and 20, or the sum of a stretch. A hash can't answer that. Think prefix sums or a tree.
  • No: The keys are tiny whole numbers in a small range, like the letters a to z. A plain array of counts is simpler and faster.

Which pattern fits?

  1. Which pattern? 1 of 5

    Given an array of numbers, return true if any value appears at least twice.

  2. Which pattern? 2 of 5

    Given a sorted array, find two numbers that add up to a target, using only O(1) extra space.

  3. Which pattern? 3 of 5

    Keys keep arriving, and each time you must report the smallest key stored that is larger than 40.

  4. Which pattern? 4 of 5

    Given a list of words, group together the words that are anagrams of each other.

  5. Which pattern? 5 of 5

    Find the length of the longest substring that has at most 2 different letters.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1seen = an empty map, answer = nothing yet
  2. for each position i in nums:
  3. 2need = target - nums[i]
  4. 3if need is already in seen:
  5. 5answer = [seen[need], i], then stop
  6. 4seen[nums[i]] = i
  7. 6return answer

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def two_sum(nums, target):
    seen = {}
    answer = []
    for i in range(len(nums)):
        need = target - nums[i]
        if need in seen:
            answer = [seen[need], i]
            break
        seen[nums[i]] = i
    return answer
Time · O(n) total, O(1) per lookup on averageSpace · O(n)
  • One pass: each number triggers one lookup and one store. Both are O(1) on average, so n numbers cost O(n) in total.
  • "On average" is honest. If many keys land in one bucket, a single lookup walks a long chain and costs O(n), so a loop of n lookups could reach O(n²). A good hash function and resizing make this rare, and some libraries (Java's HashMap, for one) turn very long chains into trees.
  • The map costs O(n) memory. You are trading space for time: the nested-loop version needs no extra memory but takes O(n²) time.
  • Check the map before you store nums[i]. That order stops a number from pairing with itself.
  • Look up without inserting. In C++, seen[x] adds a default entry when x is missing, so use find or count to ask "is it there?". In Python, `x in seen` and `seen.get(x)` never insert.
  • Order is not part of the promise. Python's dict remembers insertion order; Java's HashMap and C++'s unordered_map do not. Never rely on it unless you picked an ordered type, like Java's LinkedHashMap or C++'s std::map.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each number may be used only once.

Input

nums = [8,3,2,4,6], target = 9

Output

[1, 4]

Approach

  1. The slow way tries every pair. Instead, for each number ask: which partner would finish the sum? That partner is target minus the number.
  2. Keep a map of the numbers you have already passed, each with its index. Looking up the partner takes one step.
  3. Walk left to right. 8, 3, 2 and 4 find no partner, so each is stored. At 6 the partner is 3, and 3 is in the map from index 1.
  4. Look before you store, so a number can never pair with itself. The answer is [1, 4].
def two_sum(nums, target):
    seen = {}
    answer = []
    for i in range(len(nums)):
        need = target - nums[i]
        if need in seen:
            answer = [seen[need], i]
            break
        seen[nums[i]] = i
    return answer
Time · O(n)Space · O(n)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. Why is looking up a key in a hash map usually fast?
  2. With 5 buckets and key % 5 as the hash function, you put key 12 and then key 17. What happens?
  3. A hash map lookup is O(1) on average. What is its worst case, and when does it happen?
  4. Why do real hash maps add more buckets as they fill up?
  5. In Two Sum, why do we look for the partner before storing nums[i]?

Question 1 of 5

Why is looking up a key in a hash map usually fast?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Contains Duplicate (opens in a new tab) (LeetCode, easy)

    Hint: For each number ask "have I seen it?". A set answers that in one step.

  2. Solve Ransom Note (opens in a new tab) (LeetCode, easy)

    Hint: Count the letters the magazine offers, then spend one count for every letter the note needs.

  3. Solve Isomorphic Strings (opens in a new tab) (LeetCode, easy)

    Hint: Each letter must always map to the same partner, and no two letters may share one, so track the mapping in both directions.

  4. Solve Group Anagrams (opens in a new tab) (LeetCode, medium)

    Hint: All anagrams share something identical, like their letters in sorted order. Use that as the key and keep a list of words under it.

  5. Solve Top K Frequent Elements (opens in a new tab) (LeetCode, medium)

    Hint: Count with a map first. Then the job is picking the k biggest counts, which sorting or bucketing by count can do.

  6. Solve Subarray Sum Equals K (opens in a new tab) (LeetCode, medium)

    Hint: Think prefix sums: a stretch sums to k when two running totals differ by k. What would you store to find the earlier total quickly?

  7. Solve Longest Substring Without Repeating Characters (opens in a new tab) (LeetCode, medium)

    Hint: It is a sliding window, and the set or map is how you notice the window has just been broken.

  8. Solve LRU Cache (opens in a new tab) (LeetCode, medium)

    Hint: A map finds an entry in O(1). You also need to move entries to "most recent" in O(1), so ask what structure reorders cheaply.

Additional resources