Python Sets: Fast Lookups and the Order You Lose

Quick Answer

A set is an unordered collection of unique, hashable values. Membership testing is a hash lookup, so x in my_set is roughly constant time while x in my_list scans every element. That difference turns an O(n squared) duplicate check into an O(n) one. The cost is that sets have no order, no indexing, no duplicates, and cannot hold unhashable items such as lists or dicts. Use frozenset when you need a set that can itself be a key.

What a set actually is

A set stores unique values with no defined order. It is built on the same hashing machinery as a dictionary, minus the values. That one implementation detail explains every behaviour in this article: what is fast, what is impossible, and what silently disappears.

subjects = {"python", "sql", "python"}
print(subjects)          # duplicate dropped; printed order varies
print(len(subjects))     # 2

subjects.add("react")
subjects.discard("php")  # no error if missing
subjects.remove("php")   # KeyError if missing

The first thing everyone gets wrong is the empty set. {} is an empty dictionary, not a set, because dicts got the braces first. An empty set has no literal at all and must be written set().

a = {}
b = set()
print(type(a), type(b))   # <class 'dict'> <class 'set'>

The second surprise is that not everything can go in. Set members must be hashable, which in practice means immutable. Strings, numbers, tuples of immutables and frozensets are fine. Lists, dicts and other sets are not.

{[1, 2]}
# TypeError: unhashable type: 'list'

{(1, 2)}   # fine, tuples are hashable

There is a subtle equality trap on top of that. Because 1 == True and 1.0 == 1 in Python, and equal objects share a hash, a set collapses them into one member and keeps whichever arrived first. {1, True, 1.0} is {1}. That is rarely what a data cleaning script intends when a CSV column contains a mixture of integers and booleans.

Why membership testing is fast on a set and slow on a list

The reason to reach for a set is almost always membership testing. x in some_list compares against elements one at a time until it finds a match, so on average it touches half the list and in the worst case all of it. That is O(n). x in some_set hashes the value, jumps straight to the right bucket and compares a handful of candidates, which is O(1) on average.

Standing alone that difference is invisible. Put it inside a loop and it becomes the whole runtime.

# O(n squared): for every roll, scan the whole seen list
seen = []
duplicates = []
for roll in rolls:
    if roll in seen:          # O(n) scan, every iteration
        duplicates.append(roll)
    seen.append(roll)

# O(n): hash lookup instead of a scan
seen = set()
duplicates = []
for roll in rolls:
    if roll in seen:          # O(1) average
        duplicates.append(roll)
    seen.add(roll)

Both versions are three lines and look equally reasonable in a code review. On a few hundred records neither is noticeable. On a few hundred thousand, the first one is the reason your script is still running at lunchtime. This exact pattern shows up constantly in interview problems, in data cleaning and in graph traversal, where a visited set is the difference between a working BFS and one that crawls.

There is a catch worth stating, because people over-correct. Building the set costs a full pass over the data. Converting a list to a set inside a loop rebuilds it every iteration and is slower than the naive version, not faster.

# wrong: rebuilds the set on every iteration
for name in names:
    if name in set(blacklist):
        ...

# right: build once, outside the loop
blocked = set(blacklist)
for name in names:
    if name in blocked:
        ...

The other honest caveat is that O(1) here is an average. A pathological set of keys that all hash to the same bucket degrades towards a linear scan. With ordinary strings and numbers you will not meet this, but it is why the guarantee is stated as amortised rather than absolute.

Union, intersection and difference

Set operations replace whole loops with one expression, and they read the way the problem is stated.

known = {"python", "sql", "git"}
required = {"python", "react", "sql", "docker"}

print(known & required)   # {'python', 'sql'}   have and need
print(required - known)   # {'react', 'docker'} still to learn
print(known - required)   # {'git'}             extra
print(known | required)   # everything, no duplicates
print(known ^ required)   # in one but not both

That second line is a genuinely useful pattern for a placement prep tracker: the gap between a job description's skills and your own is a single subtraction rather than a nested loop.

Each operator has a method twin: & is intersection, | is union, - is difference, ^ is symmetric_difference. They are not quite interchangeable. The operators require both sides to be sets and raise TypeError otherwise, while the methods accept any iterable.

known & ["python", "go"]
# TypeError: unsupported operand type(s) for &: 'set' and 'list'

known.intersection(["python", "go"])   # {'python'}

There are in-place versions too: update, intersection_update, difference_update, matching |=, &= and -=. These mutate the set rather than returning a new one, which matters when the set is large or shared.

For comparisons, issubset and issuperset (or <= and >=) answer containment questions directly, and isdisjoint checks for no overlap without building an intersection you then throw away. Using isdisjoint instead of len(a & b) == 0 avoids allocating a whole intermediate set.

Deduplication, and the order you just lost

The one-liner everybody learns first is real and useful:

cities = ["Pune", "Kochi", "Pune", "Surat", "Kochi"]
print(list(set(cities)))
# ['Surat', 'Pune', 'Kochi']   order is not the original

The output is correct and the order is arbitrary. It is not random, it is determined by hash values and insertion history, but it is not the order you put things in and you must not rely on it. A test that asserts a particular order will pass on your machine and fail elsewhere, and for strings it can differ between runs because Python randomises string hashing by default for security reasons.

When the original order matters, use a dict instead. Dictionaries preserve insertion order in modern Python, so this gives you deduplication with order intact:

print(list(dict.fromkeys(cities)))
# ['Pune', 'Kochi', 'Surat']

If you want a stable, predictable order for output, sort explicitly: sorted(set(cities)). Never leave ordering to chance in something a user will read.

Deduplication also depends entirely on equality, which is why it fails on dictionaries and on objects without a sensible __eq__ and __hash__. Two dicts with identical contents are unhashable, so a list of API records cannot be deduplicated with set() at all. Convert each record to a hashable key first, typically a tuple of the fields that define identity:

rows = [{"roll": "CS21", "city": "Pune"}, {"roll": "CS21", "city": "Pune"}]
unique = {(r["roll"], r["city"]): r for r in rows}
print(list(unique.values()))   # one record

Finally, frozenset is the immutable version. Because it is hashable, it can be a dictionary key or a member of another set, which is exactly what you need when the thing you are deduplicating is itself a group. A set of unordered pairs, for instance, treats Pune-Mumbai and Mumbai-Pune as the same route.

routes = {frozenset({"Pune", "Mumbai"}), frozenset({"Mumbai", "Pune"})}
print(len(routes))   # 1

When a set is the wrong choice

Sets are so convenient that they get used where they actively lose information. Four cases where you should not.

When order matters. There is no indexing, no slicing, no .sort() in place, and no first element. my_set[0] raises TypeError: 'set' object is not subscriptable. If the sequence is meaningful, it is a list.

When duplicates are the data. Converting to a set to "clean" a list of exam scores destroys the fact that four students scored 78. If you need counts, collections.Counter is the right tool and gives you the uniqueness benefit as a side effect.

from collections import Counter

scores = [78, 91, 78, 65, 78]
c = Counter(scores)
print(c[78])            # 3
print(c.most_common(1)) # [(78, 3)]
print(set(c))           # {65, 78, 91}, the unique values

When items are unhashable. Lists, dicts and mutable objects cannot go in. Converting them to tuples works for nested lists, but only if they are genuinely immutable all the way down; a tuple containing a list is still unhashable.

When the collection is tiny. For four or five items the constant cost of hashing can outweigh a short scan, and a list is easier to read and debug. Reach for a set because the semantics fit, and because you expect the collection to grow, not as a reflex.

Two runtime traps to finish. You cannot modify a set while iterating over it; adding or removing members inside the loop raises RuntimeError: Set changed size during iteration. Iterate over a copy with for x in list(s): if you must. And floating point membership follows floating point equality, so 0.1 + 0.2 in {0.3} is False, for the same reason that comparison is false anywhere else in Python. Sets do not fix precision; they inherit it.

Frequently Asked Questions