Handling Missing Keys with setdefault

In line with Python’s fail-fast philosophy, dict access with d[k] raises an error when k is not an existing key. Every Pythonista knows that d.get(k, default) is an alternative to d[k] whenever a default value is more convenient than handling KeyError. However, when updating the mutable value found, using either d[k] or get is awkward and inefficient.

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-2.

$ 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-3, 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 sys
import re

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          

# print 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-3 can be replaced by a single line using dict.setdefault. Example 3-4 is closer to Alex Martelli’s original example.

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

import sys
import re

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)  

# print 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.

defaultdict: Another Take on Missing Keys

Example 3-5 uses collections.defaultdict to provide another elegant solution to the problem in Example 3-4. A defaultdict is configured to create items on demand whenever a missing key is searched.

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

For example, given an empty 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 called default_factory.

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

import sys
import re
import collections

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)  

# print 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⁴, 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 that 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-6 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-7 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. The last line, 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().

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.

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

Subclassing UserDict

It’s almost always easier to create a new mapping type by extending UserDict rather than dict. We realize that when we try to extend our StrKeyDict0 from Example 3-7 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-7.

Thanks to UserDict, StrKeyDict (Example 3-8) is actually shorter than StrKeyDict0 (Example 3-7), 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-7.

__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-7), we had to code our own get to obtain results consistent with __getitem__, but in Example 3-8 we inherited Mapping.get, which is implemented exactly like StrKeyDict0.get (see 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. Read on.

Set Literals

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().

In Python 3, the standard string representation of sets always uses the {…} notation, except for the empty 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⁷.

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 in Python 2.7, together with the dictcomps that we saw in “dict Comprehensions”. Example 3-14 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.

Syntax matters aside, let’s now review the rich assortment of operations provided by sets.

Set Operations

Figure 3-2 gives an overview of the methods you can use on mutable and immutable sets. Many of them are special methods that overload operators such as & and >=. Table 3-2 shows the math set operators that have corresponding operators or methods in Python. Note that some operators and methods perform in-place changes on the target set (e.g., &=, difference_update, etc.). Such operations make no sense in the ideal world of mathematical sets, and are not implemented in frozenset.

Figure 3-2. Simplified UML class diagram for MutableSet and its superclasses from collections.abc (names in italic are abstract classes and abstract methods; reverse operator methods omitted for brevity)

Table 3-3 lists set predicates: operators and methods that return True or False.

In addition to the operators and methods derived from math set theory, the set types implement other methods of practical use, summarized in Table 3-4.

This completes our overview of the features of sets. As promised in “Dictionary views”, we’ll now see how two of the dictionary view types behave very much like a frozenset.

Set operations on dict views

Table 3-5 shows that the view objects returned by the dict methods .keys() and .items() are remarkably similar to frozenset.

In particular, dict_keys and dict_items implement the special methods to support the powerful set operators & (intersection), | (union), - (difference) and ^ (symmetric difference).

This means, for example, that finding the keys that appear in two dictionaries is as easy as this:

>>> d1 = dict(a=1, b=2, c=3, d=4)
>>> d2 = dict(b=20, d=40, e=50)
>>> d1.keys() & d2.keys()
{'b', 'd'}

Note that the return value of & is a set. Even better: the set operators in dictonary views are compatible with set instances. Check this out:

>>> s = {'a', 'e', 'i'}
>>> d1.keys() & s
{'a'}
>>> d1.keys() | s
{'a', 'c', 'b', 'd', 'i', 'e'}

This will save a lot of loops and ifs when inspecting the contents of dictionaries in your code.

We now change gears to discuss how sets and dictionaries are implemented with hash tables. After reading the rest of this chapter, you should no longer be surprised by the behavior of dict, set, and other data structures powered by hash tables.

A Performance Experiment

From experience, all Pythonistas know that dicts and sets are fast. We’ll confirm that with a controlled experiment.

To see how the size of a dict, set, or list affects the performance of search using the in operator, I generated an array of 10 million distinct double-precision floats, the “haystack.” I then generated an array of needles: 1,000 floats, with 500 picked from the haystack and 500 verified not to be in it.

For the dict benchmark, I used dict.fromkeys() to create a dict named haystack with 1,000 floats. This was the setup for the dict test. The actual code I clocked with the timeit module is Example 3-15 (like Example 3-12).

found = 0
for n in needles:
    if n in haystack:
        found += 1

I repeated the benchmark five times, each time increasing tenfold the size of haystack, from 1,000 to 10,000,000 items. The result of the dict performance test is in Table 3-6.

In concrete terms, to check for the presence of 1,000 floating-point keys in a dictionary with 1,000 items, the processing time on my laptop was 99µs, and the same search in a dict with 10,000,000 items took 512µs. In other words, the average time for each search in the haystack with 10 million items was 0.512µs—yes, that’s about half microsecond per needle. When the search space became 10,000 times larger, the search time increased a little over 5 times. Nice.

To compare with other collections, I repeated the benchmark with the same haystacks of increasing size, but storing the haystack as a set or as list. For the set tests, in addition to timing the for loop in Example 3-15, I also timed the one-liner in Example 3-16, which produces the same result: count the number of elements from needles that are also in haystack—if both are sets.

found = len(needles & haystack)

Table 3-7 shows the tests side by side. The best times are in the “set& time” column, which displays results for the set & operator using the code from Example 3-16. As expected, the worst times are in the “list time” column, because there is no hash table to support searches with the in operator on a list, so a full scan must be made if the needle is not present, resulting in times that grow linearly with the size of the haystack.

If your program does any kind of I/O, the lookup time for keys in dicts or sets is negligible, regardless of the dict or set size (as long as it fits in RAM). See the code used to generate Table 3-7 and accompanying discussion in [Link to Come], [Link to Come].

Now that we have concrete evidence of the speed of dicts and sets, let’s explore how that is achieved with the help of hash tables.

Set hash tables under the hood

Hash tables are a wonderful invention. Let’s see how a hash table is used when adding elements to a set.

Let’s say we have a set with abbreviated workdays, created like this:

>>> workdays = {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}
>>> workdays
{'Tue', 'Mon', 'Wed', 'Fri', 'Thu'}

The core data structure of a Python set is a hash table with at least 8 rows. Traditionally, the rows in hash table are called buckets⁸.

A hash table holding the elements of workdays looks like Figure 3-3.

Figure 3-3. Hash table for the set {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}. Each bucket has two fields: the hash code and a pointer to the element value. Empty buckets have -1 in the hash code field. The ordering looks random.

In CPython built for a 64-bit CPU, each bucket in a set has two fields: a 64-bit hash code, and a 64-bit pointer to the element value—which is a Python object stored elsewhere in memory. Because buckets have a fixed size, access to an individual bucket is done by offset. There is no field for the indexes from 0 to 7 in Figure 3-3.

Before covering the hash table algorithm, we need to know more about hash codes, and how they relate to equality.

32-bit Python build
1        00000000000000000000000000000001
                                          != 0
1.0      00000000000000000000000000000001
------------------------------------------------
1.0      00000000000000000000000000000001
           ! !!! ! !! ! !    ! ! !! !!!   != 16
1.0001   00101110101101010000101011011101
------------------------------------------------
1.0001   00101110101101010000101011011101
          !!!  !!!! !!!!!   !!!!! !!  !   != 20
1.0002   01011101011010100001010110111001
------------------------------------------------
1.0002   01011101011010100001010110111001
          ! !   ! !!! ! !  !! ! !  ! !!!! != 17
1.0003   00001100000111110010000010010110
------------------------------------------------

The hash table algorithm

We will focus on the internals of set first, and later transfer the concepts to dict.

Let’s see how Python builds a set like {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}, step by step. The algorithm is illustrated by the flowchart in Figure 3-4, and described next.

Figure 3-4. Flowchart for algorithm to add element to the hash table of a set.

>>> hash('Mon')
4199492796428269555

>>> 4199492796428269555 % 8
3

Step 3: put the element in the empty bucket

Python stores the hash code of the new element, 4199492796428269555, in the hash code field at offset 3, and a pointer to the string object 'Mon' in the element field. Figure 3-5 shows the current state of the hash table.

Figure 3-5. Hash table for the set {'Mon'}.

Steps for remaining items

For the second element, 'Tue', steps 1, 2, 3 above are repeated. The hash code for 'Tue' is 2414279730484651250, and the resulting index is 2.

>>> hash('Tue')
2414279730484651250
>>> hash('Tue') % 8
2

The hash and pointer to element 'Tue' are placed in bucket 2, which was also empty. Now we have Figure 3-6

Figure 3-6. Hash table for the set {'Mon', 'Tue'}. Note that element ordering is not preserved in the hash table.

Steps for a collision

When adding 'Wed' to the set, Python computes the hash -5145319347887138165 and index 3. Python probes bucket 3 and sees that it is already taken. But the hash code stored there, 4199492796428269555 is different. As discussed in “Hashes and equality”, if two objects have different hashes, then their value is also different. This is an index collision. Python then probes the next bucket and finds it empty. So 'Wed' ends up at index 4, as shown in Figure 3-7.

Figure 3-7. Hash table for the set {'Mon', 'Tue', 'Wed'}. After the collision, 'Wed' is put at index 4.

Adding the next element, 'Thu', is boring: there’s no collision, and it lands in its natural bucket, at index 7.

Placing 'Fri' is more interesting. Its hash, 7021641685991143771 implies index 3, which is taken by 'Mon'. Probing the next bucket—4—Python finds the hash for 'Wed' stored there. The hash codes don’t match, so this is another index collision. Python probes the next bucket. It’s empty, so 'Fri' ends up at index 5. The end state of the hash table is shown in Figure 3-8.

Note

Incrementing the index after a collision is called linear probing. This can lead to clusters of occupied buckets, which can degrade the hash table performance, so CPython counts the number of linear probes and after a certain threshold, applies a pseudo random number generator to obtain a different index from other bits of the hash code. This optimization is particulary important in large sets.

Figure 3-8. Hash table for the set {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}. It is now 62.5% full—close to the ⅔ threshold.

When there is an element in the probed bucket and the hash codes match, Python also needs to compare the actual object values. That’s because, as explained in “Hash collisions”, it’s possible that two different objects have the same hash code—although that’s rare for strings, thanks to the quality of the Siphash algorithm¹¹. This explains why hashable objects must implement both __hash__ and __eq__.

If a new element were added to our example hash table, it would be more than ⅔ full, therefore increasing the chances of index collisions. To prevent that, Python would alocate a new hash table with 16 buckets, and reinsert all elements there.

All this may seem like a lot of work, but even with millions of items in a set, many insertions happen with no collisions, and the average number of collisions per insertion is between one and two. Under normal usage, even the unluckiest elements can be placed after a handful of collisions are resolved.

Now, given what we’ve seen so far, follow the flowchart in Figure 3-4 to answer the following puzzle without using the computer.

Given the following set, what happens when you add an integer 1 to it?

>>> s = {1.0, 2.0, 3.0}
>>> s.add(1)

How many elements are in s now? Does 1 replace the element 1.0? When you have your answer, use the Python console to verify it.

Hash table usage in dict

Since 2012, the implementation of the dict type had two major optimizations to reduce memory usage. The first one was proposed as PEP 412 — Key-Sharing Dictionary and implemented in Python 3.3¹³. The second is called “compact dict", and landed in Python 3.6. As a side effect, the compact dict space optimization preserves key insertion order. In the next sections we’ll discuss the compact dict and the new key-sharing scheme—in this order, for easier presentation.

How compact dict saves space

Note

This is a high level explanation of the Python dict implementation. One difference is that the actual usable fraction of a dict hash table is ⅓, and not ⅔ as in sets. The actual ⅓ fraction would require 16 buckets to hold the 4 items in my example dict, and the diagrams in this section would become too tall, so I pretend the usable fraction is ⅔ in these explanations. One comment in Objects/dictobject.c explains that any fraction between ⅓ and ⅔ “seem to work well in practice”.

Consider a dict holding the abbreviated names for the weekdays from 'Mon' through 'Thu', and the number of students enrolled in swimming class on each day:

>>> swimmers = {'Mon': 14, 'Tue': 12, 'Wed': 14, 'Thu': 11}

Before the compact dict optimization, the hash table underlying the swimmers dictionary would look like Figure 3-9. As you can see, in a 64-bit Python, each bucket holds three 64-bit fields: the hash code of the key, a pointer to the key object, and a pointer to the value object. That’s 24 bytes per bucket.

Figure 3-9. Old hash table format for a dict with 4 key-value pairs. Each bucket is a struct with the hash code of the key, a pointer to the key, and a pointer to the value.

The first two fields play the same role as they do in the implementation of sets. To find a key, Python computes the hash code of the key, derives an index from the key, then probes the hash table to find a bucket with a matching hash code and a matching key object. The third field provides the main feature of a dict: mapping a key to an arbitrary value. The key must be a hashable object, and the hash table algorithm ensures it will be unique in the dict. But the value may be any object—it doesn’t need to be hashable or unique.

Raymond Hettinger observed that significant savings could be made if the hash code and pointers to key and value were held in an entries array with no empty rows, and the actual hash table were a sparse array with much smaller buckets holding indexes into the entries array¹⁴. In his original message to python-dev, Hettinger called the hash table indices. The width of the buckets in indices varies as the dict grows, starting at 8-bits per bucket—enough to index up to 128 entries, while reserving negative values for special purposes, such as -1 for empty and -2 for deleted.

As an example, the swimmers dictionary would then be stored as shown in Figure 3-10.

Figure 3-10. Compact storage for a dict with 4 key-value pairs. Hash codes and pointers to keys and values are stored in insertion order in the entries array, and the entry offsets derived from the hash codes are held in the indices sparse array, where an index value of -1 signals an empty bucket.

Assuming a 64-bit build of CPython, our 4-item swimmers dictionary would take 192 bytes of memory in the old scheme: 24 bytes per bucket, times 8 rows. The equivalent compact dict uses 104 bytes in total: 96 bytes in entries (24 * 4), plus 8 bytes for the buckets in indices—configured as an array of 8 bytes.

The next section describes how those two arrarys are used.

Algorithm for adding items to compact dict.

Step 0: set up indices

The indices table is initially set up as an array of signed bytes, with 8 buckets, each initialized with -1 to signal “empty bucket”. Up to 5 of these buckets will eventually hold indices to rows in the entries array, leaving ⅓ of them with -1. The other array, entries, will hold key/value data with the same three fields as in the old scheme—but in insertion order.

Step 1: compute hash code for the key

To add the key-value pair ('Mon', 14) to the swimmers dictionary, Python first calls hash('Mon') to compute the hash code of that key.

Step 2: probe entries via indices

Python computes hash('Mon') % len(indices). In our example, this is 3. Offset 3 in indices holds -1: it’s an empty bucket.

Step 3: put key-value in entries, updating indices.

The entries array is empty, so the next available offset there is 0. Python puts 0 at offset 3 in indices and stores the hash code of the key, a pointer to the key object 'Mon', and a pointer to the int value 14 at offset 0 in entries. Figure 3-11 shows the state of the arrays when the value of swimmers is {'Mon': 14}.

Figure 3-11. Compact storage for the {'Mon': 14}: indices[3] holds the offset of the first entry: entries[0].

Steps for next item

To add ('Tue', 12) to swimmers:

1. Compute hash code of key 'Tue'.

2. Compute offset into indices, as hash('Tue') % len(indices). This is 2. indices[2] has -1. No collision so far.

3. Put the next available entries offset, 1, in indices[2], then store entry at entries[1].

Now the state is Figure 3-12. Note that entries holds the key-value pairs in insertion order.

Figure 3-12. Compact storage for the {'Mon': 14, 'Tue': 12}.

Steps for a collision

1. Compute hash code of key 'Wed'.

2. Now, hash('Wed') % len(indices) is 3. indices[3] has 0, pointing to an existing entry. Look at the hash code in entries[0]. That’s the hash code for 'Mon', which happens to be different than the hash code for 'Wed'. This mismatch signals a collision. Probes the next index: indices[4]. That’s -1, so it can be used.

3. Make indices[4] = 2, because 2 is the next available offset at entries. Then fill entries[2] as usual.

After adding ('Wed', 14), we have Figure 3-13

Figure 3-13. Compact storage for the {'Mon': 14, 'Tue': 12, 'Wed': 14}.

Key-sharing dictionary

Instances of user-defined classes usually hold their attributes in a __dict__ attribute which is a regular dictionary¹⁵. In an instance __dict__, the keys are the attribute names, and the values are the attribute values. Most of the time, all instances have the same attributes with different values. When that happens, 2 of the 3 fields in the entries table for every instance has the exact same content: the hash code of the attribute name, and a pointer to the attribute name. Only the pointer to the attribute value is different.

In PEP 412 — Key-Sharing Dictionary, Mark Shannon proposed to split the storage of dictionaries used as instance __dict__, so that each attribute hash code and pointer is stored only once, linked to the class, and the attribute values are kept in parallel arrays of pointers attached to each instance.

Given a Movie class where all instances have the same attributes named 'title', 'release', 'directors', and 'actors', Figure 3-14 shows the arrangement of key-sharing in a split dictionary—also implemented with the new compact layout.

Figure 3-14. Split storage for the __dict__ of a class and three instances.

PEP 412 introduced the terms combined-table to discuss the old layout and and split-table for the proposed optimization.

The combined-table layout is still the default when you create a dict using literal syntax or call dict(). A split-table dictionary is created to fill the __dict__ special attribute of an instance, when it is the first instance of a class. The keys table (see Figure 3-14) is then cached in the class object. This leverages the fact that most Object Oriented Python code assigns all instance attributes in the __init__ method. That first instance (and all instances after it) will hold only its own a value array. If an instance gets a new attribute not found in the shared keys table, then this instance’s __dict__ is converted to combined-table form. However, if this instance is the only one in its class, the __dict__ is converted back to split-table, since it is assumed that further instances will have the same set of attributes and key sharing will be useful.

The PyDictObject struct that represents a dict in the CPython source code is the same for both combined-table and split-table dictionaries. When a dict converts from one layout to the other, the change happens in PyDictObject fields, with the help of other internal data structures.

Practical Consequences of How dict Works

• Keys must be hashable objects. They must implement proper __hash__ and __eq__ methods as described in “What Is Hashable?”.

• Key searches are nearly as fast as element searches in sets.

• Item ordering is preserved in the entries table—this was implemented in CPython 3.6, and became an official language feature in 3.7.

• To save memory, avoid creating instance attributes outside of the __init__ method. If all instance attributes are created in __init__, the __dict__ of your instances will use the split-table layout, sharing the same indices and key entries array stored with the class.