Fluent Python

Chapter 3. Dictionaries and Sets

Any running Python program has many dictionaries active at the same time, even if the user’s program code doesn’t explicitly use a dictionary.

A. M. Kuchling, “Python’s Dictionary Implementation: Being All Things to All People”¹

The dict type is not only widely used in our programs but also a fundamental part of the Python implementation. Module namespaces, class and instance attributes, and function keyword arguments are some of the fundamental constructs where dictionaries are deployed. The built-in functions live in __builtins__.__dict__.

Because of their crucial role, Python dicts are highly optimized. Hash tables are the engines behind Python’s high-performance dicts.

We also cover sets in this chapter because they are implemented with hash tables as well. Knowing how a hash table works is key to making the most of dictionaries and sets.

Here is a brief outline of this chapter:

• Common dictionary methods

• Special handling for missing keys

• Variations of dict in the standard library

• The set and frozenset types

• How hash tables work

• Implications of hash tables (key type limitations, unpredictable ordering, etc.)

Generic Mapping Types

The collections.abc module provides the Mapping and MutableMapping ABCs to formalize the interfaces of dict and similar types (in Python 2.6 to 3.2, these classes are imported from the collections module, and not from collections.abc). See Figure 3-1.

Figure 3-1. UML class diagram for the MutableMapping ...