Sets, Frozensets, Membership & Set Algebra

A set represents a mutable collection of unique, hashable elements. Under the hood, CPython implements sets using a modified hashtable architecture similar to dictionaries, providing average-case $O(1)$ membership checks (x in s), additions, and deletions.

This chapter details PySetObject hashtable mechanics, dummy sentinel handling during deletions, set algebra optimization fast-paths, and frozenset immutability.

1. CPython Set Architecture (PySetObject)

Unlike PyDictObject, which maps keys to values, a PySetObject stores only keys in its entry slots:

typedef struct {
    Py_hash_t key_hash;
    PyObject *key;
} setentry;

typedef struct {
    PyObject_HEAD
    Py_ssize_t fill;     /* # of active + dummy entries */
    Py_ssize_t used;     /* # of active entries */
    Py_ssize_t mask;
    setentry *table;
    Py_hash_t hash;      /* Only used for frozenset */
    setentry smalltable[PySet_MINSIZE];
} PySetObject;

Dummy Sentinel Key Deletion (Py_Dummy):

When an element is removed from a set (s.discard(item)), CPython cannot simply wipe the table entry to NULL. Clearing the slot would break open-addressing probe chains for other keys that collided and probed past that slot!

Instead, CPython replaces deleted elements with a special Dummy Sentinel Object (Py_Dummy):

• Probing algorithms treat Py_Dummy slots as occupied when searching for existing keys (continuing the probe sequence).
• Probing algorithms treat Py_Dummy slots as available when inserting new keys.

Dummy Sentinel Handling on Set Deletion:

Slot Array: [ Key A (hash1) | Py_Dummy (Deleted Key B) | Key C (hash1 collision) ]
                                      ^
                                      |
Lookup Key C: Probes index 0 (Key A) -> Probes index 1 (Py_Dummy: Continues probe!) -> Finds Key C!

2. Set Algebra & C-Level Fast Paths

Set operations (-, &, |, ^) express logic compactly and execute at C speed in CPython:

• Intersection (s1 & s2): CPython evaluates pointer sizes first. It iterates over the smaller set and performs hashtable lookups in the larger set, ensuring $O(\min(|s1|, |s2|))$ performance.
• Union (s1 | s2): Copies the larger set’s hashtable directly in memory, then inserts elements from the smaller set.
• Difference (s1 - s2): Scans the left operand, maintaining elements not present in the right operand.

required_permissions = {"read", "write", "admin"}
user_permissions = {"read", "profile"}

missing = required_permissions - user_permissions  # {'write', 'admin'}
has_access = required_permissions <= user_permissions  # False (Subset check)

3. frozenset Immutability & Hashability

While a standard set is mutable (and therefore unhashable and unusable as a dictionary key or set element), a frozenset is immutable:

• Hashable: Once constructed, a frozenset calculates and caches its overall hash attribute.
• Set of Sets: Allows building nested set structures or using sets as dictionary keys.

# Grouping permission sets into a cached dictionary
role_permissions = {
    frozenset({"read", "write"}): "EditorRole",
    frozenset({"read", "write", "admin"}): "AdminRole",
}

4. Production Trade-offs & Memory Footprint

• Set vs. List Membership: x in my_list requires an $O(N)$ linear scan. x in my_set performs an $O(1)$ hash lookup. Converting a list to a set once ($O(N)$) enables $O(1)$ membership checks across millions of operations.
• Memory Overhead: A set requires ~216 bytes of base memory plus 16 bytes per entry slot. Do not use sets for small fixed arrays where order matters and size is under 5 items.