Dicts, sets and sorted keys in Python

Why it matters

Knowing how a hash table works is half the job. The other half is using the Python types well. In everyday code you will reach for three things again and again: a dict for fast lookup, a set for "have I seen this?", and a sorted list with the bisect module when the keys must stay in order or when you need the nearest key to a value. Choosing the right one, and calling its methods without surprises, is what turns a correct idea into a working program.

This lesson is hands-on. You will read a dict as a collection of pairs, loop over it, build sets, search a sorted list, and group items without writing the same code three times. Each example runs as a complete program, so you can change it and see what happens. Read the outputs carefully, because the differences between the three types show up in them.

A dict is a lookup table of pairs

A dict stores pairs. Each pair has a key and a value. The key is the label you look things up by, and the value is the data attached to it. A phone book is a dict: the name is the key, and the number is the value. You look up "Asha" and get her number.

You write a dict with curly braces and colons, as in {"Asha": 21, "Ben": 25}, or start with an empty one with {}. Two rules define a dict. Keys are unique: a dict cannot hold two entries with the same key. Values can repeat freely. When you assign to a key that already exists, the old value is replaced, and the size stays the same.

Python has no separate map interface to declare, so the type of a dict is just dict. Type hints can describe it, as in dict[str, int] for a dict from names to ages. A type hint is a note for readers and tools. Python does not check it while the program runs.

dict: the everyday lookup table

A dict gives average O(1) time for storing and reading a value. It keeps insertion order, so loops over it visit keys in the order they were added. The table below lists the operations you will use most.

The program below uses most of them. The age dict starts with two people. It changes one value, asks for missing keys, and adds one to Ben's age.

22
None
0
True
26
2
Asha=22
Ben=26

Trace the program line by line. The first assignment stores Asha with 21. The second stores Ben with 25. The third assigns to Asha again. The key already exists, so Python replaces 21 with 22, and the dict still holds two pairs. The first print shows 22.

ages.get("Zed") finds no key Zed, so it returns None. Python's None is the value that means "nothing here". ages.get("Zed", 0) also finds no key, but it returns the default, 0. Use the default form whenever a missing key should mean a fallback value. Plain ages["Zed"] would raise KeyError instead, which is a loud error and is often the better choice when a missing key is a bug.

"Ben" in ages is True. It is the right test when you care about whether a key exists, not what its value is.

The line ages["Ben"] = ages.get("Ben", 0) + 1 is the Python way to add to a count. Read the old value or zero, add one, and store the result. Java has a merge method that does this in one call. Python has no single method for it, but the pattern is short, and collections.Counter covers the counting case later in this lesson.

The loop prints the pairs in key order. sorted(ages) returns a new list of the keys in alphabetical order, and the dict is not changed. Lesson 1 explained that a dict's insertion order is not the same as sorted order.

Looping over a dict

A dict gives you three views. d.keys() returns the keys, d.values() returns the values, and d.items() returns the pairs. Each view is linked to the dict. When the dict changes, the view shows the change.

Most loops use items(), because it gives you the key and the value at once:

for name, age in ages.items():
    print(f"{name} is {age}")

Use keys() when you only need the keys, and values() when you only need the values. For example, max(ages.values()) finds the largest value. Do not loop over the keys and then call ages[name] for each one when items() gives you both at once. The second lookup costs time and adds no information.

Views are read-only. You can loop over them and test them, but you cannot add to them or remove from them through the view. Use del, assignment, or pop on the dict itself. Lesson 11 covers what happens when you change a dict while you loop over it.

set: a collection with no duplicates

A set stores unique items with no values attached. It answers one question very quickly: "is this item in the set?" The item is the key, and there is no value beside it.

A set is built on the same kind of hash table as a dict. Each item is hashed, so in, add and remove all take average O(1) time. Lesson 1 explained what a hash is.

Python's set.add returns None, so it does not tell you whether the item was new. The check is written as two steps. You test with in first, then add. The program below removes duplicates from a list while keeping the first occurrence of each value, and then does three set operations.

unique in order: [4, 1, 2, 9]
in both: ['green']
union: ['blue', 'green', 'red', 'yellow']
only in a: ['blue', 'red']
has red? True

The loop is the standard duplicate filter. The number 4 is new the first time, so it goes into both seen and unique. The second 4 is already in seen, so the loop skips it. The list keeps the order of first appearance.

The operators &, | and - are the set operations. a & b is the intersection, the items in both. a | b is the union, the items in either. a - b is the difference, the items in a that are not in b. Each operator returns a new set, so a and b stay unchanged. Sets have no order, so the code wraps each result in sorted(...) before printing. That makes the output easy to check.

The method form a.intersection(b) does the same job as a & b, and it also accepts other iterables (anything you can loop over), such as a list. The operator form is shorter when both sides are sets.

Sorted keys with bisect

Python has no built-in sorted map. The standard way to answer order questions is to keep the keys in a sorted list and use the bisect module, which finds positions in a sorted list with binary search. Binary search takes O(log n) steps. Lesson 1 described the idea: check the middle, then throw half away, and repeat.

Here are the functions this lesson uses:

• bisect_left(keys, x) returns the position where x would go, before any equal value.
• bisect_right(keys, x) returns the position after any equal values.

With those two positions, the four nearest-key questions become one line each. The program below keeps meeting start times in a dict, sorts the keys once, and answers the questions with bisect. Times are 24-hour numbers, so 900 means 9:00 and 1700 means 17:00.

first: 900
last: 1700
floor 1200: 1030
ceiling 1200: 1400
higher 1400: 1700
lower 900: None
before 1400: {900: 'standup', 1030: 'design review'}
from 1400: {1400: 'lunch talk', 1700: 'demo'}
between: {900: 'standup', 1030: 'design review', 1400: 'lunch talk'}
entry at 1500: 1400 lunch talk

Each question asks about position in the sorted order. The names are easy to mix up, so use this list to remember them.

• keys[0] and keys[-1] are the smallest and largest keys. A negative index counts from the end.
• floor_key(x) returns the largest key that is less than or equal to x. Think of the floor as the level below you.
• ceiling_key(x) returns the smallest key that is greater than or equal to x. Think of the ceiling as the level above you.
• higher_key(x) and lower_key(x) are the same as ceiling and floor, but they exclude x itself. The line higher 1400 gives 1700, not 1400.
• The dict comprehensions for "before", "from" and "between" build a new dict from the keys in a range. They cost O(n), because they look at every key. A real sorted map would return a view in O(log n). The list version is simpler to read, and it is fast enough when the data is small.
• floor_key(1500) gives the key, and slots[f] gives the value. Python has no single call that returns both, so the code does two lookups.

Walk through floor_key(1200). The keys are 900, 1030, 1400 and 1700. bisect_right finds the position just after 1200, which is index 2. Index 1 holds 1030, so that is the floor. For ceiling_key(1200), bisect_left finds index 2 again, and the key there is 1400. For lower_key(900), bisect_left returns index 0, which has nothing before it, so the function returns None. A None result is the normal way these functions say "nothing there", so check for it when the question can have no answer.

The keys must be comparable. Numbers and strings compare with < already. A class you write must define comparison methods, or you must pass a key function to sorted. The sorting module in this course covers key functions.

To keep a sorted list up to date when keys arrive, use bisect.insort(keys, new_key). It finds the position and inserts the key in one call. Inserting into the middle of a Python list costs O(n), because the items after the position move one place. For a few thousand keys that is fast. For millions of inserts, use a different data structure.

Choosing the right container

Here is a short decision guide. Start at the top and stop at the first line that matches your need.

A dict keeps insertion order, so the usual choice is dict, not an ordered structure. A set does not keep order. When you need unique items in the order they first appeared, use dict.fromkeys, which builds a dict whose keys are the items in order. The next program shows it.

['b', 'a']

In an interview, state the choice and the reason in one sentence. For example: "I need the closest price below a budget, so I keep the prices in a sorted list and use bisect_right to find the floor in O(log n), while a dict would need a full scan." That sentence shows you understand both the need and the cost.

Grouping items with defaultdict

A very common pattern is to group items under a key. You want a list of words for each first letter, or a list of orders for each customer. The naive code checks whether the key exists, creates a list if it does not, and then adds to the list. Python gives you a shorter way: collections.defaultdict. You give it a function that makes a default value, such as list. When you read a missing key, it calls that function, stores the result, and returns it.

{'a': ['apple', 'avocado', 'apricot'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}
{'a': 3, 'b': 2, 'c': 1}
Counter({'a': 3, 'b': 2, 'c': 1})

Read the first loop in plain words. For each word, take its first letter. The first time a letter appears, by_letter[letter] is missing, so defaultdict creates an empty list. Then .append(w) adds the word to that list. The next words that start with the same letter find the list already there.

The second part uses Counter. Give it any iterable, and it counts how many times each item appears. Counter is a dict subclass, so it has the same lookup methods, and a missing key counts as 0. The printed form of a Counter shows its class name, so the program sorts it into a plain dict first to match the other output.

Use defaultdict(list) when each key needs a collection, and Counter when each key needs a number. Both replace an if statement and an assignment with one step. They also make the intent clearer: you are grouping or counting, not checking the dict by hand.

Reading input and counting words

Programs in this course can read input with input(). It reads one line from the input box as a string, without the newline at the end. To read a number, convert the string with int(). To read the words in a line, call split(), which splits on spaces.

The program below counts words, one per line of input. Words are compared without case, so Banana and banana count as the same word. The counts are stored in a dict, and the output is sorted alphabetically. The first line holds how many words follow.

n = int(input())
counts = {}
for _ in range(n):
    word = input().strip().lower()
    counts[word] = counts.get(word, 0) + 1
 
for word in sorted(counts):
    print(word, counts[word])
print("distinct:", len(counts))

Feed it this input, one line at a time. The first line is 3. The next three lines are apple, Banana and apple.

apple 2
banana 1
distinct: 2

The program reads three lines, one per word. strip() removes spaces at both ends, and lower() turns each word into lowercase before counting. counts.get(word, 0) + 1 adds one to the count, starting from zero for a new word. The sorted loop prints the keys in alphabetical order, and len(counts) counts the distinct words, not the total number of lines.

Change the input and predict the output before you run it. If the words repeat, the count for the repeated word goes up and the distinct count stays the same. Predicting the output is the best way to find out whether you understand a program.

Trace a word count step by step

Counting is the most common use of a dict, so it is worth following one count slowly. Take the sentence the cat and the dog and the cat. It has eight words. Start with an empty dict and do the same step for each word. The table shows the dict after each step.

Each step is one of two cases. Either the key is new and the code stores 1, or the key exists and the code adds 1 to the old count. The get(word, 0) + 1 form handles both cases in one line. The same two cases apply to any counting job, whether the keys are words, letters, customer ids or error codes.

The final counts are the=3, cat=2, and=2 and dog=1. Check the total: the counts add up to 8, which is the number of words. That check is worth making in your own code. If the total of the counts is not the number of items you read, a key is being split or a count is being replaced when it should be added.

Changing a dict through its views

Views do not copy the dict. Removing a key from the dict removes it from every view. Python's views are read-only, so you remove through the dict itself. The program below removes zero-valued entries safely, and it shows the error you get when you try to change a view.

{'a': 1, 'c': 5}
{'a': 1}

The loop is over list(scores), which is a copy of the keys. Deleting from the dict while looping over the dict itself raises an error, so the copy is what makes the loop safe. The second line builds a new dict that keeps only the non-zero values. Use a comprehension like that when you want a filtered copy and the original can stay as it is.

Views cannot be changed. The next program shows the error that comes from trying.

AttributeError: 'dict_keys' object has no attribute 'add'

The rule is simple: use d[key] = value or del d[key] to change a dict, and use the views only to read.

When a sorted list is the wrong choice

A sorted list with bisect is a good tool, but it is not the default. Inserting a key into the middle of a list costs O(n), because the later items move. A dict insert costs average O(1). If you only count and never need the order, use a dict and sort the keys once at the end. Sorting costs O(k log k) for k distinct keys, and the count loop stays at average O(1) per word. A sorted list is the right choice when the order is needed during the work, such as when you ask for the nearest key again and again and the keys do not change often.

Another reason to avoid a sorted list is the key type. Every key must be comparable with the others. A class with no comparison methods cannot be sorted, and sorted raises a TypeError when it meets two items it cannot compare. A dict only needs == and hash, so it accepts a wider range of keys.

Reading the printed form

When you print a dict or a set, Python uses a fixed format, and it helps to know it. A dict prints inside curly braces, with 'key': value pairs separated by commas, such as {'and': 2, 'cat': 2}. A set also uses curly braces, but its items have no colons, such as {1, 17, 3}. An empty set prints as set(), because {} is an empty dict. A list prints in square brackets.

Printed sets are not in a reliable order. The same items can print in a different order when the table size changes. Use sorted(...) before printing when you need a fixed order, as the examples in this lesson do.

Returning dicts and sets from functions

When a function builds a dict and returns it, decide who may change it afterwards. If you return your internal dict directly, the caller can add or remove entries and break your code's assumptions. A safer choice is to return a copy with dict(counts) or counts.copy(), or to return a read-only view with types.MappingProxyType(counts). For sets, frozenset(seen) returns an immutable copy that has no add method.

frozenset [1, 2, 3]
AttributeError: 'frozenset' object has no attribute 'add'

Use the same thinking for sets. Return frozenset(seen) when the caller only needs to read the set, and keep the mutable version for your own loop. These habits are small, but they are the difference between code that is easy to reuse and code that breaks when someone adds a new call.

Errors you will meet, and what they mean

These containers fail in a small set of ways. Learn the messages once and you will recognise them quickly.

Adding a number to a missing value. d.get(key) returns None when the key is missing. Arithmetic on None raises TypeError:

scores = {"ana": 90}
print(scores.get("bo") + 5)

TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

The message names NoneType, which is the type of None. The fix is a default value: scores.get("bo", 0) + 5.

Changing a dict or set while looping over it. Adding or removing items during a for loop over the dict or set changes its size. Python detects this on the next step of the loop and raises RuntimeError. The dict version looks like this:

d = {"a": 1, "b": 0}
for name in d:
    if d[name] == 0:
        del d[name]

RuntimeError: dictionary changed size during iteration

The set version raises RuntimeError: Set changed size during iteration. The fix is the one from the section on changing a dict: loop over list(d) or build a new dict.

Comparing values that cannot be ordered. sorted needs every pair of items to be comparable. Mixing None with numbers fails:

print(sorted([3, None, 1]))

TypeError: '<' not supported between instances of 'NoneType' and 'int'

Remove the None values first, or use a key function that gives every item a comparable value.

Using a mutable key. A list cannot be a dict key, because lists can change. The error names the type:

try:
    counts = {[1, 2]: 0}
except TypeError as error:
    print("TypeError:", error)

TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

Use a tuple instead, as in {(1, 2): 0}. A tuple of numbers and strings is hashable.

Comparing numbers with is. is checks whether two names refer to the same object. Two equal numbers are not always the same object. CPython keeps shared objects only for small integers from -5 to 256, so is can look right for small numbers and fail for large ones:

True False

Use == to compare values. Use is None for the one check where None is the right answer.

Edge cases

An empty input line gives an empty dict and an empty set. Loops over them do nothing, and len returns 0. A dict with one entry still needs get with a default for missing keys. A frozenset cannot change, so calling add on it raises AttributeError. Build a set(...) first when you plan to change it.

Two sets are equal when they contain the same items, regardless of order. Two dicts are equal when they hold the same pairs, regardless of insertion order. Both comparisons use ==. This is why {1, 2} == {2, 1} is True.

A set of lists does not work, because lists cannot be hashed. Convert each list to a tuple first, as in set(tuple(row) for row in rows).

Also note the empty-brace trap. {} is an empty dict, not an empty set. Write set() for an empty set. The program below shows the difference.

<class 'dict'> <class 'set'>

Interview angle: pick the structure from the question

Interviewers often describe a problem in words and wait to see which structure you choose. Read the question for its key verbs. "Have I seen" points to a set. "Count how many times" points to a Counter or a dict with get. "Group by" points to defaultdict(list). "Closest value below" or "in sorted order" points to a sorted list with bisect. "Remove the oldest" points to a queue, which lesson 4 uses.

After you pick, say the complexity. A dict gives average O(1) per operation, a sorted list with bisect gives O(log n) for a search and O(n) for an insert, and a plain list scan gives O(n). A good answer includes the reason for the choice. "I used a sorted list because the question asks for the nearest key, and bisect answers that in O(log n)" is much stronger than "I used a dict".

Real-world uses

Web frameworks use dicts for request headers and query parameters. Crawlers use sets to track visited URLs, so the same page is not fetched twice. A shop uses a sorted list with bisect to find the price tier just below a given order size. A calendar app keeps event start times in a sorted list to find the next event. A log analyser groups lines by user with defaultdict(list). Each of these uses the same small set of tools you practised here.

Practice

Try each exercise before you open its answer. Use paper for the traces, and check your answers with a short program.

1. Write a program that reads five words and prints each distinct word once, in the order it first appeared. Use a set. Hint: check with in before you add.

Show the answer

seen = set()
for w in ["b", "a", "b", "c", "a"]:
    if w not in seen:
        seen.add(w)
        print(w)

The program prints b, a and c, one per line. Replace the list with five words read from input() to finish the exercise.

2. Using the meeting times from the example, what does floor_key(5) return? Hint: nothing is at most 5.

Show the answer

None. bisect_right returns 0 for 5, so there is no index before it, and the function returns None.

3. Explain when you would pick a dict over a set, and when a set is the better tool, in two sentences. Hint: think about whether each item needs a value.

Show the answer

Pick a dict when each key needs a value next to it, such as a name and a score. Pick a set when you only need to know whether an item is present, because a set stores the item alone and in checks it in average O(1) time.

4. Write code that counts how many times each letter appears in the string hello and prints the counts in alphabetical order. Hint: Counter and sorted.

Show the answer

{'e': 1, 'h': 1, 'l': 2, 'o': 1}

5. Given a dict of scores, print the names of everyone with a score above 50, in alphabetical order. Hint: loop over items() and sort the names.

Show the answer

scores = {"Ana": 72, "Bo": 40, "Chen": 88}
for name in sorted(n for n, s in scores.items() if s > 50):
    print(name)

The program prints Ana and then Chen.

6. Write a function that returns True when two lists contain the same set of numbers, ignoring duplicates. Hint: compare two sets.

Show the answer

True
False

7. A sorted list of times holds 800, 1200 and 1800. Write the calls that return the time closest to 1000 from below and from above. Hint: floor_key and ceiling_key.

Show the answer

floor_key(1000) returns 800, because 800 is the largest key at most 1000. ceiling_key(1000) returns 1200, the smallest key at least 1000.

8. Predict the output of print({3, 1}.add(3)). Then explain why.

Show the answer

The output is None. set.add changes the set in place and returns None. The item 3 is already present, so the set does not change, and the print shows the return value, which is None.

9. Explain why a dict accepts a None key, but sorted fails when a list contains None next to numbers. Hint: think about what each operation must do with the key.

Show the answer

A dict only needs the key's hash and ==, and None has both. sorted must compare each item with the others using <, and None cannot be compared with a number, so sorted raises TypeError.

10. Write a function group_by_length(words) that groups words by their length, using defaultdict(list). Hint: the key is len(w).

Show the answer

{1: ['a', 'd'], 2: ['bb', 'cc']}

What you now know

• A dict stores key-value pairs with unique keys, and get with a default is the safe way to read a value that may be missing.
• defaultdict and Counter replace most manual checks in counting and grouping code.
• Looping over items() gives keys and values together, and list(d) lets you delete while you loop.
• A set answers "have I seen this?" with in, and the operators &, | and - combine sets.
• A sorted list with bisect answers nearest-key questions in O(log n) per call.
• Reading a missing key from a dict raises KeyError with [], and returns None with get. Changing a dict while looping over it raises RuntimeError.

The next lesson applies these tools to three classic problems: two sum, frequency counting and subarray sums. Each of them turns a slow nested loop into a single pass with a dict.