Dictionaries and Sets

Why this lesson matters

So far you have seen the list, which stores items in a row and finds them by position. That is good for “the third item” but slow for “the item named Alice.” To find something by name in a list, the computer has to walk through the items one by one until it hits a match.

Two data structures fix that. A dictionary stores pairs of things, a name and a value, and jumps straight to the value when you give it the name. A set stores a bag of unique things and answers “is this one in there?” almost instantly. Both are built into Python, and both are among the most-used tools in real code. This lesson explains what they are, how to use them, and when to reach for each.

A quick word on notation. Big-O is how we describe the speed of an operation as the data grows. O(1) means “constant time,” the work does not grow with the size of the collection. O(n) means “linear time,” the work grows in proportion to the number of items n. We will use these labels throughout.

Dictionaries

What a dictionary is

A dictionary (type name dict) is a collection of key-value pairs. A key is the label you look something up by. A value is the data stored under that label. Think of a real dictionary: the word is the key, the definition is the value. You do not scan every page; you jump to the word.

In Python you write a dictionary with curly braces {}, with each pair as key: value, separated by commas.

ages = {"Alice": 30, "Bob": 25, "Carol": 41}
print(ages)  # -> {'Alice': 30, 'Bob': 25, 'Carol': 41}

Here the keys are the strings "Alice", "Bob", "Carol", and the values are the numbers 30, 25, 41.

An empty dictionary is just {}:

empty = {}
print(empty)  # -> {}

Looking up a value

Give the dictionary a key in square brackets and it returns that key’s value.

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

This lookup is O(1) on average, meaning it takes about the same amount of time whether the dictionary holds 3 pairs or 3 million. That is the whole point of a dictionary.

If you ask for a key that is not there, Python raises a KeyError and stops:

ages = {"Alice": 30}
print(ages["Dave"])  # -> KeyError: 'Dave'

Looking up safely with `.get`

To avoid that crash, use the .get method. It returns the value if the key exists, or a default value you choose if it does not. A method is a function attached to an object; you call it with a dot.

ages = {"Alice": 30}
print(ages.get("Alice"))       # -> 30
print(ages.get("Dave"))        # -> None
print(ages.get("Dave", 0))     # -> 0

None is Python’s built-in “nothing here” value. The second argument to .get (here 0) is the fallback returned when the key is missing. Use .get whenever a missing key is a normal, expected case.

Adding and updating

Assigning to a key sets its value. If the key is new, the pair is added. If the key already exists, its value is replaced. Both are O(1) on average.

ages = {"Alice": 30}
ages["Bob"] = 25      # add a new pair
ages["Alice"] = 31    # update an existing value
print(ages)           # -> {'Alice': 31, 'Bob': 25}

There is no difference in syntax between adding and updating; the dictionary decides based on whether the key is already present.

Deleting

Remove a pair with del, or with .pop if you also want the value back.

ages = {"Alice": 31, "Bob": 25}
del ages["Bob"]
print(ages)                    # -> {'Alice': 31}

removed = ages.pop("Alice")
print(removed)                 # -> 31
print(ages)                    # -> {}

.pop also takes a default so it does not crash on a missing key: ages.pop("Dave", None) returns None instead of raising.

Checking membership

The in keyword asks whether a key is present. It checks keys only, not values, and is O(1) on average.

ages = {"Alice": 31}
print("Alice" in ages)   # -> True
print("Dave" in ages)    # -> False

Iterating

To iterate means to visit each item in turn, usually with a for loop. A dictionary lets you loop over its keys, its values, or both together.

ages = {"Alice": 31, "Bob": 25}

for name in ages:              # looping a dict gives keys
    print(name)                # -> Alice, then Bob

for age in ages.values():      # just the values
    print(age)                 # -> 31, then 25

for name, age in ages.items(): # both, as pairs
    print(name, age)           # -> Alice 31, then Bob 25

.items() hands you each pair as two variables at once. Since Python 3.7 a dictionary remembers the order in which keys were inserted, so iteration follows insertion order.

The rule about keys: they must be hashable

Not everything can be a key. A key must be hashable, which in practice means immutable, unable to change after it is created. Strings, numbers, and tuples of immutable things are fine. Lists and dictionaries are mutable, they can change, so they cannot be keys.

d = {"x": 1}          # string key: fine
d = {(1, 2): "point"} # tuple key: fine
d = {[1, 2]: "bad"}   # -> TypeError: unhashable type: 'list'

Values have no such restriction; a value can be anything, including a list or another dictionary. The rule is only about keys, and the reason comes down to how lookup actually works.

How O(1) lookup works: hashing

Here is the intuition, with the deeper mechanics left for a later lesson on hash maps.

A hash function takes a key and turns it into a number. The same key always produces the same number, and different keys usually produce different numbers. The dictionary keeps an internal array of slots and uses that number to decide which slot a key’s value lives in.

When you look up ages["Alice"], Python does not scan the pairs. It hashes "Alice" to a number, jumps directly to that slot, and reads the value. Computing the hash and jumping to a slot takes the same amount of work no matter how many pairs exist, which is why lookup, insert, and delete are all O(1) on average. Follow one key through that jump:

flowchart LR
    K["key: 'Alice'"] --> H["hash function"]
    H --> N["number, e.g. 2"]
    N --> S["slot 2 -> value 31"]

This is also why keys must be immutable. The slot is chosen from the key’s hash. If a key could change after being stored, its hash would change, and the dictionary would look in the wrong slot and fail to find the value. Immutable keys keep the hash stable, so the value stays findable.

The phrase “on average” matters. Occasionally two keys hash to the same slot, called a collision, and the dictionary does a little extra work to sort them out. In rare bad cases lookup can degrade toward O(n), but for everyday use you can rely on O(1). The hash-maps lesson covers collisions in detail.

Sets

What a set is

A set is an unordered collection of unique elements. “Unordered” means the items have no position, there is no “first” or “third.” “Unique” means duplicates are automatically discarded; a value is either in the set or it is not, never twice.

A set is like a dictionary that keeps only keys and no values. It uses the same hashing idea, so membership tests are O(1) on average. That is what a set is for: answering “is this in here?” fast, and holding a collection with no repeats.

Write a set with curly braces and bare values (no colons):

colors = {"red", "green", "blue"}
print(colors)  # -> {'blue', 'green', 'red'} (order may vary)

Because sets are unordered, the print order is not guaranteed and may differ from how you wrote it. Do not rely on it.

One trap: {} makes an empty dictionary, not an empty set. For an empty set you must use the set() function.

empty_set = set()
print(empty_set)  # -> set()

You can also build a set from a list, which is a quick way to remove duplicates:

nums = [1, 2, 2, 3, 3, 3]
print(set(nums))  # -> {1, 2, 3}

Adding, removing, and membership

s = {1, 2, 3}
s.add(4)          # add an element
print(s)          # -> {1, 2, 3, 4}

s.discard(2)      # remove if present; no error if absent
print(s)          # -> {1, 3, 4}

s.discard(99)     # not there, but this does not crash

There is also .remove, which works like .discard but raises a KeyError if the element is absent. Prefer .discard when a missing element is acceptable.

Membership uses in, and this is where sets shine. It is O(1) on average, compared with O(n) for the same check on a list.

s = {1, 2, 3}
print(2 in s)     # -> True
print(9 in s)     # -> False

If you find yourself repeatedly asking “is x in this list?”, converting the list to a set first will make each check dramatically faster.

Set operations: union, intersection, difference

Sets support the classic operations from math, each answering a common question about two collections.

a = {1, 2, 3}
b = {2, 3, 4}

print(a | b)   # union: in a OR b        -> {1, 2, 3, 4}
print(a & b)   # intersection: in a AND b -> {2, 3}
print(a - b)   # difference: in a NOT b   -> {1}

Union (|) gives every element that is in either set.
Intersection (&) gives only elements in both sets.
Difference (a - b) gives elements in a that are not in b.

Each runs in roughly O(n) where n is the size of the sets involved, and each returns a new set without changing the originals. These operations replace fiddly loops: “which users are in both groups?” is just group_a & group_b.

Set elements must be hashable for the same reason dictionary keys must be. You can put numbers, strings, and tuples in a set, but not lists.

Choosing between dict, list, and set

All three hold collections, but they answer different questions. Pick by what you need to do most.

Use a list when order and position matter and items may repeat: a sequence of steps, a queue of tasks, a log of events. Lookup by value is O(n).
Use a dict when you look things up by a key: a phone book, counts of each word, settings by name. Lookup by key is O(1) on average.
Use a set when you only care about membership and uniqueness, not order or associated data: which IDs have been seen, the distinct tags on a post. Membership is O(1) on average.

A useful test: if you keep writing if x in my_list inside a loop, a set or dict is almost certainly the better structure.

Here is one small task solved with each, to show the difference in fit. Counting how many times each word appears is a natural job for a dict:

words = ["a", "b", "a", "c", "b", "a"]
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1
print(counts)  # -> {'a': 3, 'b': 2, 'c': 1}

The .get(w, 0) gives 0 the first time a word is seen, so the running count starts cleanly. This pattern, “look up with a default, then update,” is one of the most common uses of a dictionary you will write.

Common pitfalls

{} is an empty dict, not a set. Use set() for an empty set. This bites nearly everyone once.
KeyError on missing keys. d[key] crashes if the key is absent. Use d.get(key, default) or check key in d first when a miss is expected.
Sets and dict keys lose order guarantees you might assume. A dict preserves insertion order; a set has no order at all. Never write code that depends on the iteration order of a set.
Unhashable keys and elements. You cannot use a list as a dict key or a set element. Convert it to a tuple first if the contents are fixed.
in on a dict checks keys, not values. "Alice" in ages tests the keys. To search values, use 31 in ages.values(), which is O(n).
A set removes duplicates silently. set([1, 1, 2]) is {1, 2}. That is a feature when you want unique items and a bug when you needed to keep the repeats.

Practice

Given a list of names with repeats, build a dictionary that maps each name to how many times it appears. Then print only the names that appear more than once.
You have two lists, yesterday and today, each holding user IDs who logged in on that day. Using sets, find the IDs that logged in on both days, and the IDs that logged in today but not yesterday.
Write a function that takes a list and returns True if it contains any duplicate values and False otherwise. Do it in a single pass and explain why comparing len(the_list) to len(set(the_list)) also works and what its time and space cost is.