Inside dict and set

Python’s dict is an open-addressing hash table (lesson 3) with two clever additions. It keeps keys in the order they were added, and it uses less memory than a plain table. This lesson looks inside it. Everything here describes CPython, the usual Python.

Two arrays

A plain open-addressing table stores the key, the value and the hash in every slot, including the empty ones. Since Python 3.6, a dict splits this into two arrays:

• entries lists each key’s hash, the key and its value, in the order they were added. It has no gaps.
• indices is the hash table itself. Each slot is empty, or holds a position in entries. A slot is tiny: one byte for small dicts.

To find a key, Python hashes it, probes indices, and follows each position it meets into entries to compare the key. Step through four inserts and one lookup:

Because entries is in insertion order, looping over a dict gives the keys in the order they were added. Since Python 3.7 this is a promise of the language, not just a detail of CPython. Empty slots now cost one byte instead of a whole entry, so a dict uses much less memory than before.

Each entry keeps the key’s hash. A probe compares the stored hash first, and only calls == when the hashes are equal. Comparing two numbers is much faster than comparing, say, two long strings. And when the dict grows, it can place every key again without calling hash() again.

How Python probes

Linear probing would make clusters (lesson 3). Python uses a different probe sequence. With 2^k slots (a power of 2, such as 8, 16 or 32), the next slot after slot i is

perturb >>= 5                    # drop the lowest 5 bits
i = (5 * i + perturb + 1) % 2**k

perturb starts as the whole hash, and >>= 5 shifts it right by 5 bits each time, which is the same as dividing by 32 and rounding down. So the first probe uses only the low bits of the hash (hash % 2**k), and later probes mix in the higher bits. Two keys with the same home slot but different hashes soon follow different paths.

After a few probes, perturb becomes 0, and the rule is just i = (5*i + 1) % 2**k. In the figure the keys are small, so this happens at once. Does this rule ever miss a slot? No. A known result about such sequences (the Hull–Dobell theorem) says that i → 5i + 1, taken % 2**k, visits every slot once before repeating. With 8 slots, starting at 0:

0 → 1 → 6 → 7 → 4 → 5 → 2 → 3 → 0

When a dict grows

A new dict has 8 slots. It may fill only two-thirds of them, so the sixth key makes it grow. The new size is the smallest power of 2 that is at least three times the number of keys. Growing builds new arrays and places every entry again: O(n), but rare, so inserts stay O(1) amortised (lesson 2).

del d[k] uses the marker idea from lesson 3. The slot in indices gets a deleted marker, and the entry is emptied. Neither is reused straight away; both are cleaned up the next time the dict grows or is rebuilt. That is why a dict that grew large and then lost most of its keys still uses a lot of memory. d = dict(d) builds a compact copy.

Sets

A set is a hash table of keys with no values. It has no entries array, so it does not keep insertion order: the order you see when you print a set comes from the slots. Its probing first checks a few neighbouring slots, as linear probing does, because neighbours are cheap to read. Then it jumps, as a dict does.

seen = set()
seen.add('NDLS')
'NDLS' in seen            # True, O(1) on average
{1, 2, 3} & {2, 3, 4}     # {2, 3}: the keys in both
{1, 2, 3} | {3, 4}        # {1, 2, 3, 4}: the keys in either
{1, 2, 3} - {2}           # {1, 3}

s & t loops over the smaller set and checks each key in the larger one, so it costs O(min(len(s), len(t))) on average. s | t costs O(len(s) + len(t)). A frozenset is a set that cannot change, so it is hashable and can itself be a dict key or a set member.

The everyday lesson: x in a_list walks the list, O(n). x in a_set is O(1) on average. If you check membership many times, build a set once.