Sets in Python: Fast Membership Tests and Set Operations

Sets are the most underused of Python's built-in collections. Plenty of code checks if item in some_list inside a loop, deduplicates with nested loops, or compares two lists element by element, when a set would make the same code both shorter and dramatically faster.

A set is an unordered collection of unique, hashable objects. Those three properties give you two superpowers: checking whether something is in a set takes roughly constant time no matter how big the set is, and you can combine sets with operators that read like the math you learned in school, such as union, intersection, and difference. This post covers creating and modifying sets, why membership tests are fast, every set operation and comparison, frozenset, practical patterns, and the gotchas that trip people up.

Creating Sets

Use curly braces with at least one element, or the set() constructor with any iterable. Duplicates collapse automatically:

nums = {3, 1, 2, 3, 1}
print(nums, len(nums))

print(set([1, 2, 2, 3]), sorted(set("banana")))

{1, 2, 3} 3
{1, 2, 3} ['a', 'b', 'n']

There's one trap right at the start: {} is an empty dict, not an empty set. Use set():

print(type({}), type(set()))

<class 'dict'> <class 'set'>

Set comprehensions work like list comprehensions with braces:

print({x % 3 for x in range(10)})

{0, 1, 2}

Elements Must Be Hashable

Sets store elements by hash, so every element must be hashable. Numbers, strings, tuples of hashable items, and frozensets are fine. Lists, dicts, and regular sets aren't:

{[1, 2]}

TypeError: unhashable type: 'list'

If you need to store a sequence, convert it to a tuple first. The lists vs tuples post explains why tuples are hashable and lists aren't.

Sets Are Unordered

A set has no defined order. Small integers often appear sorted because of how their hashes work, but that's a coincidence you shouldn't rely on. String hashes are randomized per process, so a set of strings can print in a different order every time you run your program. When you need a predictable order for output or tests, use sorted():

tags = {"python", "sets", "basics"}
print(sorted(tags))

['basics', 'python', 'sets']

For the same reason, sets don't support indexing or slicing. {1, 2}[0] raises TypeError: 'set' object is not subscriptable.

Adding and Removing Elements

s = {1, 2}
s.add(3)
s.add(2)          # already present: no effect, no error
print(s)

s.update([4, 5], (6,))   # add many, from any iterables
print(s)

s.remove(6)
s.discard(99)     # missing: silently does nothing
print(s)

{1, 2, 3}
{1, 2, 3, 4, 5, 6}
{1, 2, 3, 4, 5}

The difference between remove() and discard() is how they treat a missing element. remove(99) raises KeyError: 99, while discard(99) does nothing. Use remove() when a missing element means something went wrong, and discard() when you just want it gone.

pop() removes and returns an arbitrary element (not the "last" one, since there's no order), and clear() empties the set.

Why Membership Tests Are Fast

This is the main reason to reach for a set. Checking x in some_list compares x against each element until it finds a match, so the time grows with the list's length. A set works like a dictionary without values: it computes hash(x), jumps straight to the matching slot in its internal hash table, and checks just that slot (plus occasionally a few more on collisions). The time stays roughly the same whether the set has ten elements or ten million.

Here's a quick measurement looking up the last element of 100,000 integers, a thousand times:

import timeit

setup = "data_list = list(range(100_000)); data_set = set(data_list)"
t_list = timeit.timeit("99_999 in data_list", setup=setup, number=1_000)
t_set = timeit.timeit("99_999 in data_set", setup=setup, number=1_000)
print(f"list: {t_list:.4f}s  set: {t_set:.6f}s")

list: 0.5529s  set: 0.000021s

Your exact numbers will differ, but the gap is enormous: about half a second for the list and about twenty microseconds for the set on my machine. This is the worst case for the list since the target is at the end, but even average-case list lookups scale linearly while set lookups don't.

The Classic Fix: Convert Once, Look Up Many Times

The pattern to watch for is a membership test inside a loop:

# Slow: each "in" scans the whole list
blocked = load_blocked_ids()          # returns a list
active = [u for u in users if u.id not in blocked]

# Fast: build the set once
blocked = set(load_blocked_ids())
active = [u for u in users if u.id not in blocked]

With 10,000 users and 10,000 blocked IDs, the list version does up to 100 million comparisons. The set version does about 10,000 hash lookups. Building the set is a one-time linear cost, so it pays off as soon as you do more than a handful of lookups.

When the collection is a fixed constant, like a set of allowed HTTP methods, CPython optimizes a literal set in an in test into a frozenset constant, so if method in {"GET", "POST"}: is both readable and efficient.

Set Operations

Sets support the classic mathematical operations as both operators and methods. I'll use two small sets throughout:

a = {1, 2, 3, 4}
b = {3, 4, 5}

print(a | b)   # union: in either
print(a & b)   # intersection: in both
print(a - b)   # difference: in a but not b
print(b - a)
print(a ^ b)   # symmetric difference: in exactly one

{1, 2, 3, 4, 5}
{3, 4}
{1, 2}
{5}
{1, 2, 5}

Difference is the only one where order matters: a - b and b - a are different.

Operators vs. Methods

Each operator has a named method: union(), intersection(), difference(), and symmetric_difference(). The operators require both sides to be sets, but the methods accept any iterable, and most accept several at once:

print(a.union([5, 6]), a.intersection(range(3)), a.difference((1,)))

a | [5]

{1, 2, 3, 4, 5, 6} {1, 2} {2, 3, 4}
TypeError: unsupported operand type(s) for |: 'set' and 'list'

Use operators when you have two sets and want concise code. Use methods when the other side is a list, a generator, or a dictionary view, so you can skip the conversion.

To combine a whole list of sets, call the method on the class and unpack:

print(set.union(*[{1, 2}, {2, 3}, {4}]))
print(set.intersection(*[{1, 2, 3}, {2, 3}, {3, 2, 9}]))

{1, 2, 3, 4}
{2, 3}

Watch out for an empty list here: set.union(*[]) raises TypeError because there's no set to call the method on.

In-Place Versions

Each operation has an augmented assignment form that modifies the set in place:

c = {1, 2, 3}
c |= {4}
c &= {2, 3, 4}
c -= {3}
print(c)

{2, 4}

The matching methods are update(), intersection_update(), difference_update(), and symmetric_difference_update(). Like the other methods, they accept any iterable.

Comparing Sets

Comparison operators on sets test subset and superset relationships rather than size:

print({1, 2} <= {1, 2, 3})        # subset
print({1, 2} < {1, 2})            # proper subset (must be smaller)
print({1, 2, 3} >= {3})           # superset
print({1, 2}.isdisjoint({3, 4}))  # no elements in common
print({1, 2} == {2, 1})           # same elements, order irrelevant

True
False
True
True
True

The method forms issubset() and issuperset() accept any iterable. isdisjoint() stops at the first shared element, so it's cheaper than checking whether a & b is empty.

Because < and > mean "proper subset" and "proper superset", sets are only partially ordered. Neither {1} < {2} nor {2} < {1} is true, so sorting a list of sets doesn't produce a meaningful order.

frozenset: The Immutable Set

frozenset is to set what tuple is to list. It supports every non-mutating operation, but you can't add or remove elements after creation:

fs = frozenset({1, 2})
fs.add(3)

AttributeError: 'frozenset' object has no attribute 'add'

Because it's immutable, a frozenset is hashable. That means you can use it as a dictionary key or put it inside another set, which you can't do with a regular set:

print({fs: "pair"}[frozenset({2, 1})])

pair

That's useful whenever the identity of something is an unordered group: a pair of users in a friendship, a combination of ingredients, or a set of permissions used as a cache key.

Mixing the two types in an operation returns the type of the left operand:

print(type(fs | {3}), type({3} | fs))

<class 'frozenset'> <class 'set'>

Use frozenset for module-level constants like VALID_METHODS = frozenset({"GET", "POST", "PUT", "DELETE"}). It documents that the collection is fixed, and nothing can modify it by accident.

Practical Patterns

Removing Duplicates

set(items) removes duplicates, but it throws away order. When order matters, dict.fromkeys() deduplicates while keeping the first occurrence of each item, because dicts preserve insertion order:

emails = ["a@x.com", "b@x.com", "a@x.com", "c@x.com", "b@x.com"]
print(list(dict.fromkeys(emails)))

['a@x.com', 'b@x.com', 'c@x.com']

When you need custom logic, such as deduplicating by a normalized key, keep a "seen" set alongside your output:

seen: set[str] = set()
unique: list[str] = []
for email in emails:
    key = email.casefold()
    if key not in seen:
        seen.add(key)
        unique.append(email)
print(unique)

['a@x.com', 'b@x.com', 'c@x.com']

The seen set keeps each check constant-time, so the whole loop stays linear. The same "seen set" idea is how graph traversals avoid visiting nodes twice.

Validating Required and Unexpected Fields

Set difference is perfect for checking incoming data. A dictionary's keys() view supports set operations directly:

required = {"name", "email", "age"}
submitted = {"name": "Lena", "email": "l@x.com", "nickname": "L"}

print(sorted(required - submitted.keys()))   # missing
print(sorted(submitted.keys() - required))   # unexpected

['age']
['nickname']

The dictionaries deep dive covers why keys() views behave like sets.

Diffing Two Snapshots

Whenever you need "what was added and what was removed" between two states, such as group members, installed packages, or files in a directory, two differences answer it:

before = {"alice", "bob", "carol"}
after = {"bob", "carol", "dave"}

print("added:", sorted(after - before), "removed:", sorted(before - after))

added: ['dave'] removed: ['alice']

Finding Common Elements

Tags shared by two posts, permissions shared by two roles, or customers who bought both products: all intersections. a & b replaces a nested loop with a single expression that runs in time proportional to the smaller set.

Pitfalls

Equal Values Collapse

Sets use equality and hashing to decide uniqueness. Since 1 == 1.0 == True and they share a hash, they count as the same element:

print({1, 1.0, True})

{1}

The first one inserted is kept.

Custom Objects Use Identity by Default

Instances of your own classes are hashable, but by default they hash and compare by identity. Two objects with the same data are different set elements:

from dataclasses import dataclass


class User:
    def __init__(self, uid: int) -> None:
        self.uid = uid


print(len({User(1), User(1)}))


@dataclass(frozen=True)
class UserId:
    uid: int


print(len({UserId(1), UserId(1)}))

2
1

A frozen dataclass generates __eq__ and __hash__ based on its fields, so equal values deduplicate as expected. If you write __eq__ by hand, you must also define __hash__ consistently (and only for objects whose hashed fields don't change). The dataclasses post covers frozen dataclasses in more detail.

Don't Mutate Elements' Hashed State

If an object's hash changes after it's been added to a set, the set can no longer find it. That's why the built-in mutable types are unhashable to begin with. Follow the same rule in your own classes.

Don't Change a Set While Iterating Over It

s = {1, 2, 3}
for i in s:
    s.add(i * 10)

RuntimeError: Set changed size during iteration

Iterate over a copy (for i in list(s):) or collect changes in a separate set and apply them afterward.

Sets Cost Memory

A set uses noticeably more memory than a list of the same elements, because a hash table needs empty slots to stay fast. For one-off checks against a short list, the conversion isn't worth it. Sets earn their keep when you do many lookups or need the operations.

Quick Reference

Task	Code
Empty set	set()
Add / add many	s.add(x), s.update(iterable)
Remove (error if missing)	s.remove(x)
Remove (no error)	s.discard(x)
Membership	x in s
Union / intersection	a | b, a & b
Difference / symmetric difference	a - b, a ^ b
Subset / superset	a <= b, a >= b
No overlap	a.isdisjoint(b)
Immutable, hashable set	frozenset(iterable)
Dedupe, keep order	list(dict.fromkeys(items))

Conclusion

Sets give you uniqueness and fast membership tests for free, along with a vocabulary of operations that turns many loops into one-line expressions. Use them whenever you're asking "is this in there?" more than a few times, removing duplicates, or comparing two collections to find what's shared, added, or missing. Reach for frozenset when the set itself needs to be a dictionary key or a constant.

Keep the trade-offs in mind: sets are unordered, need hashable elements, and use more memory than lists. For counting how many times each element appears, a set isn't enough; that's what collections.Counter is for, covered in the collections module post.