Lists, tuples, dicts and sets · about 45 min

Dictionaries

Why this matters

Lists find things by position. Very often you want to find things by name: a user's record by username, a word's count by the word, a configuration value by its key, the price of a product by its code. The dictionary (dict) maps keys to values and finds a value by its key in roughly constant time, no matter how big the dictionary is. Dicts are everywhere in Python: JSON data becomes dicts, keyword arguments arrive as a dict, and even the interpreter stores each module's global variables in one.

Creating and using dicts

A dict literal lists key: value pairs in curly braces:

ages = {"ada": 36, "alan": 41, "grace": 85}
empty = {}
print(ages["alan"])
print(len(ages))
41
3

Assigning to a key adds or replaces:

ages["linus"] = 54      # new key: added
ages["ada"] = 37        # existing key: value replaced
print(ages)
{'ada': 37, 'alan': 41, 'grace': 85, 'linus': 54}

Each key appears at most once. Other ways to build dicts:

d1 = dict(red=1, green=2)                 # keyword arguments
d2 = dict([("x", 10), ("y", 20)])         # from (key, value) pairs
print(d1, d2)
{'red': 1, 'green': 2} {'x': 10, 'y': 20}

Missing keys

Looking up a key that is not there with square brackets raises KeyError:

print(ages["bob"])
Traceback (most recent call last):
  File "demo.py", line 1, in <module>
    print(ages["bob"])
          ~~~~^^^^^^^
KeyError: 'bob'

Three ways to deal with that:

print("bob" in ages)            # membership tests keys: False
print(ages.get("bob"))          # None instead of an error
print(ages.get("bob", 0))       # or a default of your choice: 0

in on a dict checks keys, not values. To test values use x in d.values() (which is a slow, linear scan).

Removing

ages = {"ada": 36, "alan": 41, "grace": 85}
del ages["alan"]               # KeyError if missing
born = ages.pop("grace")       # remove and return the value
maybe = ages.pop("bob", None)  # with a default, no error
print(ages, born, maybe)
{'ada': 36} 85 None

Iterating

Looping over a dict gives its keys. The methods keys(), values() and items() give views of keys, values, and (key, value) pairs:

prices = {"tea": 3.5, "cake": 4.0, "jam": 2.25}
for item in prices:
    print(item)
for item, price in prices.items():
    print(f"{item}: {price:.2f}")
print(sum(prices.values()))
tea
cake
jam
tea: 3.50
cake: 4.00
jam: 2.25
9.75

Since Python 3.7, dicts preserve insertion order: iteration visits keys in the order they were first added (replacing a value keeps the position; deleting and re-adding moves it to the end). That is a language guarantee, so output that loops over a dict you built is deterministic. If you want a different order, sort: for k in sorted(d): gives keys alphabetically.

Warning: Do not add or delete keys while looping over a dict. Python detects it and raises RuntimeError: dictionary changed size during iteration. Loop over list(d) (a copy of the keys) if you must delete.

Patterns you will use constantly

Counting. Start at zero for unseen keys:

counts = {}
for ch in "mississippi":
    counts[ch] = counts.get(ch, 0) + 1
print(counts)
{'m': 1, 'i': 4, 's': 4, 'p': 2}

Grouping. Collect items into lists per key. setdefault(key, default) returns the existing value, or inserts default and returns it, so it is perfect for "create the list on first use":

words = ["apple", "avocado", "banana", "blueberry", "cherry"]
by_letter = {}
for w in words:
    by_letter.setdefault(w[0], []).append(w)
print(by_letter)
{'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}

The standard library also offers collections.Counter and collections.defaultdict for these two jobs; module 10 covers them. Write them by hand first so you know what they do.

Merging. d.update(other) copies all pairs from other into d, overwriting duplicates; d | other makes a new merged dict:

defaults = {"color": "blue", "size": "M"}
chosen = {"size": "L"}
print(defaults | chosen)
{'color': 'blue', 'size': 'L'}

Records. A dict can describe one thing with named fields: {"name": "Ada", "born": 1815}. A list of such dicts is how JSON data usually looks.

What happens underneath: a hash table

How can d[key] be fast with a million entries? A dict is a hash table. When you store a key, Python calls hash(key), which turns the key into a large integer, and uses that number to pick a slot in an internal array. To look the key up later, it hashes again, goes straight to that slot, and checks that the key there is equal (==) to the one you asked for:

hash("alan") -> 7203947190... -> slot 5
                                       slots: 0 [ ]
                                              1 [ "ada"   -> 36 ]
                                              ...
                                              5 [ "alan"  -> 41 ]

No scanning through all the entries is needed, so lookup, insertion and deletion take about the same time whatever the size: O(1) on average. (When two keys land on the same slot, a collision, Python probes other slots in a fixed pattern; the internals module goes into the details, and into how CPython keeps insertion order cheaply.)

This design explains the rule on keys: keys must be hashable, meaning their hash never changes during their lifetime. If a key changed after insertion, its hash would change, and Python would look in the wrong slot. So immutable built-in types are hashable (str, int, float, bool, None, tuples of hashable items) and mutable ones are not:

d = {[1, 2]: "pair"}
TypeError: unhashable type: 'list'

Use a tuple instead: d[(1, 2)] = "pair". Values have no restrictions at all.

Note that string hashes are randomized per process (a security measure), so hash("alan") differs between runs. This never affects which keys a dict contains, or its iteration order, which follows insertion.

Common mistakes

Recap

Going further: read "Dictionaries" in the official tutorial (section 5.5). Then try print(globals()) at the top level of a script: the module's namespace is just a dict.

Exercises

Exercise 1 · quiz

Lookup behavior

Given ages = {"ada": 36, "alan": 41}, which expressions evaluate without raising an exception? Select all that apply.

Answer

  • ages["ada"]

  • ages.get("grace")

  • ages.get("grace", 0)

Square-bracket lookup of a missing key raises KeyError (ages["grace"], and ages[36] since 36 is a value, not a key). get returns None, or the default you supply, when the key is absent. Lookups go from key to value only; finding a key by its value needs a loop.

Exercise 2 · quiz

What can be a key?

Which of these can be used as dictionary keys? Select all that apply.

Answer

  • "name"

  • 42

  • (1, 2)

  • 3.5

Keys must be hashable: their hash value must never change, which in practice means immutable. Strings, numbers and tuples of immutable items qualify. A list can change after you insert it, which would leave it in the wrong slot of the hash table, so {[1, 2]: "x"} raises TypeError: unhashable type: 'list'.

Exercise 3 · write code

Count words

Read a single line of text and count how often each word occurs. Words are separated by whitespace; compare them case-insensitively (convert to lowercase). Print one line per distinct word, in order of first appearance, as word: count.

For input the cat and The hat and the bat:

the: 3
cat: 1
and: 2
hat: 1
bat: 1

File: main.py

Starting point

words = input().lower().split()
counts = {}

Example

input

the cat and The hat and the bat

expected output

the: 3
cat: 1
and: 2
hat: 1
bat: 1

Example

input

Go go GO

expected output

go: 3
Hint 1

counts.get(w, 0) + 1 gives the new count whether or not w was seen before.

Hint 2

Dicts remember insertion order, so for w, n in counts.items(): visits words in order of first appearance.

Reference solution
words = input().lower().split()
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1
for w, n in counts.items():
    print(f"{w}: {n}")

Exercise 4 · write code

Group by value

Define group_by_grade(grades) that takes a dict mapping student names to letter grades and returns a new dict mapping each grade to a list of names with that grade, names in the order they appear in the input:

group_by_grade({"ann": "A", "bob": "B", "cat": "A", "dan": "C"})
# {"A": ["ann", "cat"], "B": ["bob"], "C": ["dan"]}

Do not modify the input dict. An empty input gives {}.

File: solution.py

Starting point

def group_by_grade(grades):
    result = {}
    for name, grade in grades.items():
        result[grade] = name
    return result
Hint 1

Each value in the result must be a list; the first time you see a grade, create an empty list for it.

Hint 2

result.setdefault(grade, []).append(name) does both steps in one line.

Reference solution
def group_by_grade(grades):
    """Return a dict mapping each grade to the list of names with that grade."""
    result = {}
    for name, grade in grades.items():
        result.setdefault(grade, []).append(name)
    return result

Exercise 5 · write code

Inventory commands

Maintain a shop inventory (item name -> quantity) from commands, one per line, until a line end:

For this input:

add apple 5
add pear 2
remove apple 3
add fig 1
show
remove pear 5
remove kiwi 1
show
end

the output is:

apple=2 fig=1 pear=2
apple=2 fig=1

File: main.py

Starting point

stock = {}
line = input()
while line != "end":
    line = input()

Example

input

add apple 5
add pear 2
remove apple 3
add fig 1
show
remove pear 5
remove kiwi 1
show
end

expected output

apple=2 fig=1 pear=2
apple=2 fig=1

Example

input

show
add tea 1
remove tea 1
show
end

expected output

empty
empty
Hint 1

Split each line into parts; parts[0] is the command.

Hint 2

For remove: check if item in stock: first, subtract, then del stock[item] when it is 0 or less.

Hint 3

sorted(stock) gives the keys in alphabetical order. Build the strings f"{k}={stock[k]}" and join them with spaces.

Reference solution
stock = {}
line = input()
while line != "end":
    parts = line.split()
    command = parts[0]
    if command == "add":
        item, n = parts[1], int(parts[2])
        stock[item] = stock.get(item, 0) + n
    elif command == "remove":
        item, n = parts[1], int(parts[2])
        if item in stock:
            stock[item] -= n
            if stock[item] <= 0:
                del stock[item]
    elif command == "show":
        if stock:
            shown = []
            for k in sorted(stock):
                shown.append(f"{k}={stock[k]}")
            print(" ".join(shown))
        else:
            print("empty")
    line = input()