Iteration order and changing a dict in a loop

Why this matters

Most programs loop over a dict. They print every entry, add up the values, or remove the ones they do not need. Two things need care in this work. The first is the order the loop visits the entries. The second is an error that appears when the dict is changed while the loop is still running. Both come from how a dict and a set are built, and both can be handled with a few simple habits.

This lesson uses small programs and shows the real output of each one. You will see which orders Python promises, which orders it does not, and what Python does when a loop and a change collide. The lesson on custom keys in this module explains why a key must be found reliably. This one covers what the loop does with the entries it finds.

Dict order is insertion order

Since Python 3.7, a dict keeps its keys in the order they were added. The language promises this, so you can rely on it. The program below adds the same three keys to two dicts in different orders, and prints each dict's keys.

dict order A: ['banana', 'apple', 'cherry']
dict order B: ['cherry', 'apple', 'banana']
keys added from 9 down to 0: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Order A and order B hold the same keys, and each loop visits them in its own insertion order. The dict does not sort anything, and it does not reorder keys when you add more of them. This is the behaviour you should expect from a dict, and the examples in the rest of this lesson rely on it.

Set order is not a promise

A set is different. A set is built on a hash table (a row of slots, where each value's hash picks its slot), and it does not promise any order. Its loop order depends on where each value lands in the table, and that position comes from the value's hash. The next program prints a set of integers, a sorted copy of the same set, and a set of strings.

set of ints 100, 17, 33: {17, 100, 33}
sorted copy: [17, 33, 100]
set of ints 16 and 1: [16, 1]
set of strings: ['apple', 'cherry', 'banana']

The set of integers did not print in the order it was written, and it did not print in sorted order. The order came from the positions of the values in the table. The hash of a small integer is the integer itself, so a set of small numbers often looks sorted. That is a coincidence of the table size, not a rule.

The set of strings can print in a different order from one run of Python to the next. Python adds a random seed to string hashes each time the interpreter starts, so the positions change. Run the last line twice and compare the output. The same program can print two different orders, and both are correct. The output block above is one of those runs.

Where the order comes from

A dict and a set keep their entries in a table of slots. When you add a key, Python computes its hash value and uses it to pick a slot. If the slot is already taken, Python probes for another free slot in a fixed pattern. When you loop, Python walks the table from the first slot to the last.

For a dict, the entries also keep a separate list in insertion order, and the loop uses that list. That is why the dict order is stable. For a set there is no such list. The loop walks the slots, so the order depends on the hashes and on the table size.

The table can grow. A dict or a set starts with a small table, and when it holds too many entries it builds a bigger table and places every key again. After the change, a key may sit in a different slot. So a set with the same values can loop in a different order after it grows.

You do not need to track these numbers to write correct code. The point is that the loop order of a set is a side effect of how the table looks now. It is not a rule the set keeps.

What to do when order matters

When the output order matters, pick a structure whose order is a promise, or sort before you print:

• A dict keeps insertion order, so use a dict when you need the order the items were added.
• sorted(...) returns the items in sorted order, and it does not change the original. Use it on any dict or set before printing.
• A dict built from sorted keys keeps that sorted order, for example dict(sorted(scores.items())).

Do not write a test that compares the printed text of a set with a fixed string. Compare sets with ==, which ignores the order, or sort the items before you compare.

What a loop over a dict is doing

A for loop over a dict uses an iterator. An iterator is an object that remembers where the loop is and gives the next key when asked. Think of it as a bookmark in a book. The bookmark works as long as the pages stay where they are.

A dict counts its changes in size. Each iterator remembers the size of the dict when the loop started. Before it gives the next key, it compares its saved size with the dict's current size. If they differ, the dict has changed under the iterator, and the iterator raises RuntimeError. This is Python's way of saying that the bookmark is no longer trustworthy.

The next program shows the three cases. The first loop removes an entry while it is still looping. The second loop removes the only entry. The third loop adds a key to the dict while it loops over it.

RuntimeError: dictionary changed size during iteration
single key RuntimeError: dictionary changed size during iteration
add RuntimeError: dictionary changed size during iteration

The first loop removes ben, which is the second key. The next step of the loop sees that the size changed, and it raises RuntimeError. The message says what happened: the dictionary changed its size during the iteration.

A removal that looks fine in Java does not work in Python

In Java, removing the last key during a loop can finish without an error, because the iterator stops before it checks the count again. That is luck, and it depends on which key comes last. Python does not work that way. The iterator checks the size before it gives each key, including the step after the last removal. The second case in the program above shows this: the only key is removed, and the next step still raises RuntimeError.

So Python gives the same error in every case, and it gives it on the first run. That is better than the Java behaviour, because the bug does not hide until a particular key comes last.

Changing a value is allowed

Replacing the value of a key that already exists does not change the size of the dict. The loop does not fail, and the new value is visible right away. The next program doubles each value while it loops over the keys. The keys stay the same.

value change in loop: {'ann': 20, 'ben': 0, 'cy': 14}

The loop only reads and updates existing keys, so the size never changes. Assigning to a new key or deleting a key is what breaks the loop.

Safe ways to change a dict in a loop

There are four common ways to remove entries without an error. Each one is shown in the program below, with the output after it.

The first is to loop over a copy of the keys. list(d) makes a new list of the keys. The loop walks the list, and the removal changes the dict, not the list, so the loop is safe.

The second is to build a new dict with a comprehension. The new dict keeps only the entries you want, and the old dict is not changed while you read it.

The third is to collect the keys to remove in a list while you loop, and then delete them after the loop has finished.

The fourth is pop, which removes one key and returns its value. Call it on the dict between loops, not inside a loop over the same dict.

loop over a copy: {'ann': 10, 'cy': 7}
comprehension: {'ann': 10, 'cy': 7}
collect, then delete: {'ann': 10, 'cy': 7}
pop: 0 {'ann': 10, 'cy': 7}

Each version gives the same final dict. The comprehension is the shortest, and most code should use it when it only needs a filtered copy. The copy approach costs extra memory for the list, which is fine for small dicts, and it is the easiest one to read for a beginner. Use pop when you want the removed value.

Common mistakes

Deleting inside a for loop over the same dict

The most common mistake is writing del d[k] inside for k in d:. It raises RuntimeError on the next step of the loop. The fix is one of the four methods in the section above, most often a comprehension.

Adding keys inside the loop

Adding a key to the dict that you are looping over raises the same error, as the third case in the program above shows. If the loop needs to create new keys, collect them in a separate dict or list, and add them after the loop finishes.

Comparing the printed text of a set

A test that compares str(s) with a fixed string depends on the set's order. It can pass today and fail after a change to the set's size or to its values. Compare sets with ==, or sort the items before you print them.

Relying on the order of a set

A function that returns list(some_set) gives a list whose order is not promised. If the order matters to a caller, return sorted(some_set) instead.

Practice

Try each exercise before you open its answer. Use the programs above to check your reasoning.

Exercise 1. A dict gets the keys apple, cherry and banana in that order, with the values 1, 2 and 3. What order does its loop visit the keys in? Give the reason.

Show the answer

It visits them in insertion order: apple, cherry, banana. A dict keeps the order the keys were added, and this is a promise of the language. The program below prints the order.

['apple', 'cherry', 'banana']

Exercise 2. Write code that removes every entry whose value is less than 5 from m, without an error. Then print the dict in sorted order by key.

Show the answer

Build a new dict with a comprehension, then sort the items by key when you print.

{'b': 7, 'd': 9}

Exercise 3. This loop is meant to remove every key that starts with tmp. It fails. Rewrite it so that it works.

for k in d:
    if k.startswith("tmp"):
        del d[k]

Show the answer

Loop over a list of the matching keys, and delete them after the list is built. The list is a copy, so the dict can change while the loop walks the list.

{'keep': 2}

Exercise 4. A set of integers holds 16 and 1. Does its loop visit 16 first or 1 first? Why does the answer not come from insertion order?

Show the answer

It visits 16 first, and the program below prints that order. A set does not keep insertion order, so the answer comes from the table. The value 16 is in slot 0 of an 8-slot table, and 1 is in slot 1. The loop walks the slots in order. The example is a coincidence of the table size, so do not rely on it.

[16, 1]

Exercise 5. Explain in plain words why changing a value inside a for loop over a dict does not raise an error, but deleting a key inside the same loop does.

Show the answer

Changing a value keeps the number of keys the same, so the dict's size does not change, and the iterator's saved size still matches. Deleting a key changes the size. The iterator sees that the size no longer matches the one it saved, and it raises RuntimeError on its next step.

Summary

• A dict keeps insertion order, and you can rely on it.
• A set does not promise any order. Its loop order depends on the slots the values landed in, and for strings it can change from one run of Python to the next.
• Use sorted(...) before printing when the order matters, and compare sets with ==.
• Deleting or adding a key inside a for loop over the same dict raises RuntimeError, every time.
• Use a comprehension, a loop over list(d), a list of keys to delete later, or pop.
• Changing the value of an existing key inside the loop is safe.