Sets Performance Better vs Lists — Why?
Hash tables, O(1) average-case operations, and when sets dramatically outperform lists in Python.
Python sets outperform lists for membership testing, insertion, and deletion because a set is backed by a hash table, while a list is a simple array that must be scanned element by element.
Checking x in my_set computes one hash and jumps straight to the answer — O(1) on average — whereas x in my_list compares against every element until it finds a match, O(n).
With a million elements, that is the difference between one operation and up to a million comparisons; in practice a set lookup can be tens of thousands of times faster.
The trade-offs: sets hold only unique, hashable elements, don't support indexing, and use more memory per element, and dense lists still iterate faster.
The rule is simple — lots of in checks means use a set; ordered data and heavy iteration means use a list.
Why Sets Excel: The Hash Table
A Python set is backed by a hash table.
When you add an element, Python computes hash(element) and stores it at that hash's bucket.
When you look up an element with x in my_set, Python computes the hash again and jumps directly to that bucket — one operation, regardless of how many elements are in the set.
This gives sets O(1) average-case complexity for:
- Membership testing:
x in my_set - Add:
my_set.add(x) - Remove:
my_set.discard(x)
A list stores elements in contiguous memory in insertion order.
Membership testing (x in my_list) scans every element sequentially — O(n).
For 1,000,000 elements, that's up to 1,000,000 comparisons vs one hash computation.
Why Are Set Lookups O(1) Even With a Million Elements?
CPython implements sets with open addressing: a sparse array of slots where each element's position is derived from its hash value. A lookup masks the hash down to a slot index and checks that slot directly — no scanning. If two elements hash to the same slot (a collision), CPython probes a deterministic sequence of alternative slots, mixing in more bits of the hash each step, until it finds the element or an empty slot.
To keep those probe chains short, the table stays deliberately sparse: when it fills past roughly three-fifths of capacity, CPython allocates a larger table and rehashes everything into it.
That resize is O(n), but it happens so rarely that insertion still averages out to O(1) — the same amortized trick lists use for append.
The fine print: O(1) is the average case. If every element collided (pathological or adversarial hashes), lookups would degrade toward O(n) — which is why Python randomizes string hashing per process.
How Do List and Set Operations Compare in Big-O?
| Operation | list | set |
|---|---|---|
Membership — x in c | O(n) | O(1) average |
Insert — append / add | O(1) amortized | O(1) average |
Remove by value — remove / discard | O(n) | O(1) average |
Access by index — c[i] | O(1) | Not supported |
| Iterate all elements | O(n), cache-friendly | O(n), slower per element |
| Deduplicate | O(n²) naive | O(n) — set(my_list) |
| Union / intersection | O(n × m) | O(n + m) / O(min(n, m)) |
How Big Is the Difference in Practice?
Measure it yourself with timeit — a worst-case membership test (the element sits at the very end of the list):
import timeit
setup = 'data = list(range(1_000_000)); s = set(data)'
print(timeit.timeit('999_999 in data', setup=setup, number=100))
# ~1.1 s — the list scans a million elements, 100 times
print(timeit.timeit('999_999 in s', setup=setup, number=100))
# ~0.000004 s — the set hashes once per checkSame data, same question, five orders of magnitude apart — and the gap keeps widening as the collection grows, because the list's cost scales with n while the set's stays flat.
Iteration: Where Lists Have the Edge
Sets use sparse, scattered memory — the hash table has empty buckets between entries. Iterating requires walking the internal array, skipping gaps. Lists store elements densely — sequential memory access is cache-friendly and fast.
For tight iteration loops over large collections, lists are faster than sets. This is the one case where the hash table structure works against sets.
What Do Sets Cost You?
The O(1) lookups aren't free. Know the trade-offs before converting every list in your codebase:
- More memory — the hash table must stay sparse, so a set typically uses several times the memory of a list holding the same elements (each entry also stores its cached hash)
- Elements must be hashable — numbers, strings, and tuples work; mutable types like lists and dicts raise
TypeError: unhashable type. Convert inner lists to tuples first - No order, no indexing — sets don't remember insertion order and don't support
s[0]or slicing; if order matters, a set is the wrong tool - Duplicates are silently dropped — usually the point, but a bug if your data legitimately contains repeats you need to keep
For small collections — a handful of elements — none of this matters and neither does the speed difference; a list membership check over five items is effectively instant. The set advantage is a scaling advantage.
When to Use Sets
- Membership testing at scale — filtering large datasets for element presence
- Deduplication —
unique = set(my_list)removes duplicates instantly - Set algebra — union, intersection, difference operations at scale
- Data analysis — finding unique values, shared elements across datasets
- Large-scale computation — any lookup-heavy algorithm benefits from O(1) membership
The Practical Rule
- Lots of
inchecks? → use a set - Lots of iteration / indexing? → use a list
- Need both? → keep a list for order, maintain a parallel set for lookups
See also: List vs Set in a Minute — a deeper benchmark comparison with iteration and membership timing.