Sets: dictionaries with different tradeoffs

A set is often introduced as "a collection with no duplicates." True, but incomplete. That description makes deduplication look like the main feature and hides the design decision that powers almost everything useful about sets.

Python sets are hash tables optimized around keys without associated values. They answer membership questions, enforce uniqueness, and implement union, intersection, difference, and symmetric difference. In that sense they are close relatives of dictionaries. In CPython they are even historically derived from dictionary code.

But "a dictionary with dummy values" is not the current physical layout, and the semantic tradeoffs differ. Sets do not preserve insertion order, support indexing, or accept unhashable elements. CPython's set table is optimized for membership cases where either presence or absence is common. Understanding those choices helps you know when a set removes work and when it removes information you needed.

Version note. Examples target Python 3.10 through 3.14 and were verified on CPython 3.14.7. Unordered semantics, hashability requirements, and set operations are Python behavior. Probe sequences, resize thresholds, table fields, and byte counts are CPython 3.14 implementation details.

Uniqueness follows equality and hashing

A set does not compare every new item with every existing item. It hashes the candidate, uses that hash to locate possible table slots, and confirms a candidate with identity or equality. Different objects that compare equal occupy one logical set element.

values = {True, 1, 1.0, 2}

print("[result] unique value count:", len(values))
print("[check] True and 1.0 are members:", True in values, 1.0 in values)
print("[check] values equal {1, 2}:", values == {1, 2})

2
True True
True

True, 1, and 1.0 compare equal and have equal hashes, as Python requires for equal hashable values. The set keeps one representative. Which equal object remains visible should not carry domain meaning; normalize inputs first when type distinctions matter.

Hash collisions do not collapse unequal elements. Here both objects deliberately return the same hash:

class Token:
    def __init__(self, text):
        self.text = text

    def __hash__(self):
        return 7

    def __eq__(self, other):
        return isinstance(other, Token) and self.text == other.text


left = Token("left")
right = Token("right")
tokens = {left, right}

print("[check] colliding hashes:", hash(left), hash(right))
print("[check] distinct tokens retained:", len(tokens), left in tokens, right in tokens)

7 7
2 True True

Python guarantee. Equal hashable objects must have equal hashes. Unequal objects may collide. A set uses equality, not the hash alone, to decide whether an element is already present.

Average membership is constant time when hashes distribute well and equality is inexpensive. Worst-case behavior can degrade toward linear time under heavy collisions. Hash tables offer expected performance, not a per-operation deadline.

Hashability is the admission price

Set elements must remain findable after insertion. If an element's hash changed while stored, lookup would start in a different part of the table. Python therefore rejects mutable built-in containers such as lists, dictionaries, and sets as elements:

for candidate in ([1, 2], {"id": 1}, {1, 2}):
    try:
        {candidate}
    except TypeError as error:
        print("[error] unhashable candidate:", type(candidate).__name__, "->", type(error).__name__)

list -> TypeError
dict -> TypeError
set -> TypeError

Tuples are hashable only when all their elements are hashable. Custom classes that define value equality need a compatible hash based on immutable state. A frozen data class is often the least surprising expression of that contract:

from dataclasses import dataclass


@dataclass(frozen=True)
class Permission:
    resource: str
    action: str


grants = {
    Permission("invoice", "read"),
    Permission("invoice", "approve"),
}

print("[check] equivalent permission is granted:", Permission("invoice", "read") in grants)

Mutability and hashability are related through observable equality, not through a blanket rule that every object must be physically immutable. Ordinary user-defined instances are hashable by identity unless equality is redefined. That can be correct for identity sets, but it is different from deduplicating equal domain values.

As with dictionary keys, never persist hash() as an identifier. String and bytes hashes are randomized between ordinary interpreter processes, and hash values are not a stable serialization format.

Set algebra communicates the question

The major advantage over a dictionary is not fewer keystrokes. It is a vocabulary for relationships among collections:

requested = {"read", "write", "delete"}
granted = {"read", "write", "share"}

print("[result] requested and granted:", requested & granted)  # intersection
print("[result] requested but not granted:", requested - granted)  # missing grants
print("[result] requested or granted:", requested | granted)  # either side
print("[result] on exactly one side:", requested ^ granted)  # exactly one side
print("[check] read is a granted subset:", {"read"} <= granted) # subset
print("[check] requested excludes archive and restore:", requested.isdisjoint({"archive", "restore"}))

Exact printed order is intentionally unspecified, but the mathematical results are:

{'read', 'write'}
{'delete'}
{'read', 'write', 'delete', 'share'}
{'delete', 'share'}
True
True

Set comparisons are subset and superset relationships, not sorting. Two nonempty disjoint sets are neither less than, equal to, nor greater than one another. There is only a partial order:

left = {1, 2}
right = {2, 3}

print("[check] subset, superset, and equality:", left < right, left > right, left == right)
print("[result] non-canonical partial sort:", sorted([left, right]))

The first line is False False False. The second line completes, but its output should not be interpreted as a canonical ordering: the docs explicitly say sorting a list of sets does not define the order when comparisons are partial. For deterministic presentation, sort the elements inside each set using an application-defined key and then sort those resulting sequences.

Methods and operators also accept different inputs. Operators require set-like operands, which catches some mistakes; methods accept any iterable:

active = {"api", "worker", "scheduler"}

print("[result] active names in sequence:", active.intersection(["api", "web"]))

try:
    active & ["api", "web"]
except TypeError as error:
    print("[error] set operator with list:", type(error).__name__)

Use methods when streaming or sequence inputs are intentional. Use operators when the expression is genuinely set algebra between set values.

Unordered does not mean randomly shuffled

Python defines sets as unordered collections. There is no indexing or slicing, and iteration order is not an insertion-order guarantee:

names = set()
for name in ["parser", "worker", "api"]:
    names.add(name)

print("[result] arbitrary set element:", next(iter(names)) if names else "empty")
print("[result] alphabetically sorted names:", sorted(names))

Only the sorted output is suitable when the required order is alphabetical. next(iter(names)) returns some element, not the first inserted element and not the minimum.

In an unchanged CPython set, iteration typically remains stable within one process because it scans the unchanged hash table. Across processes, randomized hashes can change string placement. Resizing or mutation can change placement within a process too.

CPython detail, not a promise. Same-run stability of an unmodified set is a consequence of the current table implementation. Python's language contract remains unordered. Tests, APIs, generated files, and user-facing output should sort explicitly when order matters.

set.pop() follows the same contract: it removes an arbitrary element. CPython 3.14 keeps an internal search finger and scans table slots, but that does not make the result FIFO, LIFO, minimum, or random. Use a list, deque, heap, or random selection strategy when one of those policies is required.

CPython sets are not compact dictionaries

Modern CPython dictionaries separate a sparse index table from a compact insertion-ordered entry array. Sets do not simply reuse that layout without values. CPython 3.14's PySetObject uses its own open-addressed table whose active cells hold a key pointer and cached hash.

set table
+----------------+----------------+----------------+----------------+
| empty          | key *, hash    | dummy          | key *, hash    |
+----------------+----------------+----------------+----------------+
        ^ probe begins from bits selected from the element hash

Lookup starts from an index derived from the hash. CPython checks a short run of nearby entries for cache locality, then mixes more hash bits into subsequent probes. The source describes this as a hybrid of linear and randomized probing. It is tuned for both found and not-found membership tests because, unlike many dictionary workloads, set queries commonly do not know whether an item exists.

Small sets keep a small table inside the set object. Medium and large sets allocate a separate table. Those are private details: Python 3.14 even soft-deprecates the C API's PySet_MINSIZE constant to discourage external code from depending on a fixed internal table size.

The practical message is not to reproduce the probe recurrence. It is to avoid transferring every dictionary fact to sets. Dictionary insertion order has been a language guarantee since Python 3.7. Set insertion order is not. Dictionary and set memory profiles differ. Their source has shared ancestry, not one interchangeable representation.

Growth, empty space, and deleted cells

Open addressing needs genuinely unused cells so unsuccessful lookup can terminate. It also needs a special deleted marker: turning a removed cell immediately into an ordinary empty cell could break a probe path to another colliding element.

CPython calls these deleted cells dummy entries. Future insertions may reuse them, and rebuilding the table purges them. We can observe stepped allocation without touching private fields:

import sys


values = set()
previous = None

for count in range(100):
    if count:
        values.add(count)

    shallow_bytes = sys.getsizeof(values)
    if shallow_bytes != previous:
        print(f"{count:>2} elements -> {shallow_bytes:>5} bytes")
        previous = shallow_bytes

On 64-bit CPython 3.14.7 in our environment this printed:

 0 elements ->   216 bytes
 5 elements ->   728 bytes
19 elements ->  2264 bytes
77 elements ->  8408 bytes

These thresholds and sizes are measurements, not API. They show that hash tables reserve empty capacity and grow in discontinuous steps. sys.getsizeof() is shallow and excludes the referenced element objects.

Deletion does not promise immediate release of table memory. clear() resets an existing set to its small empty representation in CPython 3.14, while a sequence of individual removals can leave a larger allocation and dummy entries until a rebuild. Do not schedule ritual copies without evidence; measure a long-lived, churn-heavy workload if retained table storage matters.

Mutation and iteration do not mix

Unlike a list iterator, a CPython set iterator records the set's used-element count and raises when that count changes:

values = {1, 2, 3}

try:
    for value in values:
        if value == 2:
            values.add(4)
except RuntimeError as error:
    print(type(error).__name__)

RuntimeError

Do not use the check as a transactional guarantee. A mutation that preserves size, callbacks from custom __hash__ or __eq__, implementation differences, or concurrent access are poor foundations for reasoning about an active iterator. Treat mutation during set iteration as unsupported application logic.

Build a result or iterate over a snapshot:

values = {1, 2, 3, 4, 5}
values = {value for value in values if value % 2}
print("[check] filtering retained odd values:", values == {1, 3, 5})

Use in-place methods such as intersection_update() when no iterator over the same set is active and retaining object identity is useful.

Frozenset makes a set into a value

frozenset provides the non-mutating set operations but no add(), remove(), or in-place updates. When all elements are hashable, the frozenset itself is hashable, so it can be a dictionary key or another set's element:

routes = {
    frozenset({"GET", "HEAD"}): "read handler",
    frozenset({"POST"}): "create handler",
}

methods = frozenset({"HEAD", "GET"})
print("[result] handler for GET and HEAD:", routes[methods])

groups = {frozenset({"alice", "bob"}), frozenset({"carol"})}
print("[check] group lookup ignores order:", frozenset({"bob", "alice"}) in groups)

read handler
True

Frozenset equality and hashing are order-independent, which makes it appropriate for unordered composite identities: an undirected graph edge, a capability bundle, or a canonical group. A sorted tuple is a different representation. It imposes orderability during construction and preserves multiplicity unless deduplicated; choose based on domain semantics, not merely hashability.

Mixed binary operations return the type of the left operand for built-in set types:

mutable = {1, 2}
frozen = frozenset({2, 3})

print("[result] mutable-left union type:", type(mutable | frozen).__name__)
print("[result] frozen-left union type:", type(frozen | mutable).__name__)

set
frozenset

Keep operand order intentional when the result's mutability matters.

Deduplication can destroy information

list(dict.fromkeys(items)) and list(set(items)) both remove equal duplicates, but they promise different things. Dictionaries preserve first insertion order. Sets do not preserve insertion order.

events = ["queued", "running", "queued", "done", "running"]

ordered_unique = list(dict.fromkeys(events))
unordered_unique = set(events)

print("[result] first-seen event order:", ordered_unique)
print("[check] unordered unique events:", unordered_unique == {"queued", "running", "done"})

['queued', 'running', 'done']
True

Choose a set when the result is conceptually a set and later operations benefit from membership or algebra. Choose dict.fromkeys when first-seen order is part of the result. Neither handles unhashable values; a linear equality-based strategy or domain key extraction may be necessary.

Sets also retain only one representative from an equality class. They cannot count duplicates; use collections.Counter. They cannot associate metadata; use a dictionary. They cannot explain where an item came from; retain provenance separately.

Choosing the representation

Use a set when uniqueness and repeated membership are central and elements have stable hash semantics. It is especially effective for visited nodes, permission checks, dirty identifiers, joins between key collections, and duplicate suppression where order has no meaning.

• use frozenset for an immutable unordered value, a mapping key, or a member of another set;
• use a dictionary when each unique key carries a value or insertion order matters;
• use dict.fromkeys() when deduplicating while preserving first occurrence;
• use Counter when multiplicity is information;
• use a list or tuple when order, duplicates, indexing, or unhashable elements matter;
• use a bit mask or specialized bit set for a known dense integer universe when representation size and bulk operations dominate;
• use a database index or external store when the collection does not fit the process or must be shared durably.

For tiny collections, linear scanning may be simpler and sometimes faster than hashing overhead. For one membership query, constructing a set first usually adds unnecessary work. For a thousand queries against the same large collection, retaining a set often pays quickly. Measure representative objects because expensive custom hashes and equality methods can dominate container mechanics.

Exercises: test the model

1. Create three unequal objects with a constant hash and print from __eq__. Compare successful and unsuccessful membership probes.
2. Design a frozen domain object for a set of active subscriptions. Identify which fields define equality and why none may change while stored.
3. Run the shallow growth experiment, remove all but one element individually, and compare that size with a newly constructed one-element set. Label every conclusion that is CPython-specific.
4. Implement ordered deduplication with dict.fromkeys(). Then implement unordered deduplication with a set and explain which information each result retains.
5. Model undirected graph edges as two-element frozensets. Decide how your representation should handle a self-loop and justify the semantics.
6. Given several permission sets, compute users who have all required permissions, any forbidden permission, and no overlap with an administrative set.

Keep this model

A set is a hash table for keys without associated values, designed around membership, uniqueness, and algebra. Hashing routes a lookup; equality confirms an element. Empty capacity keeps ordinary probes short, and deleted markers keep collision paths intact.

The resemblance to dictionaries is useful but bounded. CPython sets have their own open-addressed table and workload tuning. Python guarantees dictionary insertion order but deliberately leaves sets unordered. A set gains fast expected membership and expressive algebra by giving up positions, duplicates, values, and mutable elements.

When a set surprises you, ask:

1. What equality and hash semantics define one element?
2. Did conversion discard order, multiplicity, type distinctions, or provenance?
3. Is the observed order or memory behavior a Python guarantee or a CPython accident?

If the answers fit the domain, the set is doing more than saving syntax: it is removing work by choosing the right semantics.

Primary sources

• Python 3.14 set and frozenset types
• Python 3.14 data model: object.__hash__
• Python 3.14 C API: set objects
• CPython 3.14 set implementation
• CPython 3.14 set object structure
• Python 3.14 collections.Counter
• sys.getsizeof documentation