A dictionary maps keys to values — like an index at the back of a book. You look up a key in O(1) time, regardless of how many entries exist.
In this chapter you will use dictionaries to:
A dict stores key–value pairs. Keys must be immutable (strings, numbers, tuples).
# Creating a dict
ages = {"Alice": 30, "Bob": 25}
# Reading a value
ages["Alice"] # 30
# Adding / updating
ages["Carol"] = 28
# Check if a key exists
"Bob" in ages # True
# Looping over a dict
for name in ages:
print(name, ages[name])
# .get() returns a default instead of crashing
ages.get("Dave", 0) # 0 (Dave not in dict)
# Common patterns
ages.keys() # dict_keys(["Alice", "Bob", "Carol"])
ages.values() # dict_values([30, 25, 28])
ages.items() # dict_items([("Alice",30), ("Bob",25), ...])
# String methods you will use
text = "Hello World"
text.lower() # "hello world"
text.split() # ["Hello", "World"]
d[key] raises KeyError if the key is missing; d.get(key, default) is safe..split() with no argument splits on whitespace.Before coding the exercises, make sure you are comfortable with the four core operations.
A dictionary literal looks like {key: value, key: value, ...}.
d = {"apple": 3, "banana": 1, "cherry": 5}
d["apple"] # 3
d["banana"] # 1
Task: Create a dictionary scores with three student names and their exam scores. Then print the score for one student.
Use a literal like scores = {"Alice": 85, "Bob": 92, "Charlie": 78}, then access with scores["Alice"].
scores = {"Alice": 85, "Bob": 92, "Charlie": 78}
print(scores["Alice"]) # 85
You can add a new key or update an existing one with d[key] = value.
Task: Starting from an empty dict, add three entries one at a time. Then update one of them (increase the value by 10).
Verify that len(d) == 3 after adding, and that the updated value is correct.
Start with d = {}, then d["x"] = 10 to add, and d["x"] = d["x"] + 10 (or d["x"] += 10) to update.
d = {}
d["math"] = 90
d["science"] = 85
d["english"] = 78
d["math"] = d["math"] + 10 # or d["math"] += 10
print(d)
assert len(d) == 3
key in d — True if key existsd.get(key, default) — returns default instead of raising KeyError if key is missingTask: Write a function safe_lookup(d, key) that returns the value if the key exists, or the string "not found" if it does not.
safe_lookup({"a": 1}, "a") # 1
safe_lookup({"a": 1}, "b") # "not found"
You can use d.get(key, "not found") as a one-liner, or use an if key in d check.
def safe_lookup(d, key): return d.get(key, "not found")
def safe_lookup(d, key):
return d.get(key, "not found")
Write count_items(items) that takes a list and returns a dictionary where each key is an item and the value is how many times it appears.
Before you code:
count_items(["a", "b", "a", "c", "b", "a"]) # {"a": 3, "b": 2, "c": 1}
count_items([1, 2, 1, 1, 3]) # {1: 3, 2: 1, 3: 1}
count_items([]) # {}
Use if item in counts: to decide whether to increment or initialise. Alternatively, counts[item] = counts.get(item, 0) + 1 handles both cases in one line.
Structure: counts = {}, then for item in items: counts[item] = counts.get(item, 0) + 1, then return counts.
def count_items(items):
counts = {}
for item in items:
counts[item] = counts.get(item, 0) + 1
return counts
Now apply count_items to text: split a string into words, then count each word.
Write word_count(text) that:
text into words using text.split().word_count("hello world hello")
# {"hello": 2, "world": 1}
word_count("apple orange apple banana orange")
# {"apple": 2, "orange": 2, "banana": 1}
word_count("")
# {}
Hint: This is count_items applied to text.split(). Can you implement it by reusing count_items?
text.split() turns "hello world hello" into ["hello", "world", "hello"]. Pass that list to count_items.
One-liner: def word_count(text): return count_items(text.split())
def word_count(text):
return count_items(text.split())
Write most_frequent_word(text) that returns the word with the highest count. If there is a tie, return any one of the tied words.
most_frequent_word("the cat sat on the mat the") # "the"
most_frequent_word("a b a b c a") # "a"
Before you code:
word_count to get the frequency dictionary.max with a custom key argument?)Get the counts dict, then loop: track best_word and best_count, updating whenever you find a higher count.
Shorter approach: max(counts, key=counts.get) returns the key whose value is largest.
def most_frequent_word(text):
counts = word_count(text)
return max(counts, key=counts.get)
Write top_n_words(text, n) that returns a list of the n most frequent (word, count) tuples, sorted from highest to lowest count.
top_n_words("the cat sat on the mat the cat", 2)
# [("the", 3), ("cat", 2)]
Hint: Sort the word_count(text).items() by value in descending order, then take the first n.
Try it on a longer passage:
passage = "to be or not to be that is the question to be is to do"
top_n_words(passage, 5)
Use sorted(counts.items(), key=lambda pair: pair[1], reverse=True) to sort by count descending. Then slice with [:n].
Each item in counts.items() is a (word, count) tuple. pair[1] is the count. After sorting, return sorted_list[:n].
def top_n_words(text, n):
counts = word_count(text)
sorted_pairs = sorted(counts.items(), key=lambda pair: pair[1], reverse=True)
return sorted_pairs[:n]
You used a dictionary to count words. Could you have used a list of [word, count] pairs instead? What would be the main drawback?
To increment a word's count, you first need to check if it's already in the collection. How does that lookup work in a dict vs a list?
A list of pairs would work, but finding a word requires scanning from the beginning each time — O(n) per lookup. A dict does the same lookup in O(1) on average using hashing. For a document with thousands of unique words, the dict approach is dramatically faster. Lists CAN store pairs and CAN be sorted, so A and D are wrong.
Two words are anagrams of each other if they contain exactly the same letters (in possibly different order).
Examples:
Think about it: How could you represent a word so that all its anagrams map to the same key?
Write anagram_key(word) that returns the sorted string of a word's letters. This key will be the same for all anagrams.
anagram_key("listen") # "eilnst"
anagram_key("silent") # "eilnst"
anagram_key("evil") # "eilv"
anagram_key("vile") # "eilv"
Hint: sorted("abc") gives ["a","b","c"]. Use "".join(...) to get a string.
sorted(word) returns a list of characters in alphabetical order. Join them back: "".join(sorted(word)).
def anagram_key(word):
return "".join(sorted(word))
Write find_anagrams(text) that:
text into words.anagram_key.{key: [word1, word2, ...]}find_anagrams("listen silent enlist inlets hello world")
# {
# "eilnst": ["listen", "silent", "enlist", "inlets"],
# "ehllo": ["hello"],
# "dlorw": ["world"]
# }
find_anagrams("evil vile live veil")
# {"eilv": ["evil", "vile", "live", "veil"]}
You have anagram_key from Exercise 2.1. How would you group all words that share the same key?
Same pattern as count_items, but instead of incrementing a number, you append to a list. Check with if key in groups: to decide between groups[key].append(word) and groups[key] = [word].
You can also use groups.setdefault(key, []).append(word) to handle both cases in one line.
def find_anagrams(text):
groups = {}
for word in text.split():
key = anagram_key(word)
if key in groups:
groups[key].append(word)
else:
groups[key] = [word]
return groups
find_anagrams returns every word, including words with no anagram partner. Write find_true_anagram_groups(text) that returns only the groups that contain more than one word.
find_true_anagram_groups("listen silent hello world live evil")
# {"eilnst": ["listen", "silent"], "eilv": ["live", "evil"]}
# ("hello" and "world" are excluded — no partners)
Call find_anagrams(text) first, then filter the result: keep only entries where len(words) > 1.
Use a dict comprehension: {k: v for k, v in groups.items() if len(v) > 1}.
def find_true_anagram_groups(text):
groups = find_anagrams(text)
return {k: v for k, v in groups.items() if len(v) > 1}
A dictionary is a natural fit for tracking totals per category:
{"food": 500, "rent": 1000, "travel": 150}
Keys are expense categories; values are running totals.
Write update_expenses(expense_list, expenses_dict) that:
(category, amount) tuples and an existing dict.amount to the running total for category.expenses_dict in place (no return value needed).expenses = {}
update_expenses([("food", 200), ("rent", 1000)], expenses)
update_expenses([("food", 300), ("travel", 150)], expenses)
# expenses == {"food": 500, "rent": 1000, "travel": 150}
Before you code:
Same pattern as count_items: use expenses_dict[cat] = expenses_dict.get(cat, 0) + amount to handle both new and existing categories.
Loop over the expense list: for cat, amount in expense_list:, then update the dict on each iteration.
def update_expenses(expense_list, expenses_dict):
for cat, amount in expense_list:
expenses_dict[cat] = expenses_dict.get(cat, 0) + amount
Write print_expenses(expenses_dict) that prints each category and its total, one per line, in the format "category : amount".
print_expenses({"food": 500, "rent": 1000, "travel": 150})
# food : 500
# rent : 1000
# travel : 150
Loop over items: for cat, amount in expenses_dict.items(): then print(f"{cat} : {amount}").
def print_expenses(expenses_dict):
for cat, amount in expenses_dict.items():
print(f"{cat} : {amount}")
Write top_expense(expenses_dict) that returns the category with the highest total spend as a tuple (category, amount).
top_expense({"food": 500, "rent": 1000, "travel": 150})
# ("rent", 1000)
Loop over expenses_dict.items() and track the pair with the largest amount. Or use max(expenses_dict.items(), key=lambda pair: pair[1]).
max returns the whole tuple, so max(expenses_dict.items(), key=lambda p: p[1]) gives ("rent", 1000) directly.
def top_expense(expenses_dict):
return max(expenses_dict.items(), key=lambda pair: pair[1])
Write over_budget(expenses_dict, limits) that returns a dictionary containing only the categories where spending exceeds the budget limit.
limits is a dict of {category: budget}.{category: (spent, limit)} for each over-budget category.expenses = {"food": 500, "rent": 1000, "travel": 300}
limits = {"food": 400, "rent": 1200, "travel": 200}
over_budget(expenses, limits)
# {"food": (500, 400), "travel": (300, 200)}
# ("rent" is under budget: 1000 <= 1200)
Loop over expenses_dict.items(). For each category, check if the category exists in limits and whether spent > limits[cat].
Build the result dict: result = {}, then if cat in limits and spent > limits[cat]: result[cat] = (spent, limits[cat]).
def over_budget(expenses_dict, limits):
result = {}
for cat, spent in expenses_dict.items():
if cat in limits and spent > limits[cat]:
result[cat] = (spent, limits[cat])
return result
In the expense tracker, you used category names as dictionary keys. What would happen if you accidentally used expenses[category] = amount instead of expenses[category] += amount for a category that already exists?
What does = do to an existing dictionary key versus +=?
Assignment (=) replaces the value entirely, while += adds to it. Using d[key] = value when the key already exists silently overwrites the previous value — a common bug. Python won't warn you. This is why the pattern d[key] = d.get(key, 0) + amount or d[key] += amount (after initializing) is important.
Sometimes you need to look up a key by its value instead of the other way around. Inverting a dictionary swaps keys and values.
Write invert_dict(d) that returns a new dictionary with keys and values swapped. Assume all values in d are unique (otherwise some keys would be lost).
invert_dict({"a": 1, "b": 2, "c": 3}) # {1: "a", 2: "b", 3: "c"}
invert_dict({}) # {}
Loop over d.items() and build a new dict where each old value becomes a key and each old key becomes a value.
Dict comprehension: {v: k for k, v in d.items()}.
def invert_dict(d):
return {v: k for k, v in d.items()}
Write group_by(items, key_func) that groups items from a list by the result of applying key_func to each item.
This is a generalisation of both find_anagrams and the expense grouping pattern.
group_by(["cat", "car", "bar", "bat"], lambda w: w[0])
# {"c": ["cat", "car"], "b": ["bar", "bat"]}
group_by([1, 2, 3, 4, 5, 6], lambda x: x % 2)
# {1: [1, 3, 5], 0: [2, 4, 6]}
Same pattern as find_anagrams: compute a key for each item, then append the item to the list stored under that key.
groups = {}, then for item in items: k = key_func(item); groups.setdefault(k, []).append(item).
def group_by(items, key_func):
groups = {}
for item in items:
k = key_func(item)
if k in groups:
groups[k].append(item)
else:
groups[k] = [item]
return groups
find_anagrams is just group_by with anagram_key as the key function.
def find_anagrams_v2(text):
return group_by(text.split(), anagram_key)
Verify it gives the same results as your original find_anagrams.
This is a one-liner. The key insight is that group_by generalises the grouping pattern you already wrote by hand in find_anagrams.
def find_anagrams_v2(text):
return group_by(text.split(), anagram_key)
You've used dictionaries all chapter without asking the awkward question: d["banana"] is instant even if d holds a million keys. A list would have to check entries one by one. How does a dict jump straight to the right spot?
The answer is an idea you're about to invent: turn the key into a number, and use that number as a position.
Python exposes each character's numeric code: ord("a") is 97, and chr(97) goes back to "a".
Write letter_position(ch) returning the position of a lowercase letter in the alphabet — "a" → 0, "b" → 1, ... "z" → 25 — using ord (no lookup tables!).
ord("a") is 97. So letter_position(ch) = ord(ch) - ord("a").
def letter_position(ch):
return ord(ch) - ord("a")
One letter is easy. For a whole string, the simplest recipe: add up the character codes. That gives a big number; to turn it into a position, take the remainder when dividing by the number of slots available.
Write string_hash(s, n_buckets) = (sum of ord of every character) % n_buckets. The result is always a valid index between 0 and n_buckets - 1 — exactly what you need to pick a slot in a list of buckets.
string_hash("a", 10) # 7 (97 % 10)
string_hash("banana", 10) # deterministic: same input always gives same output
string_hash("listen", 10) # 5 (655 % 10)
Use sum(ord(ch) for ch in s) to add up all character codes, then take % n_buckets.
def string_hash(s, n_buckets):
return sum(ord(ch) for ch in s) % n_buckets
Run this before reading on:
string_hash("listen", 1000), string_hash("silent", 1000)
Both give 655. Of course — they're anagrams (Part 2 of this chapter!), so they contain the same letters, and addition doesn't care about order. Two different keys landing in the same bucket is called a collision, and a hash that collides for every anagram is a bad hash.
The fix: make position matter. Weight each character by where it sits:
hash(s) = sum of ord(s[i]) * (i + 1), mod n
Write string_hash_v2(s, n_buckets) using the weighted sum (hint: enumerate(s)), and confirm the anagram pair now separates.
string_hash_v2("listen", 1000) # 292 (2292 % 1000)
string_hash_v2("silent", 1000) # 299 (2299 % 1000)
Use enumerate(s) to get both the index and the character: sum(ord(ch) * (i + 1) for i, ch in enumerate(s)), then % n_buckets.
Multiplying by (i + 1) means the first character is weighted by 1, the second by 2, etc. This breaks the symmetry that caused anagrams to collide.
def string_hash_v2(s, n_buckets):
return sum(ord(ch) * (i + 1) for i, ch in enumerate(s)) % n_buckets
You just invented how a dict works inside:
That's why d[key] costs the same whether the dict holds ten keys or ten million: this is what O(1) lookup means.
Now zoom out. A big website can't fit a billion users on one database server; it splits them across many. Which server holds user 12345? Same invention: hash the key. With numeric IDs the hash is just the remainder.
Write which_shard(user_id, n_servers) returning user_id % n_servers, then check the test's fairness experiment: hashing 10,000 users across 7 servers should load every server almost equally.
which_shard(12345, 10) # 5
which_shard(12345, 7) # 4
Think about it (no code): if you add an 8th server, % 7 becomes % 8 — which users are now on the wrong server? (Almost all of them! Real systems soften this with consistent hashing — worth a web search. Python dicts face the same event when they grow: they resize and re-hash every key.)
This one is a one-liner: return user_id % n_servers. The interesting part is the reflection question about what happens when n_servers changes.
def which_shard(user_id, n_servers):
return user_id % n_servers
You built a hash function that converts a string to a number, then uses modulo to pick a bucket. What happens when two different keys hash to the same bucket (a collision)?
You saw collisions in Exercise C.3. Did the system break, or did it handle them?
Collisions are expected and handled: the bucket stores multiple entries (often as a linked list or similar structure). On lookup, Python hashes the key to find the bucket, then scans the entries in that bucket to find the exact match. As long as collisions are rare (a good hash function distributes keys evenly), each bucket has only 1–2 entries, keeping lookup effectively O(1).
| Function | What it does |
|---|---|
count_items(items) |
Count occurrences of each item in a list |
word_count(text) |
Count word frequencies in a string |
most_frequent_word(text) |
Find the most common word |
top_n_words(text, n) |
Top n words by frequency |
anagram_key(word) |
Canonical key: sorted letters as a string |
find_anagrams(text) |
Group words by anagram key |
find_true_anagram_groups(text) |
Only groups with 2+ words |
update_expenses(list, dict) |
Accumulate totals per category |
print_expenses(dict) |
Display category totals |
top_expense(dict) |
Category with highest spend |
over_budget(dict, limits) |
Categories that exceed their limit |
invert_dict(d) |
Swap keys and values |
group_by(items, key_func) |
General grouping — subsumes all of the above |
The group_by pattern is one of the most frequently recurring patterns in data processing: collect items into buckets based on a computed property.