12.3 Internal Representation

A set stores elements by hash, in a fixed-size slot array — not by insertion order.

Hash Table

Internally, a set is a hash table — each element’s position is computed from hash(element), not from insertion order. This is what makes membership testing O(1) average: checking for an item means computing its hash and looking at one slot, not scanning everything.

Memory Allocation

A set pre-allocates hash table space up front, even when empty — which is why an empty set and a small set can report similar memory overhead.

>>> import sys
>>> sys.getsizeof(set())
216
>>> sys.getsizeof({1, 2, 3})
216

References

Like lists and tuples, each set slot holds a reference to the actual object, not a copy of its data — the same reference model covered in 6.2 Objects and Variable References. The hash table itself stores hash values and pointers, not full copies of the elements.

Performance Benefits

The hash-table design is the entire reason sets exist as a distinct type from lists — full comparison in 12.13 Performance.

Quick Interview Answer

“A set is implemented as a hash table: every element’s slot is computed from hash(element) rather than from where it was inserted, which is exactly why membership testing is O(1) average — it’s a direct lookup, not a scan. That hash table is pre-allocated up front, which is why sys.getsizeof(set()) and a small non-empty set can report the same overhead. It also explains every other set behavior in this chapter: no indexing (there’s no meaningful position), no guaranteed iteration order (elements are laid out by hash, not insertion sequence), and a requirement that every element be hashable, since an unhashable element has no way to compute a slot at all.”

Common Mistakes

• Assuming a set stores elements “in a list internally” — it’s a hash table, structurally closer to a dict’s key storage than to a list.
• Expecting memory use to scale down for a near-empty set — the hash table’s base allocation is there whether the set holds 0 or 3 elements.
• Forgetting the hash-table design is why set elements must be hashable — it’s not an arbitrary restriction, it’s a direct requirement of how the type is implemented.