Why this matters
Some questions are about membership, not order or position: Have I seen this item before? Which users are in both groups? Which required fields are missing? A set is an unordered collection of distinct items, built for exactly these questions. Testing whether an item is in a set takes about the same time whether the set has ten items or ten million, while the same test on a list gets slower with every item. Choosing a set at the right moment can turn a program that takes minutes into one that takes milliseconds.
Creating sets
Sets are written with curly braces, or created from any iterable with set():
primes = {2, 3, 5, 7}
letters = set("hello")
empty = set() # not {}: that is an empty dict
print(len(primes), 3 in primes, sorted(letters))4 True ['e', 'h', 'l', 'o']Two properties define a set:
- No duplicates. Adding an item that is already present does nothing.
set("hello")has four elements, because the secondlis the same as the first. Converting to a set is the quickest way to remove duplicates (but you lose the order). - No order. There is no first element and no indexing:
primes[0]raisesTypeError: 'set' object is not subscriptable.
Never rely on set order
When you print a set or loop over it, the items come out in some order, determined by their hash values and the set's internal size. For small integers it often looks sorted; for strings it changes from one run of the program to the next, because string hashing is randomized per process:
$ python3 -c 'print({"apple", "banana", "cherry"})'
{'cherry', 'apple', 'banana'}
$ python3 -c 'print({"apple", "banana", "cherry"})'
{'banana', 'cherry', 'apple'}So whenever output must be predictable (always, in tests and in learnprog exercises), sort before printing: sorted(s) returns a list in a defined order.
Modifying sets
tags = {"python"}
tags.add("tutorial") # add one item
tags.update(["beginner", "python"]) # add many; duplicates ignored
tags.discard("missing") # remove if present, no error otherwise
tags.remove("tutorial") # remove; KeyError if absent
print(sorted(tags))['beginner', 'python']pop() removes and returns an arbitrary element, and clear() empties the set.
Set algebra
Sets support the operations from mathematics, as operators and as methods:
python_devs = {"ada", "bob", "cy", "dee"}
rust_devs = {"cy", "dee", "eve"}
print(sorted(python_devs | rust_devs)) # union: in either
print(sorted(python_devs & rust_devs)) # intersection: in both
print(sorted(python_devs - rust_devs)) # difference: in the first only
print(sorted(python_devs ^ rust_devs)) # symmetric difference: in exactly one['ada', 'bob', 'cy', 'dee', 'eve']
['cy', 'dee']
['ada', 'bob']
['ada', 'bob', 'eve'] python_devs rust_devs
+-----------+-----+-----------+
| ada bob | cy | eve |
| | dee | |
+-----------+-----+-----------+
only python both only rustThe method forms (a.union(b), a.intersection(b), a.difference(b)) also accept any iterable, not just sets: python_devs.union(["zed"]). Comparisons test subset relations: a <= b means every element of a is in b, and a.isdisjoint(b) means they share nothing.
A typical real use, checking required fields:
required = {"name", "email", "password"}
submitted = {"name": "Ada", "password": "x"}
missing = required - submitted.keys()
print(sorted(missing))['email'](Dict key views behave like sets, so - works on them directly.)
What happens underneath: sets are hash tables
A set is implemented like a dict without values: a hash table of keys. To test x in s, Python computes hash(x), jumps to the corresponding slot, and checks equality with whatever is there. No scanning is needed, so membership, add and discard are O(1) on average. A list must compare x against items one by one, O(n).
The difference is dramatic at scale. Checking 10,000 lookups against 10,000 items:
import time
items_list = list(range(10_000))
items_set = set(items_list)
t = time.perf_counter()
hits = 0
for n in range(10_000):
if n in items_list:
hits += 1
print("list:", round(time.perf_counter() - t, 3), "s")
t = time.perf_counter()
for n in range(10_000):
if n in items_set:
hits += 1
print("set: ", round(time.perf_counter() - t, 4), "s")On a typical machine the list version takes about half a second and the set version under a millisecond. The cost: a set uses more memory than a list, and loses order.
Because sets are hash tables, the same rule as for dict keys applies: elements must be hashable. Numbers, strings and tuples of hashable items are fine; lists, dicts and sets are not:
s = {[1, 2]}TypeError: unhashable type: 'list'frozenset
A set is mutable, so it is itself unhashable: you cannot put a set inside a set or use it as a dict key. The immutable variant, frozenset, can:
pair = frozenset({"ada", "bob"})
meetings = {pair: "Monday"}
print(meetings[frozenset({"bob", "ada"})])MondayOrder does not matter for equality, so {"bob", "ada"} finds the same key. That makes frozensets handy for unordered pairs.
Common mistakes
{}for an empty set: it is a dict. Useset().- Printing a set in checked output: the order is unpredictable. Sort it.
set("word")versus{"word"}: the first is a set of letters, the second a set containing one string.- Expecting order to be preserved when deduplicating with
set(items): if order matters, deduplicate with a loop and aseenset (as in the exercise), or uselist(dict.fromkeys(items)), which keeps first occurrences because dicts preserve insertion order. removeof a missing element:KeyError. Usediscardwhen absence is fine.
Recap
- A set holds distinct hashable items with no order:
{1, 2},set(iterable),set()for empty. in,addanddiscardare O(1) on average because a set is a hash table; lists are O(n) for membership.|,&,-,^give union, intersection, difference and symmetric difference.- Never depend on set iteration order; sort for output.
frozensetis the immutable, hashable version.
Going further: read "Sets" in the official tutorial (section 5.4) and the set section of the Library Reference ("Set Types"). Try python3 -c 'print({"a", "b", "c"})' several times, then with PYTHONHASHSEED=0 set in the environment, and explain the difference.