Lecture notes · Programming in Python · Lecture 14

Dictionaries

MIT 6.100L Intro to CS and Programming using Python, lecture 14, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part explains why storing student data in separate lists gets messy, which sets up the need for a new kind of data structure called a dictionary.

Key ideas

The lecture introduces Python dictionaries as a new compound data type, which means it can hold several pieces of data together, like lists and tuples. It is not the same as a paper dictionary. 0:11
One way to store student data is with separate lists, one for names and one for grades. A student's grade is found by matching their position, or index, in the name list to the same index in the grade list. 1:15
Separate lists get messy fast. You have to pass many lists into functions, and when a student joins or leaves, you must update every list at the same index. 4:49
A better idea is one master list. Each student is a sublist that holds the student's name, problem set grades, and micro quiz grades together. 5:32
Even the master list is hard to work with. Finding a student's grades takes nested loops, which are loops placed inside other loops, so the lecture says you do not need to understand that function well. 7:17

Words to know

compound data type: A container that holds more than one piece of data at once, such as a list, a tuple, or a dictionary.
mutable: Able to be changed after it is made. Lists are mutable, so you can add, remove, or change items in them.
index: The position number of an item in a list. The first item is at index 0.
nested for loop: A loop that sits inside another loop, so the inner loop runs fully for each step of the outer loop.

Example

The lesson's own example: Ana's name is at index 0 in the name list, so her grade is at index 0 in the grade list. If Ana drops the class, you have to remove her from the name list and from the grade list, and from every other list you keep, or the lists will no longer line up.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part introduces dictionaries, which store pairs of a key and a value so you can look up a value by its key.

Key ideas

A dictionary maps a custom index, called a key, to a value. It works like a book dictionary, which maps a word to its definition. 10:40
Each key-and-value pair in a dictionary is called an entry. A list is like a dictionary whose keys are always the numbers 0, 1, 2, and so on, in order. 11:01
Keys must be immutable, which means they cannot be changed after they are created. Values can be any kind of object, even lists or other dictionaries. 13:52
You create a dictionary with curly braces, and you look up a value by putting its key in square brackets. If the key is not there, Python raises a KeyError. 17:32
You cannot look up a key from a value in one step, because values can repeat. You would need a loop that checks each entry. 18:39

Words to know

key: The custom label you use to find something in a dictionary, like a name or a word.
entry: One item in a dictionary, made of a key paired with its value.
immutable: Something that cannot be changed after it is made, such as a string or a number.
KeyError: The error Python shows when you try to look up a key that is not in the dictionary.

Example

Think of a phone contact list where each name is linked to a phone number. The name is the key, and the number is the value. If you look up a name that is not in your contacts, your phone shows an error, just like Python does with a KeyError.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part shows how to look up, add, change, and delete entries in a dictionary, and how to check whether a key exists.

Key ideas

To get a value from a dictionary, you put the key in square brackets, such as grade[name]. You do not need a loop for this, because it is one line of code. 21:45
Writing a new key into a dictionary adds it, even if the key was not there before. Writing to a key that already exists replaces its old value. 23:59
Del removes an entry from a dictionary. Adding, changing, and deleting all change the original dictionary itself, not a copy. 25:49
The in keyword checks only the keys of a dictionary, not its values. So a value that is stored in the dictionary still gives False for in. 26:35
In the find_in_L exercise, you loop over the list of dictionaries and check each one with k in d. As soon as you find a match, you can return True right away. 29:56

Words to know

key: The label you use to find a value in a dictionary, like a name that points to a grade.
mutate: To change something in place, so the original is changed instead of making a new copy.
iterate: To go through items one by one, usually with a loop.
del: A keyword that removes an entry from a dictionary or an item from a list.

Example

Think of a phone's contact list. The name is the key, and the phone number is the value. You look up a number by typing the name, you add a new name to the list, and you can erase a name, and each of these changes the same contact list.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part shows how to look at every entry in a dictionary, and why you should never count on the entries being in any particular order.

Key ideas

A search function can return true as soon as it finds the key, because that ends the loop early. It should return false only after checking every dictionary, so it knows the key is really missing. 30:20
Dictionaries have no order you can rely on. Older Python versions gave no guaranteed order, so good code should assume there is none. 33:13
The keys() and values() functions return a sequence of all the keys or all the values. They do not change the dictionary. 33:35
The items() function gives you each key and value together. Using 'for k, v in grades.items()' lets you work with both at once on each pass through the loop. 38:19
The results of keys(), values(), and items() are iterables, which you can loop over. You can turn them into a list if that makes them easier to read, but you don't have to. 34:17

Words to know

iterable: Something you can loop through one item at a time, such as a list or the result of keys().
tuple: A small group of values held together in order, written with parentheses, such as (key, value).
mutate: To change something in place. keys() and values() do not mutate the dictionary, so the dictionary stays the same after you call them.
cast: To convert one type of data into another, such as turning the result of keys() into a list.

Example

Think of a shelf of labeled boxes, where each label is a key and each box holds a value. You can read all the labels, look at all the box contents, or go through each box with its label together. Looking does not move or change any box, and the boxes are not necessarily lined up in a set order.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part explains how to count matching keys and values in a dictionary, how copying and aliasing work with dictionaries, what kinds of keys and values are allowed, and why keys must be unchangeable.

Key ideas

To count entries where the key equals the value, loop through the dictionary with items(), so you get each key and value together. Add 1 to a counter each time they match. 41:05
A dictionary is a mutable object, so the same copying rules as lists apply. Writing D1 = D2 makes an alias, meaning both names point to the same dictionary. Use d.copy() if you want a separate copy you can change safely. 43:41
Dictionary values can be almost any type, and more than one key can have the same value. Keys are different: each key must be unique. 44:45
Keys must also be unchangeable (immutable). For this class, that means int, float, string, tuple, or bool. Lists and dictionaries cannot be keys. 45:33
Python stores a dictionary entry by running a hash function on the key. The hash function turns the key into a number that acts like a memory location for the value. If a key could change, its hash number could change too, and Python would lose track of the value. 47:22

Words to know

alias: A second name that points to the same object. If you change the object through one name, the change shows up through the other name too.
immutable: Something that cannot be changed after it is made. Numbers, strings, and tuples are examples in this lesson.
hashable: The lesson says keys must be hashable, which means Python can run a hash function on them. For this class, you can think of it as the same as immutable.
hash function: A function that takes in a key and turns it into a number. Python uses that number to decide where to store the value.

Example

Think of a coat check where each coat gets a numbered hook based on the name on the ticket. If the name on the ticket changed after you hung the coat, the attendant would look at the wrong hook and not find your coat. That is why a dictionary key must stay the same once it is stored.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–1:00:00

This part explains why dictionary keys must be unchangeable, how to look up nested data in a dictionary, and how to collect values into one flat list.

Key ideas

A dictionary finds a value by running a hash function on its key, which gives a memory location. If the key changes, the hash function can point somewhere else, so the value cannot be found. That is why keys must be unchangeable. 51:28
A dictionary can hold other dictionaries as values, so one dictionary can hold a whole class: each student's name is a key, and that student's data is a dictionary. 52:57
A chain like grades[name]["mq"][0] is read left to right. Each step replaces the box with what it finds, until you reach a single score. 54:42
To gather scores from many students into one flat list, use concatenation with plus. Appending a list adds the whole list as a single item, which is not what you want. 59:26

Words to know

hash function: A rule that turns a key into a memory location, so the computer knows where to store or find the value for that key.
mutable: Able to be changed after it is created. A list is mutable, so its contents can change.
dictionary: A collection that stores pairs of a key and a value, so you can look up a value by its key, like finding a word's meaning in a real dictionary.
concatenate: To join two things end to end. With lists, plus joins the items of one list onto another.

Example

Think of a coat check where each coat gets a ticket number based on the name on the tag. If the name on the tag changes later, the attendant looks in the wrong spot and cannot find the coat. That is why a dictionary key must stay the same.

3 checked practice questions for this part are in the app.

Part 7 · 1:00:00–1:10:00

This part explains how dictionaries store data by key, and starts building a program that counts how often each word appears in a song.

Key ideas

A list uses numbered positions (index 0, 1, 2) that have a set order. A dictionary uses keys instead, and the keys have no set order. 1:00:44
Keys in a dictionary can be almost anything, but they cannot be immutable or hashable in the way the lesson describes. The values stored under each key can be any type, just like items in a list. 1:01:04
The lecture's big example is a program that finds the most common words in a song's lyrics. It is split into three smaller pieces, and the first piece is a frequency dictionary that maps each word to how often it appears. 1:04:20
To build the frequency dictionary, the function makes all the letters lowercase, splits the text into a list of words, and then loops through that list. If a word is already a key, its count goes up by 1. If not, it is added with a count of 1. 1:07:12
Lowercasing matters because capital T-H-E and lowercase t-h-e should count as the same word. The Python Tutor walkthrough shows the dictionary filling up one word at a time. 1:06:51

Words to know

key: The label you use to look up something in a dictionary, like a word that points to its count.
hashable: A type of value that Python can use as a dictionary key. The lesson says keys cannot be immutable or hashable in the way it describes, so the rule matters when choosing keys.
split: A function that cuts a string into pieces. By default it cuts at each space, so a sentence becomes a list of words.
frequency dictionary: A dictionary that maps each word to the number of times it appears in the text.

Example

Imagine a party where every guest wears a name tag, and you want to count how many times each name shows up on the guest list. You keep a notebook with each name written down, and each time you see a name again, you add one tally next to it. That notebook is like a frequency dictionary: the names are the keys and the tallies are the values.

3 checked practice questions for this part are in the app.

Part 8 · 1:10:00–1:17:59

This part shows how to find the most frequent words in a frequency dictionary, then repeatedly remove those words to find the next most frequent group.

Key ideas

The most frequent word is the one with the highest value in the dictionary. The computer uses the values function to get all the values, and the max function to find the biggest one. 1:10:18
The function then loops through each entry and collects every word whose value matches the highest value. There can be more than one such word, so the function keeps them all in a list and returns that list with the highest value. 1:11:20
To find the next group, the lecturer deletes the top words from the dictionary. Then the same function, run again, finds the next highest frequency. 1:14:16
The loop keeps going only while the highest remaining frequency is at least x. Once the frequencies fall below x, the loop stops and the collected groups are the answer. 1:15:40
This method uses mutation, which means changing the dictionary itself with the del keyword. It also reuses a function that was already written, so the work is not repeated from scratch. 1:16:42

Words to know

mutation: Changing an object, such as a dictionary, in place instead of making a new copy.
tuple: A group of values held together in one object, written with commas and sometimes parentheses. Here, the function returns a tuple holding a list of words and a number.
del keyword: A Python word that removes an entry from a dictionary. Using it changes the original dictionary.
items: A dictionary tool that lets you loop through each key and value pair, one pair at a time.

Example

Think of a box of tally cards, where each card has a word and a count. To find the most common words, you pick out all the cards with the biggest count, set them aside, and then look again at the cards that are left. Each time you set aside a group, the next biggest count is the new top group.

3 checked practice questions for this part are in the app.

← Lecture 13: Exceptions and Assertions · Lecture 15: Recursion →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York