CPython's set and frozenset Implementation in C: One Hash Table, Two Flavors

TL;DR: set and frozenset share one implementation: PySetObject in Objects/setobject.c, an open-addressing hash table keyed only by element. Deletion doesn’t clear a slot — it turns it into a dummy, so other keys’ probe chains stay intact.

Python’s set and frozenset share a single implementation: an open-addressing hash table keyed only by element. In CPython that’s PySetObject in Objects/setobject.c. Let’s trace the representation and the hot paths through the 3.15 source.

The object struct

Both types use the same struct (there’s no ob_size field; the logical size is used):

c
// Include/cpython/setobject.h
typedef struct {
    PyObject *key;
    Py_hash_t hash;             /* Cached hash code of the key */
} setentry;

typedef struct {
    PyObject_HEAD

    Py_ssize_t fill;            /* Number active and dummy entries */
    Py_ssize_t used;            /* Number active entries */
    Py_ssize_t mask;            /* table size - 1 (power of two) */
    setentry *table;            /* never NULL */
    Py_hash_t hash;             /* Only used by frozenset objects */
    Py_ssize_t finger;          /* Search finger for pop() */
    setentry smalltable[PySet_MINSIZE];  /* PySet_MINSIZE == 8 */
    PyObject *weakreflist;
} PySetObject;

fill counts active plus deleted (“dummy”) slots; used is len(set). mask is size - 1, so the table has mask + 1 slots and is always a power of two.

And table is never NULL: small sets live in the inline smalltable, large sets in a PyMem_NEW’d array. That kills a null test on every single lookup.

Three entry states

Every slot is in one of three states, distinguished by key and hash:

c
// Include/cpython/setobject.h
/* 1. Unused:  key == NULL and hash == 0
   2. Dummy:   key == dummy and hash == -1
   3. Active:  key != NULL and key != dummy and hash != -1 */

dummy is a single process-wide sentinel object (&_dummy_struct), so a deleted slot can be told apart from an unused one without consuming a real key.

Unused slots terminate searches. Dummies are “holes” that an insertion may reuse but that a search must keep walking past.

Probing: linear then randomized

Lookups use open addressing with a hybrid probe sequence (Knuth Algorithm D, as in dictobject.c): LINEAR_PROBES (9) consecutive slots first for cache locality, then a pseudo-random jump:

c
// Objects/setobject.c
#define LINEAR_PROBES 9
#define PERTURB_SHIFT 5

static int set_do_lookup(PySetObject *so, setentry *table, size_t mask,
                         PyObject *key, Py_hash_t hash, setentry **epp,
                         compare_func compare_entry) {
    setentry *entry;
    size_t perturb = hash;
    size_t i = (size_t)hash & mask;
    int probes;
    ...
    while (1) {
        entry = &table[i];
        probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES : 0;
        do {
            status = compare_entry(so, table, entry, key, hash);
            if (status != SET_LOOKKEY_NO_MATCH) {
                if (status == SET_LOOKKEY_EMPTY)   /* unused slot */
                    return SET_LOOKKEY_NO_MATCH;   /* not found */
                *epp = entry;
                return status;                    /* found / error */
            }
            entry++;
        } while (probes--);
        perturb >>= PERTURB_SHIFT;
        i = (i * 5 + 1 + perturb) & mask;
    }
}

The initial index is hash & mask. Consecutive probes walk memory linearly — cheap, and cache-friendly — then the congruential step scatters to break collision chains. Unused slots (key == NULL && hash == 0) stop a failing search; dummies do not.

Adding an element

set_add_entry_takeref walks the probe sequence looking for either an active match (return without taking ownership again) or a slot to fill:

c
// Objects/setobject.c
static int set_add_entry_takeref(PySetObject *so, PyObject *key,
                                 Py_hash_t hash) {
    ...
    while (1) {
        entry = &so->table[i];
        probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES : 0;
        do {
            if (entry->hash == 0 && entry->key == NULL)
                goto found_unused_or_dummy;   /* unused */
            if (entry->hash == hash) {
                ... /* compare; on match goto found_active */
            }
            else if (entry->hash == -1) {      /* dummy slot */
                assert(entry->key == dummy);
                freeslot = entry;               /* remember first dummy */
            }
            entry++;
        } while (probes--);
        perturb >>= PERTURB_SHIFT;
        i = (i * 5 + 1 + perturb) & mask;
    }

found_unused_or_dummy:
    if (freeslot == NULL)
        goto found_unused;
    /* reuse the dummy slot */
    FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, so->used + 1);
    FT_ATOMIC_STORE_SSIZE_RELAXED(freeslot->hash, hash);
    FT_ATOMIC_STORE_PTR_RELEASE(freeslot->key, key);
    return 0;

found_unused:
    so->fill++;
    FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, so->used + 1);
    FT_ATOMIC_STORE_SSIZE_RELAXED(entry->hash, hash);
    FT_ATOMIC_STORE_PTR_RELEASE(entry->key, key);
    if ((size_t)so->fill * 5 < mask * 3)
        return 0;
    return set_table_resize(so, so->used > 50000 ? so->used * 2
                                                 : so->used * 4);
}

Two details matter here. First, a dummy slot encountered during the walk is remembered as freeslot and reused in preference to extending fill — that’s how deletions get recycled.

Second, the load-factor check fill*5 < mask*3 is roughly a 60% load factor (fill < 0.6 * size). Exceed it and the table grows: 4x for small sets (used <= 50000), 2x for large ones. That growth factor is an amortization choice.

Deleting: turning active into dummy

Discard doesn’t clear the slot. It converts it to a dummy so that probe chains for other keys remain intact:

c
// Objects/setobject.c
static int set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash) {
    setentry *entry;
    PyObject *old_key;
    int status = set_lookkey(so, key, hash, &entry);
    if (status < 0) return -1;
    if (status == SET_LOOKKEY_NO_MATCH) return DISCARD_NOTFOUND;
    old_key = entry->key;
    FT_ATOMIC_STORE_SSIZE_RELAXED(entry->hash, -1);
    FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, so->used - 1);
    FT_ATOMIC_STORE_PTR_RELEASE(entry->key, dummy);
    Py_DECREF(old_key);
    return DISCARD_FOUND;
}

fill stays unchanged (the slot is still occupied, now by a dummy), so only used drops.

Here’s the thing: over many deletions fill can creep up to size. At that point even failed searches need a resize to recreate a virgin slot. Delete-heavy workloads therefore resize more often than you’d expect.

Resizing and rehashing

set_table_resize allocates a new table and reinserts every active key via set_insert_clean (which assumes absence and never calls back into Python):

c
// Objects/setobject.c
static int set_table_resize(PySetObject *so, Py_ssize_t minused) {
    ...
    size_t newsize = PySet_MINSIZE;
    while (newsize <= (size_t)minused) newsize <<= 1;

    oldtable = so->table;
    is_oldtable_malloced = oldtable != so->smalltable;

    if (newsize == PySet_MINSIZE) {
        newtable = so->smalltable;
        if (newtable == oldtable) {
            if (so->fill == so->used) {
                /* No dummies: nothing to do. */
                return 0;
            }
            /* rebuild in place to purge dummies */
            memcpy(small_copy, oldtable, sizeof(small_copy));
            oldtable = small_copy;
        }
    } else {
        newtable = PyMem_NEW(setentry, newsize);
        ...
    }

    set_zero_table(newtable, newsize);
    FT_ATOMIC_STORE_PTR_RELEASE(so->table, NULL);
    FT_ATOMIC_STORE_SSIZE_RELEASE(so->mask, newsize - 1);

    newmask = (size_t)so->mask;
    if (so->fill == so->used) {
        for (entry = oldtable; entry <= oldtable + oldmask; entry++)
            if (entry->key != NULL)
                set_insert_clean(newtable, newmask, entry->key, entry->hash);
    } else {
        so->fill = so->used;
        for (entry = oldtable; entry <= oldtable + oldmask; entry++)
            if (entry->key != NULL && entry->key != dummy)
                set_insert_clean(newtable, newmask, entry->key, entry->hash);
    }

    FT_ATOMIC_STORE_PTR_RELEASE(so->table, newtable);
    if (is_oldtable_malloced)
        free_entries(oldtable, oldsize, SET_IS_SHARED(so));
    return 0;
}

Three things to note. The new size is the smallest power of two strictly greater than minused. Shrinking to PySet_MINSIZE with no dummies is a no-op. And dummies are dropped during reinsertion, so fill becomes used again.

The old array is freed with QSBR-delayed free on free-threaded builds when the set is shared, so concurrent readers don’t use-after-free.

Clearing empties the set before decref’ing keys, to survive re-entrancy from __del__:

c
// Objects/setobject.c
static int set_clear_internal(PyObject *self) {
    ...
    if (table_is_malloced)
        set_empty_to_minsize(so);          /* swap to smalltable first */
    else if (fill > 0) {
        memcpy(small_copy, table, sizeof(small_copy));
        table = small_copy;
        set_empty_to_minsize(so);
    }
    for (entry = table; used > 0; entry++) {
        if (entry->key && entry->key != dummy) {
            used--;
            Py_DECREF(entry->key);
        }
    }
    if (table_is_malloced)
        free_entries(table, oldsize, SET_IS_SHARED(so));
    return 0;
}

Construction

New sets start with the inline small table and no allocation:

c
// Objects/setobject.c
static PyObject *make_new_set_untracked(PyTypeObject *type, PyObject *iterable) {
    PySetObject *so = (PySetObject *)_PyType_AllocNoTrack(type, 0);
    ...
    so->fill = 0;
    so->used = 0;
    so->mask = PySet_MINSIZE - 1;   /* 7 */
    so->table = so->smalltable;
    so->hash = -1;
    so->finger = 0;
    so->weakreflist = NULL;
    if (iterable != NULL)
        set_update_local(so, iterable);   /* fills via set_add_entry */
    return (PyObject *)so;
}

PySet_New/PyFrozenSet_New wrap this with GC tracking. And frozenset(f) on an exact frozenset is idempotent — it returns the same object.

frozenset: immutability and cached hash

A frozenset uses the identical table. Immutability is enforced at the API level (PySet_Type has mutable methods, PyFrozenSet_Type does not), with one deliberate exception: PySet_Add may mutate a frozenset that is uniquely referenced, so you can fill freshly-built frozensets before they escape:

c
// Objects/setobject.c
int PySet_Add(PyObject *anyset, PyObject *key) {
    if (PySet_Check(anyset)) { ... }
    if (PyFrozenSet_Check(anyset) &&
        _PyObject_IsUniquelyReferenced(anyset)) {
        if (PyFrozenSet_CheckExact(anyset) &&
            !PyObject_GC_IsTracked(anyset) &&
            PyObject_GC_IsTracked(key))
            _PyObject_GC_TRACK(anyset);
        return set_add_key((PySetObject *)anyset, key);
    }
    PyErr_BadInternalCall();
    return -1;
}

PySet_Type.tp_hash is PyObject_HashNotImplemented (sets are unhashable), while PyFrozenSet_Type.tp_hash is frozenset_hash, which caches its result in so->hash (initialized to -1):

c
// Objects/setobject.c
static Py_hash_t frozenset_hash(PyObject *self) {
    PySetObject *so = _PySet_CAST(self);
    if (FT_ATOMIC_LOAD_SSIZE_RELAXED(so->hash) != -1)
        return FT_ATOMIC_LOAD_SSIZE_ACQUIRE(so->hash);
    Py_uhash_t hash = frozenset_hash_impl(self);
    FT_ATOMIC_STORE_SSIZE_RELEASE(so->hash, hash);
    return hash;
}

The hash is order-independent: it XORs a shuffled version of every slot’s cached hash (including null and dummy slots), then corrects for their counts, mixes in the active count, and finalizes.

Because frozensets are immutable, the cached value never goes stale. That’s the whole reason caching is safe here and nowhere else in the set code.

Frozensets also try to drop GC tracking when none of their elements are GC-tracked (_PyFrozenSet_MaybeUntrack), saving traversal cost.

pop() and the finger

set.pop() removes an arbitrary element. To avoid always scanning from slot 0, it keeps a finger index and searches forward, wrapping around:

c
// Objects/setobject.c (abridged)
PyObject *PySet_Pop(PyObject *set) {
    ...
    /* find next active entry starting at finger */
    while (entry->key == NULL || entry->key == dummy) { ... advance ... }
    /* convert to dummy, decrement used, return key */
}

(Exact implementation advances so->finger and wraps at mask.)

pop/iteration summary

Iteration (set_iter) walks the table slots in order, skipping null and dummy entries. The iterator holds a reference to the set and checks for mutation (SET_LOOKKEY_CHANGED).

Key takeaways

set and frozenset share PySetObject: fill/used/mask, a table pointer, an inline 8-slot smalltable, and (for frozensets) a cached hash.
Storage is an open-addressing hash table with three slot states; deletes become dummies to preserve probe chains.
Probing does 9 linear probes then a pseudo-random jump; load factor ~60%; growth is 4x then 2x.
Resizing reinserts active keys and drops dummies; clearing empties the set first.
Frozensets are immutable by API, but PySet_Add may fill a uniquely referenced one; their hash is computed once and cached.