Since Python 2.7, the syntax of listcomps and genexps was adapted to dict comprehensions (and set comprehensions as well, which we’ll soon visit). A dictcomp (dict comprehension) builds a dict instance by taking key:value pairs from any iterable. Example 3-1 shows the use of dict comprehensions to build two dictionaries from the same list of tuples.

>>> dial_codes = [                                                  
...     (880, 'Bangladesh'),
...     (55,  'Brazil'),
...     (86,  'China'),
...     (91,  'India'),
...     (62,  'Indonesia'),
...     (81,  'Japan'),
...     (234, 'Nigeria'),
...     (92,  'Pakistan'),
...     (7,   'Russia'),
...     (1,   'United States'),
... ]
>>> country_dial = {country: code for code, country in dial_codes}  
>>> country_dial
{'Bangladesh': 880, 'Brazil': 55, 'China': 86, 'India': 91, 'Indonesia': 62,
'Japan': 81, 'Nigeria': 234, 'Pakistan': 92, 'Russia': 7, 'United States': 1}
>>> {code: country.upper()                                          
...     for country, code in sorted(country_dial.items())
...     if code < 70}
{55: 'BRAZIL', 62: 'INDONESIA', 7: 'RUSSIA', 1: 'UNITED STATES'}

An iterable of key-value pairs like dial_codes can be passed directly to the dict constructor, but…

…here we swap the pairs: country is the key, and code is the value.

Sorting country_dial by name, reversing the pairs again, uppercasing values, and filtering items with code < 70.

If you’re used to listcomps, dictcomps are a natural next step. If you aren’t, the spread of the comprehension syntax means it’s now more profitable than ever to become fluent in it.

Python 3.9 supports using | and |= to merge mappings. This makes sense, since these are also the set union operators.

>>> d1 = {'a': 1, 'b': 3}
>>> d2 = {'a': 2, 'b': 4, 'c': 6}
>>> d1 | d2
{'a': 2, 'b': 4, 'c': 6}

Usually the type of the new mapping will be the same as the type of the left operand—d1 in the example—but it can be the type of the second operand if user-defined types are involved, according to the operator overloading rules we explore in Chapter 16.

To update an existing mapping in place, use |=. Continuing from the previous example, d1 was not changed, but now it is:

>>> d1
{'a': 1, 'b': 3}
>>> d1 |= d2
>>> d1
{'a': 2, 'b': 4, 'c': 6}

Now let’s see how pattern matching applies to mappings.

Here is part of the definition of hashable adapted from the Python Glossary:

An object is hashable if it has a hash code which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() method). Hashable objects which compare equal must have the same hash code.²

Numeric types and flat immutable types str and bytes are all hashable. Container types are hashable if they are immutable and all contained objects are also hashable. A frozenset is always hashable, because every element it contains must be hashable by definition. A tuple is hashable only if all its items are hashable. See tuples tt, tl, and tf:

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> tf = (1, 2, frozenset([30, 40]))
>>> hash(tf)
-4118419923444501110

The hash code of an object may be different depending on the version of Python, the machine architecture, and because of a salt added to the hash computation for security reasons.3 The hash code of a correctly implemented object is guaranteed to be constant only within one Python process.

User-defined types are hashable by default because their hash code is their id(), and the __eq__() method inherited from the object class simply compares the object IDs. If an object implements a custom __eq__() that takes into account its internal state, it will be hashable only if its __hash__() always returns the same hash code. In practice, this requires that __eq__() and __hash__() only take into account instance attributes that never change during the life of the object.

Now let’s review the API of the most commonly used mapping types in Python: dict, defaultdict, and OrderedDict.

Overview of Common Mapping Methods

The basic API for mappings is quite rich. Table 3-1 shows the methods implemented by dict and two popular variations: defaultdict and OrderedDict, both defined in the collections module.

The way d.update(m) handles its first argument m is a prime example of duck typing: it first checks whether m has a keys method and, if it does, assumes it is a mapping. Otherwise, update() falls back to iterating over m, assuming its items are (key, value) pairs. The constructor for most Python mappings uses the logic of update() internally, which means they can be initialized from other mappings or from any iterable object producing (key, value) pairs.

In line with Python’s fail-fast philosophy, dict access with d[k] raises an error when k is not an existing key. Pythonistas know that d.get(k, default) is an alternative to d[k] whenever a default value is more convenient than handling KeyError. However, when you retrieve a mutable value and want to update it, there is a better way.

Consider a script to index text, producing a mapping where each key is a word, and the value is a list of positions where that word occurs, as shown in Example 3-3.

$ python3 index0.py zen.txt
a [(19, 48), (20, 53)]
Although [(11, 1), (16, 1), (18, 1)]
ambiguity [(14, 16)]
and [(15, 23)]
are [(21, 12)]
aren [(10, 15)]
at [(16, 38)]
bad [(19, 50)]
be [(15, 14), (16, 27), (20, 50)]
beats [(11, 23)]
Beautiful [(3, 1)]
better [(3, 14), (4, 13), (5, 11), (6, 12), (7, 9), (8, 11), (17, 8), (18, 25)]
...

Example 3-4 is a suboptimal script written to show one case where dict.get is not the best way to handle a missing key. I adapted it from an example by Alex Martelli.⁴

"""Build an index mapping word -> list of occurrences"""

import re
import sys

WORD_RE = re.compile(r'\w+')

index = {}
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            # this is ugly; coded like this to make a point
            occurrences = index.get(word, [])  
            occurrences.append(location)       
            index[word] = occurrences          

# display in alphabetical order
for word in sorted(index, key=str.upper):      
    print(word, index[word])

Get the list of occurrences for word, or [] if not found.

Append new location to occurrences.

Put changed occurrences into index dict; this entails a second search through the index.

In the key= argument of sorted, I am not calling str.upper, just passing a reference to that method so the sorted function can use it to normalize the words for sorting.⁵

The three lines dealing with occurrences in Example 3-4 can be replaced by a single line using dict.setdefault. Example 3-5 is closer to Alex Martelli’s code.

"""Build an index mapping word -> list of occurrences"""

import re
import sys

WORD_RE = re.compile(r'\w+')

index = {}
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            index.setdefault(word, []).append(location)  

# display in alphabetical order
for word in sorted(index, key=str.upper):
    print(word, index[word])

Get the list of occurrences for word, or set it to [] if not found; setdefault returns the value, so it can be updated without requiring a second search.

In other words, the end result of this line…

my_dict.setdefault(key, []).append(new_value)

…is the same as running…

if key not in my_dict:
    my_dict[key] = []
my_dict[key].append(new_value)

…except that the latter code performs at least two searches for key—three if it’s not found—while setdefault does it all with a single lookup.

A related issue, handling missing keys on any lookup (and not only when inserting), is the subject of the next section.

A collections.defaultdict instance creates items with a default value on demand whenever a missing key is searched using d[k] syntax. Example 3-6 uses defaultdict to provide another elegant solution to the word index task from Example 3-5.

Here is how it works: when instantiating a defaultdict, you provide a callable to produce a default value whenever __getitem__ is passed a nonexistent key argument.

For example, given a defaultdict created as dd = defaultdict(list), if 'new-key' is not in dd, the expression dd['new-key'] does the following steps:

1. Calls list() to create a new list.

2. Inserts the list into dd using 'new-key' as key.

3. Returns a reference to that list.

The callable that produces the default values is held in an instance attribute named default_factory.

"""Build an index mapping word -> list of occurrences"""

import collections
import re
import sys

WORD_RE = re.compile(r'\w+')

index = collections.defaultdict(list)     
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            index[word].append(location)  

# display in alphabetical order
for word in sorted(index, key=str.upper):
    print(word, index[word])

Create a defaultdict with the list constructor as default_factory.

If word is not initially in the index, the default_factory is called to produce the missing value, which in this case is an empty list that is then assigned to index[word] and returned, so the .append(location) operation always succeeds.

If no default_factory is provided, the usual KeyError is raised for missing keys.

The mechanism that makes defaultdict work by calling default_factory is the __missing__ special method, a feature that we discuss next.

The __missing__ Method

Underlying the way mappings deal with missing keys is the aptly named __missing__ method. This method is not defined in the base dict class, but dict is aware of it: if you subclass dict and provide a __missing__ method, the standard dict.__getitem__ will call it whenever a key is not found, instead of raising KeyError.

Suppose you’d like a mapping where keys are converted to str when looked up. A concrete use case is a device library for IoT,6 where a programmable board with general-purpose I/O pins (e.g., a Raspberry Pi or an Arduino) is represented by a Board class with a my_board.pins attribute, which is a mapping of physical pin identifiers to pin software objects. The physical pin identifier may be just a number or a string like "A0" or "P9_12". For consistency, it is desirable that all keys in board.pins are strings, but it is also convenient looking up a pin by number, as in my_arduino.pin[13], so that beginners are not tripped when they want to blink the LED on pin 13 of their Arduinos. Example 3-7 shows how such a mapping would work.

Tests for item retrieval using `d[key]` notation::

    >>> d = StrKeyDict0([('2', 'two'), ('4', 'four')])
    >>> d['2']
    'two'
    >>> d[4]
    'four'
    >>> d[1]
    Traceback (most recent call last):
      ...
    KeyError: '1'

Tests for item retrieval using `d.get(key)` notation::

    >>> d.get('2')
    'two'
    >>> d.get(4)
    'four'
    >>> d.get(1, 'N/A')
    'N/A'


Tests for the `in` operator::

    >>> 2 in d
    True
    >>> 1 in d
    False

Example 3-8 implements a class StrKeyDict0 that passes the preceding doctests.

class StrKeyDict0(dict):  

    def __missing__(self, key):
        if isinstance(key, str):  
            raise KeyError(key)
        return self[str(key)]  

    def get(self, key, default=None):
        try:
            return self[key]  
        except KeyError:
            return default  

    def __contains__(self, key):
        return key in self.keys() or str(key) in self.keys()  

StrKeyDict0 inherits from dict.

Check whether key is already a str. If it is, and it’s missing, raise KeyError.

Build str from key and look it up.

The get method delegates to __getitem__ by using the self[key] notation; that gives the opportunity for our __missing__ to act.

If a KeyError was raised, __missing__ already failed, so we return the default.

Search for unmodified key (the instance may contain non-str keys), then for a str built from the key.

Take a moment to consider why the test isinstance(key, str) is necessary in the __missing__ implementation.

Without that test, our __missing__ method would work OK for any key k—str or not str—whenever str(k) produced an existing key. But if str(k) is not an existing key, we’d have an infinite recursion. In the last line of __missing__, self[str(key)] would call __getitem__, passing that str key, which in turn would call __missing__ again.

The __contains__ method is also needed for consistent behavior in this example, because the operation k in d calls it, but the method inherited from dict does not fall back to invoking __missing__. There is a subtle detail in our implementation of __contains__: we do not check for the key in the usual Pythonic way—k in my_dict—because str(key) in self would recursively call __contains__. We avoid this by explicitly looking up the key in self.keys().

A search like k in my_dict.keys() is efficient in Python 3 even for very large mappings because dict.keys() returns a view, which is similar to a set, as we’ll see in “Set Operations on dict Views”. However, remember that k in my_dict does the same job, and is faster because it avoids the attribute lookup to find the .keys method.

I had a specific reason to use self.keys() in the __contains__ method in Example 3-8. The check for the unmodified key—key in self.keys()—is necessary for correctness because StrKeyDict0 does not enforce that all keys in the dictionary must be of type str. Our only goal with this simple example is to make searching “friendlier” and not enforce types.

Inconsistent Usage of __missing__ in the Standard Library

Consider the following scenarios, and how the missing key lookups are affected:

dict subclass

A subclass of dict implementing only __missing__ and no other method. In this case, __missing__ may be called only on d[k], which will use the __getitem__ inherited from dict.

collections.UserDict subclass

Likewise, a subclass of UserDict implementing only __missing__ and no other method. The get method inherited from UserDict calls __getitem__. This means __missing__ may be called to handle lookups with d[k] and d.get(k).

abc.Mapping subclass with the simplest possible __getitem__

A minimal subclass of abc.Mapping implementing __missing__ and the required abstract methods, including an implementation of __getitem__ that does not call __missing__. The __missing__ method is never triggered in this class.

abc.Mapping subclass with __getitem__ calling __missing__

A minimal subclass of abc.Mapping implementing __missing__ and the required abstract methods, including an implementation of __getitem__ that calls __missing__. The __missing__ method is triggered in this class for missing key lookups made with d[k], d.get(k), and k in d.

See missing.py in the example code repository for demonstrations of the scenarios described here.

The four scenarios just described assume minimal implementations. If your subclass implements __getitem__, get, and __contains__, then you can make those methods use __missing__ or not, depending on your needs. The point of this section is to show that you must be careful when subclassing standard library mappings to use __missing__, because the base classes support different behaviors by default.

Don’t forget that the behavior of setdefault and update is also affected by key lookup. And finally, depending on the logic of your __missing__, you may need to implement special logic in __setitem__, to avoid inconsistent or surprising behavior. We’ll see an example of this in “Subclassing UserDict Instead of dict”.

So far we have covered the dict and defaultdict mapping types, but the standard library comes with other mapping implementations, which we discuss next.

collections.OrderedDict

Now that the built-in dict also keeps the keys ordered since Python 3.6, the most common reason to use OrderedDict is writing code that is backward compatible with earlier Python versions. Having said that, Python’s documentation lists some remaining differences between dict and OrderedDict, which I quote here—only reordering the items for relevance in daily use:

A ChainMap instance holds a list of mappings that can be searched as one. The lookup is performed on each input mapping in the order it appears in the constructor call, and succeeds as soon as the key is found in one of those mappings. For example:

>>> d1 = dict(a=1, b=3)
>>> d2 = dict(a=2, b=4, c=6)
>>> from collections import ChainMap
>>> chain = ChainMap(d1, d2)
>>> chain['a']
1
>>> chain['c']
6

>>> chain['c'] = -1
>>> d1
{'a': 1, 'b': 3, 'c': -1}
>>> d2
{'a': 2, 'b': 4, 'c': 6}

ChainMap is useful to implement interpreters for languages with nested scopes, where each mapping represents a scope context, from the innermost enclosing scope to the outermost scope. The “ChainMap objects” section of the collections docs has several examples of ChainMap usage, including this snippet inspired by the basic rules of variable lookup in Python:

import builtins
pylookup = ChainMap(locals(), globals(), vars(builtins))

Example 18-14 shows a ChainMap subclass used to implement an interpreter for a subset of the Scheme programming language.

collections.Counter

A mapping that holds an integer count for each key. Updating an existing key adds to its count. This can be used to count instances of hashable objects or as a multiset (discussed later in this section). Counter implements the + and - operators to combine tallies, and other useful methods such as most_common([n]), which returns an ordered list of tuples with the n most common items and their counts; see the documentation. Here is Counter used to count letters in words:

>>> ct = collections.Counter('abracadabra')
>>> ct
Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
>>> ct.update('aaaaazzz')
>>> ct
Counter({'a': 10, 'z': 3, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
>>> ct.most_common(3)
[('a', 10), ('z', 3), ('b', 2)]

Note that the 'b' and 'r' keys are tied in third place, but ct.most_common(3) shows only three counts.

To use collections.Counter as a multiset, pretend each key is an element in the set, and the count is the number of occurrences of that element in the set.

shelve.Shelf

The shelve module in the standard library provides persistent storage for a mapping of string keys to Python objects serialized in the pickle binary format. The curious name of shelve makes sense when you realize that pickle jars are stored on shelves.

The documentation for the shelve, dbm, and pickle modules provides more details and some caveats.

OrderedDict, ChainMap, Counter, and Shelf are ready to use but can also be customized by subclassing. In contrast, UserDict is intended only as a base class to be extended.

Subclassing UserDict Instead of dict

It’s better to create a new mapping type by extending collections.UserDict rather than dict. We realize that when we try to extend our StrKeyDict0 from Example 3-8 to make sure that any keys added to the mapping are stored as str.

The main reason why it’s better to subclass UserDict rather than dict is that the built-in has some implementation shortcuts that end up forcing us to override methods that we can just inherit from UserDict with no problems.⁷

Note that UserDict does not inherit from dict, but uses composition: it has an internal dict instance, called data, which holds the actual items. This avoids undesired recursion when coding special methods like __setitem__, and simplifies the coding of __contains__, compared to Example 3-8.

Thanks to UserDict, StrKeyDict (Example 3-9) is more concise than StrKeyDict0 (Example 3-8), but it does more: it stores all keys as str, avoiding unpleasant surprises if the instance is built or updated with data containing nonstring keys.

import collections


class StrKeyDict(collections.UserDict):  

    def __missing__(self, key):  
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]

    def __contains__(self, key):
        return str(key) in self.data  

    def __setitem__(self, key, item):
        self.data[str(key)] = item   

StrKeyDict extends UserDict.

__missing__ is exactly as in Example 3-8.

__contains__ is simpler: we can assume all stored keys are str, and we can check on self.data instead of invoking self.keys() as we did in StrKeyDict0.

__setitem__ converts any key to a str. This method is easier to overwrite when we can delegate to the self.data attribute.

Because UserDict extends abc.MutableMapping, the remaining methods that make StrKeyDict a full-fledged mapping are inherited from UserDict, MutableMapping, or Mapping. The latter have several useful concrete methods, in spite of being abstract base classes (ABCs). The following methods are worth noting:

MutableMapping.update

This powerful method can be called directly but is also used by __init__ to load the instance from other mappings, from iterables of (key, value) pairs, and keyword arguments. Because it uses self[key] = value to add items, it ends up calling our implementation of __setitem__.

Mapping.get

In StrKeyDict0 (Example 3-8), we had to code our own get to return the same results as __getitem__, but in Example 3-9 we inherited Mapping.get, which is implemented exactly like StrKeyDict0.get (see the Python source code).

We know there are immutable sequence types, but how about an immutable mapping? Well, there isn’t a real one in the standard library, but a stand-in is available. That’s next.

The syntax of set literals—{1}, {1, 2}, etc.—looks exactly like the math notation, with one important exception: there’s no literal notation for the empty set, so we must remember to write set().

>>> s = {1}
>>> type(s)
<class 'set'>
>>> s
{1}
>>> s.pop()
1
>>> s
set()

Literal set syntax like {1, 2, 3} is both faster and more readable than calling the constructor (e.g., set([1, 2, 3])). The latter form is slower because, to evaluate it, Python has to look up the set name to fetch the constructor, then build a list, and finally pass it to the constructor. In contrast, to process a literal like {1, 2, 3}, Python runs a specialized BUILD_SET bytecode.10

There is no special syntax to represent frozenset literals—they must be created by calling the constructor. The standard string representation in Python 3 looks like a frozenset constructor call. Note the output in the console session:

>>> frozenset(range(10))
frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9})

Speaking of syntax, the idea of listcomps was adapted to build sets as well.

Set Comprehensions

Set comprehensions (setcomps) were added way back in Python 2.7, together with the dictcomps that we saw in “dict Comprehensions”. Example 3-15 shows how.

>>> from unicodedata import name  
>>> {chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i),'')}  
{'§', '=', '¢', '#', '¤', '<', '¥', 'µ', '×', '$', '¶', '£', '©',
'°', '+', '÷', '±', '>', '¬', '®', '%'}

Import name function from unicodedata to obtain character names.

Build set of characters with codes from 32 to 255 that have the word 'SIGN' in their names.

The order of the output changes for each Python process, because of the salted hash mentioned in “What Is Hashable”.

Syntax matters aside, let’s now consider the behavior of sets.