CPython Set Internals

CPython’s set and frozenset are open-addressing hash tables — the same family as dict, but a deliberately different implementation. Where the modern dict is a compact, insertion-ordered table (a sparse array of small integer indices pointing into a dense, append-only entry array), a set is a plain, sparse table of (key, hash) slots with no index indirection, no dense array, and no order. The single source file Objects/setobject.c implements both set and frozenset over one C struct, PySetObject; the only structural difference is that a frozenset may cache its hash and is never mutated after construction. The collision strategy is a hybrid of linear probing (nine consecutive slots — LINEAR_PROBES) and pseudo-random perturbation probing (the same i = i*5 + 1 + perturb recurrence dict uses), tuned for the membership-test workload that dominates set usage. This note describes the layout as of CPython 3.14.5 (May 2026), grounded line-by-line in setobject.c and Include/cpython/setobject.h.

A set exists to answer one question fast: is x in this collection? The file’s own header comment is explicit that this drives the design: “Use cases for sets differ considerably from dictionaries where looked-up keys are more likely to be present. In contrast, sets are primarily about membership testing where the presence of an element is not known in advance. Accordingly, the set implementation needs to optimize for both the found and not-found case” (setobject.c lines 27–31). That asymmetry — optimizing the miss as much as the hit — is the reason the set never adopted the compact layout that the dict did, even though the two implementations share an ancestry (the file’s banner notes it was “Derived from Objects/dictobject.c” and written by Raymond Hettinger).

Mental Model — One Sparse Array, No Indirection

Think of a set as a single array of slots, each slot a tiny (key, hash) pair. The slot a key belongs in is hash & mask, where mask is table_size − 1 and the table size is always a power of two. Most slots are empty. To keep collisions rare, the table is grown long before it fills up — it is kept under three-fifths full. There is no second array, no dense packing, and crucially no recorded insertion order: iteration simply walks the raw slot array front to back, so the order you get out is an artifact of hash values and table size, not of when you inserted.

flowchart TD
    K["key = 'pear'<br/>hash(key) = 0x...A7"] --> H["i = hash & mask"]
    H --> S0["slot i: occupied by 'apple'?<br/>(hash mismatch)"]
    S0 -->|"linear scan:<br/>i+1, i+2, … i+9<br/>(LINEAR_PROBES)"| S1["slot i+1 … i+9<br/>consecutive, cache-friendly"]
    S1 -->|"all 9 occupied/mismatched"| P["perturb >>= 5<br/>i = (i*5 + 1 + perturb) & mask"]
    P --> J["jump to a far-away slot j"]
    J -->|"repeat linear scan there"| S2["slot j … j+9"]
    S2 -->|"empty slot found"| INS["insert here<br/>(key, hash)"]
    S2 -->|"matching key found"| HIT["already present — no-op"]

    style INS fill:#1f6f3f,color:#fff
    style HIT fill:#7a5c00,color:#fff

Figure: the probe sequence for one lookup. The insight is the two-scale search: within a probe, nine physically adjacent slots are scanned linearly (cheap — they share cache lines), and only when that run is exhausted does the perturbation recurrence jump to a pseudo-random far slot to break up long collision chains. A “miss” terminates the instant it hits an empty slot; a “hit” terminates when a slot’s cached hash and key both match. There is no index array between the hash slot and the stored key — the key lives directly in the slot, unlike dict’s two-array compact design.

The deliberate divergence from dict is worth stating up front because the brief turns on it. The compact dict splits storage into a sparse dk_indices array (1/2/4/8-byte integers) and a dense dk_entries array (full 24-byte records appended in insertion order). That indirection bought the dict two things: lower memory waste in the sparse part, and free insertion-order preservation. A set takes neither. Its slots are full (key, hash) records (16 bytes on a 64-bit build — see below), held directly in the hash-addressed array, and it makes no ordering promise. Why the difference? Because dicts are the runtime’s universal namespace type — every __dict__, every module globals, every keyword-argument bundle is a dict, and ordered iteration plus compactness paid for themselves across millions of small dicts. Sets are a specialized membership structure; the compact layout’s extra indirection (an index lookup then an entry lookup) would add a pointer-chase to the very operation — the miss — that sets most need to be fast, and ordering was never part of the set contract. So the set kept the simpler, flatter, order-free table on purpose.

The `PySetObject` Struct, Field by Field

Both set and frozenset are instances of the same C struct, defined in Include/cpython/setobject.h:

#define PySet_MINSIZE 8                 // every set starts with 8 slots
 
typedef struct {
    PyObject *key;                      // the stored element (borrowed-counted)
    Py_hash_t hash;                     // cached hash code of the key
} setentry;
 
typedef struct {
    PyObject_HEAD                       // refcount + type pointer (GC header separate)
 
    Py_ssize_t fill;                    // # active + # dummy (deleted) entries
    Py_ssize_t used;                    // # active entries  == len(set)
 
    Py_ssize_t mask;                    // table has mask+1 slots; always 2^k − 1
 
    setentry *table;                    // points at smalltable, or malloc'd block
    Py_hash_t hash;                     // cached hash; only meaningful for frozenset
    Py_ssize_t finger;                  // round-robin search cursor for set.pop()
 
    setentry smalltable[PySet_MINSIZE]; // 8 slots embedded inline in the object
    PyObject *weakreflist;              // list of weak references to this set
} PySetObject;

Line by line, the fields encode the table’s bookkeeping:

setentry is the slot type: a key pointer plus a cached hash. Caching the hash inside the slot is the single most important micro-optimization in the file. During a probe, the code compares the integer hash field first; only if the cached hashes are equal does it fall back to the expensive __eq__ rich comparison. Most probe steps reject a slot on the cheap integer comparison alone, never touching Python-level equality.
fill counts active plus deleted slots — every slot that is not virgin-empty. used counts only active slots and is what len() returns (PySet_GET_SIZE reads used). The gap fill − used is the number of dummy tombstones (explained below). The table grows when fill (not used) crosses the load threshold, because tombstones also lengthen probe chains.
mask is stored instead of the size because hash & mask is the per-probe operation and the mask is what it needs; the size is just mask + 1. The comment in the header says exactly this: “We store the mask instead of the size because the mask is more frequently needed.”
table “is never NULL which saves us from repeated runtime null-tests” — for a small set it points at the inline smalltable; for a larger set it points at a malloc’d block and smalltable goes unused.
hash is “Only used by frozenset objects.” A set is unhashable, so it leaves this at −1 forever; a frozenset lazily computes and caches its hash here on first hash() call.
finger is a saved cursor so that repeated set.pop() calls sweep the table round-robin instead of restarting the scan from slot 0 each time.
smalltable[8] is the embedded eight-slot table. Every set — even an empty one — carries eight setentry slots inside the object itself. This means a fresh small set never makes a separate heap allocation for its table; the table pointer just aims at this inline array. On a 64-bit build each setentry is 16 bytes (8-byte pointer + 8-byte Py_hash_t), so the inline table alone is 128 bytes, which is why sys.getsizeof(set()) reports a couple hundred bytes even for an empty set.

The Three Slot States and the `dummy` Sentinel

The header comment enumerates the three possible states of a slot precisely:

1. Unused:  key == NULL and hash == 0
2. Dummy:   key == dummy and hash == -1
3. Active:  key != NULL and key != dummy and hash != -1

An Unused (virgin) slot has never held anything: its key is NULL and its hash is 0. An Active slot holds a live element. A Dummy slot is a tombstone — it used to hold an element that was later removed. The dummy marker is a single shared sentinel object, static PyObject _dummy_struct; with #define dummy (&_dummy_struct) (setobject.c lines 61–64).

The reason a deletion cannot simply NULL the slot is the heart of open addressing. Recall how a miss terminates: a lookup walks the probe sequence and stops the moment it reaches an Unused slot, reasoning “if the key were present it would have been placed here or earlier in this chain, so it isn’t here.” Now suppose B collided with A and was placed one slot past A. If you delete A by zeroing its slot, a later search for B starts at A’s slot, sees Unused, and concludes B is absent — even though B is sitting right there in the next slot. Zeroing the slot breaks the probe chain. The dummy tombstone fixes this: a search treats a Dummy slot as “occupied, keep probing” (so the chain to B survives) while an insert treats it as “reusable, you may put a new key here.” This is exactly what the deletion code does in set_discard_entry (lines 394–410 in the 3.14.5 source):

old_key = entry->key;
entry->key = dummy;                 // mark tombstone, do NOT NULL it
entry->hash = -1;                   // dummy hash sentinel
FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, so->used - 1);  // used drops...
Py_DECREF(old_key);                 // ...but fill is unchanged: the slot is still "filled"

Note used decreases but fill does not, so the tombstone keeps counting against the load factor — deletions push you toward a resize even though the live count shrank. Tombstones are only physically reclaimed during a table resize, which rebuilds the table from the active entries and drops every dummy (set_table_resize line 357: “dummy entries aren’t copied over, of course”). This is also why a set that is churned hard — many adds and removes — will silently resize-rebuild itself to purge accumulated tombstones even when its length never changes.

The Probe Sequence — `LINEAR_PROBES` and `PERTURB_SHIFT`

The two constants that define the search are at setobject.c lines 71–76:

#ifndef LINEAR_PROBES
#define LINEAR_PROBES 9             // scan 9 adjacent slots before jumping
#endif
 
#define PERTURB_SHIFT 5             // how fast hash bits feed into the jump

The file’s design comment explains the rationale (lines 13–20): “To improve cache locality, each probe inspects a series of consecutive nearby entries before moving on to probes elsewhere in memory. This leaves us with a hybrid of linear probing and randomized probing. The linear probing reduces the cost of hash collisions because consecutive memory accesses tend to be much cheaper than scattered probes. After LINEAR_PROBES steps, we then use more of the upper bits from the hash value and apply a simple linear congruential random number generator.”

Here is the actual inner loop of the lookup, set_lookkey (lines 78–130), annotated:

static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
{
    size_t perturb = hash;              // perturb seeds from the FULL hash
    size_t mask = so->mask;
    size_t i = (size_t)hash & mask;     // initial slot = low bits of hash
    int probes;
    int frozenset = PyFrozenSet_CheckExact(so);  // 3.14.5: fast-path flag
 
    while (1) {
        entry = &so->table[i];
        // Can we run a full linear sweep without falling off the end of the table?
        probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES : 0;
        do {
            if (entry->hash == 0 && entry->key == NULL)
                return entry;           // hit an Unused slot -> key is ABSENT, stop
            if (entry->hash == hash) {  // cheap integer pre-check before __eq__
                PyObject *startkey = entry->key;
                if (startkey == key)    // identity match — same object
                    return entry;
                if (PyUnicode_CheckExact(startkey) && PyUnicode_CheckExact(key)
                    && unicode_eq(startkey, key))
                    return entry;       // fast path for two exact str objects
                if (frozenset) {        // immutable: no callback can mutate us
                    cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
                    if (cmp < 0) return NULL;
                } else {                // mutable set: guard against reentrant mutation
                    Py_INCREF(startkey);
                    cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
                    Py_DECREF(startkey);
                    if (cmp < 0) return NULL;
                    if (table != so->table || entry->key != startkey)
                        return set_lookkey(so, key, hash);  // table changed under us, restart
                }
                if (cmp > 0) return entry;  // __eq__ said yes -> FOUND
                mask = so->mask;
            }
            entry++;                    // linear step: next adjacent slot
        } while (probes--);             // up to LINEAR_PROBES adjacent slots
        perturb >>= PERTURB_SHIFT;      // shift in higher hash bits
        i = (i * 5 + 1 + perturb) & mask;  // pseudo-random jump to a far slot
    }
}

Reading the control flow: the outer while (1) is one probe group; the inner do … while (probes--) is the linear sweep of up to nine adjacent slots within a group. The probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES : 0 guard means the linear sweep is skipped entirely (zero adjacent probes) whenever i is within nine slots of the end of the table — the code never wraps the linear sweep around the array boundary; it just falls straight through to the perturbation jump. When a group is exhausted, perturb >>= PERTURB_SHIFT folds five more high-order bits of the original hash into perturb, and i = (i*5 + 1 + perturb) & mask computes the next group’s starting slot. Because perturb started as the full hash and decays five bits at a time, early jumps depend on the whole hash; once perturb reaches zero the recurrence degenerates to i = (i*5 + 1) & mask, which is a full-period linear congruential generator over a power-of-two table — guaranteeing every slot is eventually visited, so a lookup can never loop forever in a non-full table.

Two correctness subtleties in the mutable-set branch are worth dwelling on. First, the cached-hash pre-check entry->hash == hash filters out the overwhelming majority of slot mismatches with one integer compare, so Python-level __eq__ runs only on genuine hash collisions. Second, calling __eq__ can run arbitrary Python code, which could mutate the very set being searched (resize it, or even delete the element being compared). The mutable branch defends against this by incref-ing startkey across the comparison and then re-checking table != so->table || entry->key != startkey; if either changed, it restarts the whole lookup. The 3.14.5 source adds a frozenset fast-path (the int frozenset = ... flag at line 89) that skips this defensive dance for frozensets — since a frozenset is immutable, no comparison callback can alter it, so the incref/recheck is provably unnecessary and removing it speeds frozenset membership tests. This fast-path is new in the 3.14.x series (commit c05e71f61, gh-132657 / GH-136107, merged 2025-11-20); it did not exist in 3.14.0.

Resolved (2026-06-01)

The frozenset fast-path in set_lookkey was introduced after the 3.14.0 release, in the 3.14.x series. It is absent from v3.14.0 setobject.c and present in v3.14.5. Commit c05e71f61 (“[3.14] gh-132657: avoid locks and refcounting in frozenset lookups (GH-136107)”, merged 2025-11-20) is the introducing change — its diff adds exactly int frozenset = PyFrozenSet_CheckExact(so); and the if (frozenset) { ... } split inside set_lookkey (confirmed via gh api repos/python/cpython/commits/c05e71f61). A sibling commit on the same issue the same day, 072eeaf84 (GH-141183), separately optimizes PySet_Contains, not set_lookkey.

Load Factor and `set_table_resize` — the 3/5 Rule

After an insert lands in a previously-Unused slot, set_add_entry_takeref checks whether the table is too full (lines 201–209):

  found_unused:
    so->fill++;                                 // a virgin slot became occupied
    FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, so->used + 1);
    entry->key = key;
    entry->hash = hash;
    if ((size_t)so->fill*5 < mask*3)            // fill/(mask+1) < 3/5  -> still roomy
        return 0;
    return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

The test so->fill*5 < mask*3 is the three-fifths load factor, written in integer arithmetic to avoid floating point. Rearranged, it grows the table once fill reaches roughly 0.6 × (mask+1) slots. (The comparison uses mask rather than mask+1, so it triggers a hair before exactly 3/5, but the intent is the 60% threshold.) Critically the test is on fill, which includes tombstones, so a table full of dummy slots will resize even with few live entries — that is how tombstones get garbage-collected.

The growth target is used*4 for small/medium sets and used*2 once used exceeds 50,000. The motive: small sets quadruple so they don’t resize again on the next few inserts (amortizing the rebuild), while large sets only double to avoid wasting hundreds of megabytes. set_table_resize then finds the smallest power-of-two size strictly greater than that target (lines ~312–315):

size_t newsize = PySet_MINSIZE;
while (newsize <= (size_t)minused)
    newsize <<= 1;                  // smallest power of two > minused

allocates the new block (or reuses the inline smalltable if the set is shrinking back down to 8), zeroes it, and reinserts every active entry with set_insert_clean (lines 266–290). set_insert_clean is a stripped-down insert that assumes the key is absent and unique — it never runs __eq__, never checks for matches, just finds the first NULL slot along the same linear-then-perturb probe sequence and drops the key in. The file’s comment explains why this is a safety property and not only a speed one: using the full set_add_entry during a resize could trigger a comparison callback mid-rebuild and corrupt the half-built table (“there is also safety benefit since using set_add_entry() risks making a callback in the middle of a set_table_resize(), see issue 1456209”).

`frozenset` — Immutability, Hashability, and the (Non-)Singleton

frozenset shares PySetObject byte-for-byte with set; what differs is the type object, which omits all mutating methods (add, discard, pop, update, __ior__, …) and supplies a tp_hash. That tp_hash is frozenset_hash (lines ~821–833), which lazily computes and caches the hash in the struct’s hash field:

static Py_hash_t
frozenset_hash(PyObject *self)
{
    if (FT_ATOMIC_LOAD_SSIZE_RELAXED(so->hash) != -1)   // already computed?
        return so->hash;                                 // return cached value
    hash = frozenset_hash_impl(self);                    // compute once
    FT_ATOMIC_STORE_SSIZE_RELAXED(so->hash, hash);       // cache for next time
    return hash;
}

A set never has a valid hash (its hash field stays −1), and its type object’s tp_hash raises TypeError: unhashable type: 'set' — which is why a set cannot be a dict key or an element of another set, but a frozenset can. The hash itself must satisfy the data-model invariant that equal objects hash equally (Python data model, object.__hash__), and since set equality is order-independent, the hash must be too. frozenset_hash_impl (lines 779–818) achieves order-independence by XOR-ing a bit-shuffled version of every element’s cached hash — XOR is commutative and associative, so the result is independent of slot order:

for (entry = so->table; entry <= &so->table[so->mask]; entry++)
    hash ^= _shuffle_bits(entry->hash);   // fold in every slot, even empty/dummy
if ((so->mask + 1 - so->fill) & 1)         // ...then subtract out the effect of an
    hash ^= _shuffle_bits(0);              //    odd count of NULL (hash==0) slots
if ((so->fill - so->used) & 1)             // ...and an odd count of dummy (hash==-1) slots
    hash ^= _shuffle_bits(-1);
hash ^= ((Py_uhash_t)PySet_GET_SIZE(self) + 1) * 1927868237UL;  // mix in the length

The clever trick here, called out in the comment, is that the loop XORs every slot including Unused (hash==0) and Dummy (hash==-1) slots — “For speed, include null entries and dummy entries and then subtract out their effect afterwards … This allows the code to be vectorized by the compiler and it saves the unpredictable branches that would arise when trying to exclude null and dummy entries on every iteration.” Because XOR-ing the same value twice cancels, an even number of NULL slots contributes nothing automatically, and only an odd count needs the single corrective XOR afterward. The _shuffle_bits step (((h ^ 89869747) ^ (h << 16)) * 3644798167) spreads the bits of each element hash so that sets of small integers with nearby hashes don’t collapse to a handful of distinct set-hashes.

The empty-frozenset singleton no longer exists. Historically (Python 2.5 and earlier) frozenset() with no arguments returned a shared singleton, but this was removed in Python 2.6 because the singleton interfered with the C-API pattern of building a frozenset incrementally via PySet_Add() (python-dev patch discussion). In the 3.14.5 source, make_new_frozenset (lines ~1181–1192) contains exactly one identity optimization — frozenset(f) returns f itself when f is already an exact frozenset (“frozenset(f) is idempotent”) — and otherwise always builds a fresh object via make_new_set. There is no empty-frozenset cache: frozenset() is frozenset() evaluates to False (verified on CPython 3.14.5). This is unlike the empty tuple, which is cached as a singleton — () is () is True on the same build — see CPython Tuple Internals.

Set Algebra — Union, Intersection, Difference

The binary set operations are built on the same primitives. Union (|, .union()) starts from a copy of one operand and merges the other in via set_merge_lock_held, which has a fast path: if the destination table is empty it can use the comparison-free set_insert_clean for every element rather than the full membership-checking set_add_entry. Difference (-, .difference()) iterates the other operand and calls set_discard_entry for each element, with a neat optimization in set_difference_update_internal (lines ~1684–1688): “When the other set is more than 8 times larger than the base set, replace the other set with intersection of the two sets” — iterating the smaller intersection is cheaper than discarding from a giant set most of whose elements aren’t present anyway.

Intersection (&, .intersection()) shows the sharpest tuning. set_intersection (lines 1412–1486) always iterates the smaller of the two sets and probes the larger for membership:

if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
    tmp = (PyObject *)so;                       // swap so we iterate the SMALLER set
    so = (PySetObject *)other;
    other = tmp;
}
while (set_next((PySetObject *)other, &pos, &entry)) {  // walk the smaller set
    rv = set_contains_entry(so, key, hash);              // probe the larger set
    if (rv)
        set_add_entry(result, key, hash);                // common element -> result
}

Iterating the smaller operand makes the work proportional to min(|A|, |B|) membership tests rather than max. Note set_next (the internal iterator) walks the raw slot array skipping NULL and dummy slots — which is why the result set’s iteration order has no relationship to either input’s order; it reflects where elements happened to land in the freshly built result table. This is the order-independence of sets made concrete: there is simply no order to preserve.

Failure Modes and Common Misunderstandings

“Sets are ordered like dicts now.” No. The dict’s insertion-order guarantee (3.7+) came from its dense dk_entries array; the set has no such array and makes no ordering promise in any version. The apparent stability of small-int set iteration ({1, 2, 3} printing in order) is a coincidence of hash(n) == n for small ints landing in ascending slots in an 8-slot table — change the values, the size, or the insertion history and the order shifts. Relying on set iteration order is a bug.

“Removing elements frees memory.” Removal only writes a dummy tombstone and decrements used; the slot, and the whole table, stay allocated. Memory is reclaimed only on a resize-rebuild (which a shrinking set may trigger down to the 8-slot inline table) or when the set is freed. A set that grew huge and then had most elements removed keeps the large table until something forces a resize.

“An empty set() is cheap.” It carries the 128-byte inline smalltable plus the object header, so sys.getsizeof(set()) is in the low hundreds of bytes — far heavier than an empty tuple or even a small frozenset of the same length, because the table is sized for eight slots from birth.

Unhashable elements. A set element must be hashable; set_add_key calls _PyObject_HashFast and raises TypeError: unhashable type if it returns −1. This is enforced at insertion, which is why {[1, 2]} fails immediately rather than later. The element’s hash is what drives slot placement — see Object Identity and Interning for how identity, equality, and hashing interact (notably that x is y implies hash(x) == hash(y) only because identity implies equality, and the startkey == key identity short-circuit in set_lookkey exploits exactly this).

Mutating an element after insertion. Because the hash is cached in the slot at insert time, mutating an element so its hash changes leaves it stranded — it sits in a slot computed from its old hash, and a fresh lookup using the new hash probes a different chain and reports it absent. This is the general “never mutate a hashed key” hazard, identical to the dict case; sets enforce element hashability precisely to make accidental mutation harder (most hashable built-ins are immutable).

Alternatives and When the Layout Matters

Within CPython the relevant comparison is always to the dict: use a set when you need only membership and uniqueness, a dict when you need to associate values with keys and want insertion-ordered iteration. A dict with None values is sometimes (mis)used as an ordered set; if you genuinely need an order-preserving set, that pattern works because dict is ordered, whereas a real set is not. For very small membership tests against a fixed handful of literals, a tuple or even a chain of == can beat a set because the set’s hashing overhead and 128-byte footprint don’t pay off until the collection is large enough that O(1) hashing beats O(n) scanning — see CPython Tuple Internals.

frozenset is the choice whenever a set must itself be hashable: as a dict key, as a set element, or as a value that benefits from being immutable and safely shareable. Its only structural cost over set is nothing — same struct — and its hash is computed at most once and cached.

Production Notes

The set’s flat, order-free design is a load-bearing assumption in a surprising amount of code. The CPython compiler will constant-fold a set literal that appears on the right-hand side of an in test into a frozenset constant — x in {1, 2, 3} compiles the literal once into an immutable frozenset stored in the code object’s constants, rather than rebuilding a set on every execution. The 50,000-element threshold in the growth policy (used*2 above it, used*4 below) is a memory-vs-rehash-count tuning knob that has survived essentially unchanged for years — large sets in data-processing workloads (deduplication of millions of records) double rather than quadruple to keep peak memory bounded. The tombstone-purge-on-resize behavior matters for long-lived sets used as caches with high churn: a “membership cache” that adds and evicts continuously will periodically pay an invisible O(n) rebuild to clear accumulated dummy slots, which can show up as latency spikes in profiles even though the set’s length is steady. When that matters, sizing the set once (or replacing churn with a fresh set periodically) avoids the surprise. For the precise interaction of hashing, equality, and identity that underlies every probe here, see Object Identity and Interning; for how a near-identical probe drives attribute resolution through namespace dicts, see Attribute Lookup Mechanics.

vault

Explorer

CPython Set Internals

CPython Set Internals

Mental Model — One Sparse Array, No Indirection

The `PySetObject` Struct, Field by Field

The Three Slot States and the `dummy` Sentinel

The Probe Sequence — `LINEAR_PROBES` and `PERTURB_SHIFT`

Load Factor and `set_table_resize` — the 3/5 Rule

`frozenset` — Immutability, Hashability, and the (Non-)Singleton

Set Algebra — Union, Intersection, Difference

Failure Modes and Common Misunderstandings

Alternatives and When the Layout Matters

Production Notes

See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

CPython Set Internals

CPython Set Internals

Mental Model — One Sparse Array, No Indirection

The PySetObject Struct, Field by Field

The Three Slot States and the dummy Sentinel

The Probe Sequence — LINEAR_PROBES and PERTURB_SHIFT

Load Factor and set_table_resize — the 3/5 Rule

frozenset — Immutability, Hashability, and the (Non-)Singleton

Set Algebra — Union, Intersection, Difference

Failure Modes and Common Misunderstandings

Alternatives and When the Layout Matters

Production Notes

See Also

Graph View

Table of Contents

Backlinks

The `PySetObject` Struct, Field by Field

The Three Slot States and the `dummy` Sentinel

The Probe Sequence — `LINEAR_PROBES` and `PERTURB_SHIFT`

Load Factor and `set_table_resize` — the 3/5 Rule

`frozenset` — Immutability, Hashability, and the (Non-)Singleton