Master

Hash maps

Store key-value pairs for instant lookup without scanning through everything.

What you will see

About 2 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

A hash map pairs a key with a value for instant lookup, with no scanning at all. I look one value up by key, update an existing key, then add a new key and count the entries.

A hash map looks up a key directly instead of scanning every item. I print one person's age by name to show the fast lookup.

ages = {"Ada": 30, "Bob": 25} print(ages["Ada"])

Before you run it, say out loud what it will print. Then open the answer.

What it prints

A missing key raises a KeyError, not a slow scan. Look it up with ages.get(key) if it might be absent.

Assigning to an existing key updates its value in place with no duplicate key. I age Ada by one year and re-read it to confirm.

ages = {"Ada": 30, "Bob": 25} ages["Ada"] = 31 print(ages["Ada"])

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Assigning to a new key creates a brand new entry, but reassigning an existing key only changes the value that key already holds.

A new key lands in its own slot while an existing key just updates. I add one name and print the new total count of entries to confirm the growth.

ages = {"Ada": 30, "Bob": 25} ages["Cy"] = 40 print(len(ages))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Counting entries is O(1) with len on most maps, but adding a key never reorders or scans existing keys. Collisions are handled inside, out of sight.

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

A key is passed through a hash function to a slot where its value is stored, then retrieved by the same key.

1 Take a key and hash it to a slot

↓

2 Store the value at that slot

↓

3 To look up, hash the key again

↓

4 Jump straight to the stored value

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

ages = {"Ada": 30, "Bob": 25} sets nothing on screen

print(ages["Ada"]) 30

Why this works

How hashing works

A hash function converts a key into an integer slot in the table.

"Ada"  -> hash -> slot 3
"Bob"  -> hash -> slot 8
"Cy"   -> hash -> slot 3  (collision!)

When two keys land in the same slot it is called a collision. Hash maps handle collisions by chaining or by finding the next open slot. A good hash spreads keys out evenly.

When you have a choice

When to use a hash map

Use a hash map when you need fast lookup by a unique key.

Need	Best choice
Find by name/ID	hash map
Ordered data	array
Repeat counts	hash map

Count word frequencies?  hash map
Find a user by email?   hash map
Show a timeline of posts?  array

Hash maps are one of the most useful structures in real programs because lookup is so fast.

Examples

Keys and values

Looking up by name, not position

ages = {"Ada": 30, "Bob": 25}
print(ages["Ada"])   # 30

A hash map pairs a key with a value. You look up a key and get its value back almost instantly.

Why it works: a hash function turns the key into a slot number directly.

Adding and updating

Changing entries

ages["Ada"] = 31   # update existing
ages["Cy"] = 40    # add new
print(len(ages))   # 2

Adding an existing key updates its value. Adding a new key places it in a new slot. There is no scanning involved.

"Cy" -> hash -> slot 7 -> store 40

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Trees & graphs

Previous Lesson

Trees & graphs