How dict and set Work in CPython

dict and set are the most used structures in Python, and both are hash tables. In this topic we look at how the CPython dict is built: a step from theory (hash functions, open addressing, load factor) to a real implementation. For usage rules see dict basics and sets.

The compact dict

Since Python 3.6 a dict has two parts:

• indices: a hash array of small integers (an empty slot, a deleted slot or a position in entries).
• entries: records (hash, key, value) in insertion order.

A lookup does open addressing in indices and the position found leads to entries. Pros: less memory (the sparse array holds only small indices while the heavy records are packed densely) and a natural order. The order is guaranteed by the language since Python 3.7.

Probing

CPython does not use plain linear probing but a key-dependent perturbation: i = (5*i + perturb + 1) & mask, where perturb is shifted right by 5 bits on every step, so the high bits of the hash influence the sequence too. Keys with equal low bits quickly diverge, and clustering shrinks.

def slots(h, size, n):
    mask = size - 1
    perturb = h & (2**64 - 1)
    i = h & mask
    out = []
    for _ in range(n):
        out.append(i)
        perturb >>= 5
        i = (i * 5 + perturb + 1) & mask
    return out

print(slots(1, 8, 5))
print(slots(1000, 8, 5))

[1, 6, 7, 4, 5]
[0, 0, 1, 6, 7]

A model implementation