Skip to content

A set is a hash table

Level: 101 → 201 · for Python programmers

One line: Python's set is the mathematical set plus one rule, that members must be hashable, and almost every set gotcha follows from one of the two: from "a set is only its members", or from "membership is decided by hash and ==", with a third, smaller rule on top: operators insist on sets, methods accept any iterable.

This page owns the Python half of sets. The mathematics (what a set is, the laws, De Morgan, why chained ^ keeps what is in an odd number of sets) is the math library's Sets chapter ↗, and its Sets in Python ↗ page maps each law onto the operator here.

The two rules

The math library's What is a set? ↗ ends with the rule mathematics settled on: a set is its members and nothing else, so two sets with the same members are equal. Python's set obeys that rule to the letter, and most of what books list as its "characteristics" are consequences of it:

  • No order. Order is not membership, so {2, 5} == {5, 2}. A set can be iterated, but the order it comes out in is an accident of storage, and there is no s[0].
  • No duplicates. Being a member twice is the same as being a member once, so {1, 1, 2} == {1, 2}.
  • One empty set. set(), however it was reached. It is written set() because {} was already taken by the empty dict.

The second rule is Python's own. A set is a hash table: to decide whether x is a member, Python computes hash(x), looks in that slot, and confirms with ==. So:

  • Members must be hashable. A list, a dict or a set can change after it is stored, its hash would change with it, and the set would look in the wrong slot. So {[1, 2]} and s.add(other_set) raise TypeError: unhashable type. A tuple of hashables and a frozenset are fine. It is not the same as "immutable": (1, [2]) is a tuple and still unhashable, because it holds a list. The sibling Python library's Defining __eq__ deletes __hash__ ↗ shows the failure this rule prevents: an object whose fields change while it sits in a set can no longer be found there.
  • Equal means the same member. True == 1 == 1.0 and their hashes agree, so {True, 1, 1.0, '1', (1,)} has three members, not five.
  • Membership is fast. x in s is one hash lookup, whatever the size of s; x in some_list scans the list.

The third rule is about manners, not meaning: a | b needs two sets, and a.union(b) accepts any iterable, converts it, and takes several at once. The notes this page is merged from say "methods are more forgiving", and section 3 shows exactly how.

The output

Verified output of a_set_is_a_hash_table_py.py — regenerated by tools/run_examples.py, never hand-typed.

1. CREATING A SET: WHICH OF THESE IS {'a', 'b', 'c'}?
   set('abc')               yes  set {'a', 'b', 'c'}
   set(['a', 'b', 'c'])     yes  set {'a', 'b', 'c'}
   set('a', 'b', 'c')       no   TypeError
   {'a', 'b', 'c'}          yes  set {'a', 'b', 'c'}
   {('a', 'b', 'c')}        no   set {('a', 'b', 'c')}
   set(x) takes ONE iterable and adds each thing it yields;
   braces take each thing written between them, whole.
   set('foo') = {'f', 'o'}      {'foo'} = {'foo'}
   type({}) = dict         type(set()) = set      the empty set has no literal
   built by add(), one at a time:  {'CP0140.1', 'EF3616.3', 'XJ8113.5'}
   comprehension {2*x for x in [1, 2, 3]} = {2, 4, 6}

2. MEMBERSHIP IS DECIDED BY hash AND ==
   {True, 1, 1.0, '1', (1,)} has 3 members, not 5:
   True == 1 == 1.0 is True, and hash(True) == hash(1) == hash(1.0) is True
   so the three are one member; the first one written is the one kept.
   {[1, 2]}               -> TypeError
   {tuple([1, 2, 1])}     -> set {(1, 2, 1)}
   {frozenset({1, 2})}    -> set {frozenset({1, 2})}
   {(1, [2])}             -> TypeError
   s1.add(s2)             -> TypeError
   s1.update(s2)          -> s1 is now {'a', 'b', 'c', 'd', 'e'}
   s1.add(frozenset(s2))  -> 4 members: 3 letters and 1 frozenset
   add() puts in ONE member; update() puts in every member of an iterable.
   A set can hold a frozenset, never a set: a set can change, so its
   hash could change after it was filed, and it would be lost.

3. OPERATOR OR METHOD: THE SAME ANSWER, DIFFERENT MANNERS
   a = {1, 2, 3, 4}   b = {3, 4, 5}
   operation             operator  method                     result
   union                 a | b     a.union(b)                 {1, 2, 3, 4, 5}
   intersection          a & b     a.intersection(b)          {3, 4}
   difference            a - b     a.difference(b)            {1, 2}
   symmetric difference  a ^ b     a.symmetric_difference(b)  {1, 2, 5}
   subset                a <= b    a.issubset(b)              False
   superset              a >= b    a.issuperset(b)            False
   proper subset         a < b     (none)                     False
   disjoint              (none)    a.isdisjoint(b)            False
   membership            3 in a    a.__contains__(3)          True
   Every row with both forms gives the same result for two sets.
   In words, with engineers = {'ann', 'bob', 'sue', 'vic'}, managers = {'sue', 'tom'}:
     'bob' in engineers                               True                                 is bob an engineer?
     engineers & managers                             {'sue'}                              who is both?
     engineers | managers                             {'ann', 'bob', 'sue', 'tom', 'vic'}  who is either?
     engineers - managers                             {'ann', 'bob', 'vic'}                engineers who are not managers
     managers - engineers                             {'tom'}                              managers who are not engineers
     engineers >= managers                            False                                is every manager an engineer?
     {'bob', 'sue'} < engineers                       True                                 are both engineers, and not all of them?
     engineers ^ managers                             {'ann', 'bob', 'tom', 'vic'}         who is in exactly one of the two?
     (engineers | managers) - (engineers ^ managers)  {'sue'}                              either, minus exactly one: both
   The difference is what they accept. A tuple on the right:
     a | t                        -> TypeError
     a.union(t)                   -> set {1, 2, 3, 4, 5}
     a <= t                       -> TypeError
     a.issubset(t)                -> False
     a.union([9], 'x', range(2))  -> set {0, 1, 2, 3, 4, 9, 'x'}
   Operators need a set (or frozenset) on both sides; methods take any
   iterable, and several of them at once.

4. CLAIMS FROM THE NOTES, CHECKED
   claim:  'in' works but .__contains__() cannot be used
           x1.__contains__('a') = True: it is what 'in' calls. False.
   claim:  '-' has no corresponding method
           x1.difference({'a'}) = {'b', 'c'}. False.
   claim:  issubset and issuperset have no operator (N/A)
           <= and >= are those operators; {'a'} <= x1 is True. False.
   claim:  isdisjoint has no operator
           True; the nearest is 'not (a & b)', which builds a set first.
   claim:  the + operator is not supported for sets
           TypeError. True; use |.
   claim:  s1.add(s2) fails, use update()
           True, section 2: a set is unhashable.
   claim:  an empty set is falsy
           bool(set()) = False. True.
   claim:  issubset() of an empty iterable returns False
           set().issubset([]) = True; only a non-empty set gives False. False.
   claim:  {0,1,2,3,4} & {0,2,3,4} & {0,2,5}: the only common element is {2}
           it is {0, 2}; 0 is in all three. False.
   claim:  union takes several sets at once, and so does symmetric_difference
           a.union(b, c) works; TypeError. Half true.

5. CHAINING: LEFT TO RIGHT, AND WHAT ^ OF THREE MEANS
   s1 = {0, 1, 2, 3, 4}   s2 = {2, 3, 4}   s3 = {2, 5}
   s1 | s2 | s3 = {0, 1, 2, 3, 4, 5}
   s1 & s2 & s3 = {2}
   s1 ^ s2      = {0, 1}
   s1 ^ s2 ^ s3 = {0, 1, 2, 5}   = (s1 ^ s2) ^ s3 = {0, 1} ^ {2, 5}
   in how many of the three sets each element is:
     0:1  1:1  2:3  3:2  4:2  5:1
   elements in an odd number of them:  {0, 1, 2, 5}   same set: True
   So ^ over many sets keeps what appears an odd number of times,
   not 'what is in exactly one'. 2 is in all three and survives.
   s1 - s2 - s3 = {0, 1}  = (s1 - s2) - s3;  s1 - (s2 - s3) = {0, 1, 2}
   | & ^ are associative, so grouping never matters for them; - is not.
   s4 = s2 | s1 | s3;  s4 |= {11, 22}  ->  {0, 1, 2, 3, 4, 5, 11, 22}
   Every operator has an in-place form: |= &= -= ^= change the left set.

6. EQUALITY: == ASKS ABOUT MEMBERS, AND NOTHING ELSE DOES
   p = {1, 9}   q = {9, 1}   list(p) = [1, 9]   list(q) = [9, 1]
   p == q                          True      the right test
   list(p) == list(q)              False     order of iteration is not membership
   {1}.difference({1, 2}) == set() True      only says {1} <= {1, 2}
   {1} == {1, 2}                  False
   not (p ^ q)                     True      also right: no member on one side only
   Equality of sets is extensionality run as code: same members, equal.
   Iteration order depends on how the set was built, so comparing lists
   of two equal sets can say False; a one-sided difference checks only <=.

7. FROZENSET: THE SET THAT CANNOT CHANGE, SO IT CAN BE A MEMBER
   fs.add(3)          -> AttributeError
   fs.union([3, 4])   -> frozenset {1, 2, 3, 4}   a new one; fs is unchanged
   {1} | frozenset({2}) -> set;   frozenset({2}) | {1} -> frozenset   the left operand decides
   frozenset({1, 2}) == {1, 2}  True   equality is still only about members

8. SUBSET, PROPER SUBSET, DISJOINT, EMPTY
   s <= {1, 2}                True
   s < {1, 2}                 False
   s < {1, 2, 3}              True
   set() <= s                 True
   set() < set()              False
   s.isdisjoint({3, 4})       True
   s.isdisjoint({2, 3})       False
   set().isdisjoint(set())    True
   Every set is a subset of itself, but not a proper one. The empty set
   is a subset of every set, and disjoint from every set, itself included.
   if (s <= t, u):   runs, because (s <= t, u) = (True, {5}) is a non-empty tuple
   s <= t and s <= u = False   is what was meant
   the notes' version: s1 = {0, 1, 2, 3, 4}, s2 = {0, 2, 3, 4}, s3 = {0, 2, 5}
     if (s1 <= s2, s3):          always taken, tuple (False, {0, 2, 5})
     s1 <= s2 and s1 <= s3       False   1 is in s1 and in neither of the others
     s2 < = s1                   SyntaxError   <= is one token, no space inside

9. REMOVING: WHICH ONES RAISE
   s.remove(9)      -> KeyError
   s.discard(9)     -> None
   set().pop()      -> KeyError
   remove() insists the member is there; discard() does not care.
   pop() takes an arbitrary member: a set has no 'first' to take.

10. ORDER IS NOT PART OF A SET
   list(set([1, 2, 1, 3, 2, 4, 5])) = [1, 2, 3, 4, 5]   looks sorted, by luck:
   list(set([10, 3, 8]))      = [8, 10, 3]   small ints land in slot n % table size
   words              = ['pear', 'fig', 'apple', 'fig', 'pear', 'kiwi']
   sorted(set(words)) = ['apple', 'fig', 'kiwi', 'pear']   a list: sets cannot be sorted
   list(dict.fromkeys(words)) = ['pear', 'fig', 'apple', 'kiwi']
   To drop duplicates AND keep first-seen order, use a dict: its keys
   are a set that remembers insertion order. list(set(words)) comes back
   in hash order, which for strings changes from one run to the next.
   sorted({3, 1, 'apple', ...})  -> TypeError: Python 3 will not order an int against a str
   key=lambda x: (isinstance(x, str), x)  -> [1, 3, 5, 'apple', 'banana', 'orange']
   numbers first, since False < True, and no int is compared with a str.

11. WHAT SETS ARE FOR: MEMBERSHIP, DEDUPLICATION, VISITED NODES
   graph with cycles A->C->A and B->D->B:  {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'A'], 'D': ['B', 'E'], 'E': []}
   breadth-first from A, skipping nodes already in 'visited': A -> B -> C -> D -> E
   Without the set the walk loops forever. With a list, each 'in' test
   scans the list; with a set it is one hash lookup, whatever the size.
   customers = {'C001', 'C002', 'C003', 'C004'}   invoiced = {'C001', 'C002', 'C004', 'C009'}
   inner join keys     customers & invoiced = {'C001', 'C002', 'C004'}
   outer join keys     customers | invoiced = {'C001', 'C002', 'C003', 'C004', 'C009'}
   left anti-join      customers - invoiced = {'C003'}   never invoiced
   orphans             invoiced - customers = {'C009'}   no such customer
   mismatches          customers ^ invoiced = {'C003', 'C009'}
   The keys a join keeps are a set operation on the two key columns;
   pandas' merge(how='inner'/'outer'/'left') is the same algebra with rows attached.

12. DICT VIEWS: A DICT'S KEYS ARE ALREADY A SET
   stock = {'apple': 3, 'fig': 0, 'kiwi': 5}
   order = {'fig': 2, 'kiwi': 1, 'plum': 4}
   stock.keys() & order.keys() = {'fig', 'kiwi'}   type: set
   order.keys() - stock.keys() = {'plum'}   ordered but never stocked
   stock.keys() | ['pear']      = {'apple', 'fig', 'kiwi', 'pear'}   a keys view takes any iterable
   stock.keys() <= set(stock)   = True
   stock.items() & {'fig': 0, 'kiwi': 9}.items() = {'fig': 0}   same key AND same value
   stock.values() & {0}        -> TypeError
   values can repeat and need not be hashable, so their view is not a set.
   {1, 2}.update({1: 'a', 5: 'e'}) -> {1, 2, 5}   iterating a dict yields its keys
   set({'x': 1, 'y': 2}) = {'x', 'y'}

13. A MULTISET IS A Counter, AND ITS SYMMETRIC DIFFERENCE COUNTS COPIES
   l1 = ['a', 'a', 'b', 'c', 'd']   l2 = ['a', 'b', 'c', 'f']
   set(l1) ^ set(l2)                   = {'d', 'f'}   copies dropped first, so 'a' is in both
   c1 - c2 = {'a': 1, 'd': 1}   c2 - c1 = {'f': 1}
   sorted((c1 - c2 | c2 - c1).elements()) = ['a', 'd', 'f']
   l1 has two 'a' and l2 one, so one 'a' is left over: the multiset
   difference counts copies. '-' binds tighter than '|', so the line
   is (c1 - c2) | (c2 - c1), and | on Counters keeps the larger count.
   c1 ^ c2  -> TypeError   Counter has no ^; build it from two differences

What the run shows

Creating a set (section 1)

There are four ways, and they differ in one respect: what counts as one member.

Code Result Why
{'a', 'b', 'c'} {'a', 'b', 'c'} braces: each thing written is one member
set(['a', 'b', 'c']) {'a', 'b', 'c'} set() takes one iterable and adds each item it yields
set('abc') {'a', 'b', 'c'} a string is an iterable of characters
set('a', 'b', 'c') TypeError set() takes at most one argument
{('a', 'b', 'c')} {('a', 'b', 'c')} one member, a tuple
{'foo'} vs set('foo') {'foo'} vs {'f', 'o'} whole string vs its characters, deduplicated
{2*x for x in [1, 2, 3]} {2, 4, 6} a comprehension: the rule and the source together
s = set(); s.add(...) grows one member at a time add takes exactly one member

The quiz from the notes, "which of these define {'a', 'b', 'c'}?", has three right answers: set('abc'), set(['a', 'b', 'c']) and {'a', 'b', 'c'}. The two traps are set('a', 'b', 'c'), which passes three arguments where one iterable is wanted, and {('a', 'b', 'c')}, which is a set with one member.

A comprehension is also where Russell ↗ meets Python. {x for x in source if rule(x)} always draws from an existing source, which is exactly Zermelo's axiom of separation; Python has no syntax for "every x such that…" with no source, so it cannot state the paradox.

Adding: one member or many (section 2)

s1.add(s2) does not merge two sets. It tries to put s2 in as a single member and fails, because a set is unhashable. The fixes depend on what was meant:

  • merge the members: s1.update(s2), s1 |= s2, or a new set s1 | s2;
  • store the set as one member: s1.add(frozenset(s2)).

The same error with a list, s.add([1, 2, 1]), has the same cure: freeze it first, s.add(tuple([1, 2, 1])), which gives {(1, 2, 1)}. A frozenset has the opposite problem: it has no add at all (AttributeError), so "adding" to one means building a new one, fs.union([3, 4]) or fs | {3, 4}. Wrapping the original in another frozenset(...) first, as one of the notes does, is harmless and unnecessary.

There is no + for sets. [2, 3] + [3, 4] concatenates lists and keeps both 3s; for sets the operation is |, and it keeps one.

Operators and methods (section 3)

Operation Operator In place Method Maths
union a \| b a \|= b a.union(b, ...) / a.update(b, ...) A ∪ B
intersection a & b a &= b a.intersection(b, ...) A ∩ B
difference a - b a -= b a.difference(b, ...) A ∖ B
symmetric difference a ^ b a ^= b a.symmetric_difference(b), one argument only A △ B
subset a <= b a.issubset(b) A ⊆ B
proper subset a < b none A ⊂ B
superset a >= b a.issuperset(b) A ⊇ B
proper superset a > b none A ⊃ B
disjoint none a.isdisjoint(b) A ∩ B = ∅
membership x in a a.__contains__(x) x ∈ A
equality a == b none A = B

B >= A reads "B is a superset of A", B jest nadzbiorem A. For two sets, every row with both forms returns the same answer; the program asserts it. Where they differ is the right-hand side. a | (3, 4, 5) raises TypeError: unsupported operand type(s) for |: 'set' and 'tuple', and a.union((3, 4, 5)) converts the tuple and works. X = {1, 3, 5}; X & [1, 5, 9] fails, and X.intersection([1, 5, 9]) returns {1, 5}. The methods also take several iterables at once, a.union([9], 'x', range(2)), except symmetric_difference, which takes exactly one.

Why the difference? An operator is a symbol between two values, written infix like a + b, and Python makes it strict so that set | list does not quietly decide what type the answer should be. A method is a named call on one set, and its name already says the answer is a set, so it can afford to accept any iterable. (Infix, prefix and postfix are the three places an operator can stand: a | b, | a b, a b |. A method call, union(a, b), is the prefix form with brackets.)

The engineers-and-managers example from the notes turns each operator into a question in plain words, and ends with an identity worth remembering: either, minus exactly one, is both, (E ∪ M) ∖ (E △ M) = E ∩ M.

Claims from the notes, checked (section 4)

The notes this page merges include some statements that are wrong. The program runs each one:

Claim Verdict
you can use in, but not .__contains__() false: in calls __contains__
- has no corresponding method false: .difference(), and .difference_update() for -=
issubset / issuperset have no operator ("N/A") false: <= and >=, plus < and > for proper
isdisjoint has no operator true; not (a & b) is the nearest, and builds a set first
+ is not supported for sets true; use \|
s1.add(s2) fails; use update true
an empty set is falsy true
issubset of an empty iterable returns False false: set().issubset([]) is True
set2 < = set1 tests for a subset false: with the space it is a SyntaxError; <= is one token
{0,1,2,3,4} & {0,2,3,4} & {0,2,5} is {2} false: it is {0, 2}
symmetric_difference takes several sets, like union false: exactly one; chain ^ instead
there is no direct way to compare two sets for equality false: == (section 6)

Chaining: what ^ of three sets means (section 5)

The symmetric difference of two sets is "in exactly one of them". Chained over three, s1 ^ s2 ^ s3 is evaluated left to right as (s1 ^ s2) ^ s3, and it is not "in exactly one of the three". It is "in an odd number of them". With s1 = {0, 1, 2, 3, 4}, s2 = {2, 3, 4} and s3 = {2, 5}, the element 2 is in all three sets and survives, while 3 and 4 are in two and vanish. The trainer's explanation in the notes, (s1 ^ s2) ^ s3 = {0, 1} ^ {2, 5}, is correct; the counting rule says why it has to come out that way. {1} ^ {1} ^ {1} is {1}.

Union, intersection and symmetric difference are associative, so the brackets never matter for them. Difference is not: s1 - s2 - s3 means (s1 - s2) - s3, and s1 - (s2 - s3) is a different set. That is the "left to right" in the notes' summary, and it only matters for -.

Between different operators the brackets matter more, and Python's order is C's, tightest first: -, then &, then ^, then |, with <=, == and in after all four. So a - b & c is (a - b) & c, a | b & c is a | (b & c), and a - b <= c is (a - b) <= c, where C would compare first. The & before | rung is the convention mathematics borrowed from logic, ∩ before ∪, but no textbook gives ∖ or △ a place at all, so bracket them in anything a reader will check by hand. The math library's Reading a set expression ↗ asks Python's parser how it brackets each form and compares Lean and Isabelle, and its set katas ↗ try four katas on the ladder under every bracketing; lines 12 to 15 of the kata below are those four, repaired, because two of them as first written passed under the readings they claimed to rule out.

Equality and frozenset (sections 6 and 7)

a == b is extensionality run as code: same members, equal, whatever order they were added in. The alternatives in the notes each test something else. list(a) == list(b) compares iteration orders, and the program shows two equal sets, {1, 9} and {9, 1}, whose lists differ. a.difference(b) == set() checks only that a ⊆ b, so it says {1} "equals" {1, 2}. not (a ^ b) is correct, and == is simpler.

A frozenset is a set that cannot change after it is made, so it is hashable and can be a member of a set or a key of a dict. Its own page, A frozenset can be a member, has the rest, including why {1, 2} in set_of_frozensets works when a dict lookup does not. It has no add; "adding" builds a new one, fs.union([3, 4]). When a set and a frozenset are combined, the left operand decides the type of the result, and frozenset({1, 2}) == {1, 2} is True, because equality still looks only at members.

Subsets, removal, order (sections 8 to 10)

Every set is a subset of itself but not a proper subset; that is the whole difference between <= (⊆) and < (⊂). The empty set is a subset of every set and disjoint from every set, itself included. One mistake from the notes is worth its own line: if (s1 <= s2, s3): builds a tuple, and a non-empty tuple is always true, so the test always passes. Write s1 <= s2 and s1 <= s3. For the notes' sets, s1 = {0, 1, 2, 3, 4}, s2 = {0, 2, 3, 4} and s3 = {0, 2, 5}, the corrected test is False: 1 is in s1 and in neither of the others. The operator is written <= with no space; < = is a syntax error.

remove(x) raises KeyError when x is absent and discard(x) does not; pop() removes an arbitrary member and raises on an empty set; clear() empties it.

list(set(L)) removes duplicates and may reorder. With small integers the result often looks sorted, [1, 2, 3, 4, 5], only because an integer's hash is itself, so it lands in slot n modulo the table size; list(set([10, 3, 8])) is [8, 10, 3]. With strings the order changes from one run of Python to the next. To remove duplicates and keep the first-seen order, use list(dict.fromkeys(L)). Which copy survives, and why a dict comprehension keeps the wrong one, is Which duplicate survives. A set cannot be sorted, but sorted(s) returns a sorted list, and a set of mixed ints and strings needs a key such as (isinstance(x, str), x), because Python 3 will not compare an int with a str.

What sets are for (section 11)

Three uses cover most real code:

  • Membership tests. Is this word a stop word, has this ID been seen: one hash lookup each.
  • Removing duplicates, with the ordering caveat above.
  • Remembering where you have been. A walk through a graph with cycles keeps a visited set and never steps into a node twice. Without it the walk loops forever; with a list instead of a set it works, but each check scans the list.

And the set algebra itself on real data. The keys a database join keeps are a set operation on the two key columns: an inner join keeps customers & invoiced, an outer join customers | invoiced, a left anti-join customers - invoiced, the customers never invoiced. Pandas' merge(how='inner' | 'outer' | 'left') is the same algebra with the rows attached.

Dict views are sets too (section 12)

A dict's keys are unique and hashable, so they already form a set, and d.keys() returns a view that supports the set operators directly: stock.keys() & order.keys() is the items both dicts mention, and order.keys() - stock.keys() the ones ordered but never stocked. Unlike a set, a keys view accepts any iterable on the other side of the operator. d.items() works the same way when the values are hashable, and matches only pairs with the same key and the same value. d.values() is not set-like at all: values can repeat and need not be hashable. The same fact explains a line in the notes: s.update({1: 'a', 5: 'e'}) adds only 1 and 5, because iterating a dict yields its keys, and set(d) is the set of keys.

A multiset is a Counter (section 13)

A set forgets how many times something occurred; collections.Counter remembers, and its operators are the multiset versions. That explains an answer that looks wrong on StackOverflow. With l1 = ['a', 'a', 'b', 'c', 'd'] and l2 = ['a', 'b', 'c', 'f'], set(l1) ^ set(l2) is {'d', 'f'}, but (c1 - c2 | c2 - c1).elements() gives ['a', 'd', 'f']. The extra 'a' is right for a multiset: l1 has two copies and l2 one, so one copy is left over, while the set version dropped the copies before comparing. The line parses as (c1 - c2) | (c2 - c1), because - binds tighter than |, and | on Counters keeps the larger count of each element. Counter has no ^, which is why the answer builds the symmetric difference from two differences.

The Rust view

Rust's HashSet is the same hash table with the rules enforced at compile time. The element type must implement Eq + Hash, so HashSet<f64> does not compile at all, where Python quietly lets 1, 1.0 and True collapse into one member. insert returns a bool, false for a duplicate, so the silent repeat of section 2 becomes a value you can check. The operators exist on references, &a | &b, &a & &b, &a - &b and &a ^ &b, and the methods union, intersection, difference and symmetric_difference return lazy iterators instead of new sets. Iteration order is randomised per process, like Python's for strings, and BTreeSet is the ordered alternative. See the Rust library's set operations ↗.

If you are coming from ABAP

ABAP has no set type. A set is an internal table with a unique key, SORTED or HASHED, and each operation is an idiom: line_exists( ) for membership, INSERT ... INTO TABLE for adding (a duplicate sets sy-subrc = 4 rather than raising, which is the nearest thing to Python's silent repeat), FILTER ... IN for intersection, FILTER ... EXCEPT IN for difference, and SELECT ... UNION / INTERSECT / EXCEPT on the database. Comparing two internal tables with = compares them line by line in order, so it is not set equality. The ABAP library's sets in ABAP ↗ has the details. (Not machine-checked — CI cannot run ABAP.)

Try it

  1. Take a script of yours that removes duplicates with list(set(...)), run it twice with different PYTHONHASHSEED values on a list of strings, and see whether the order it produces changes. If anything downstream depends on that order, replace it with list(dict.fromkeys(...)) or sorted(set(...)).
  2. Find a place in your code that tests membership in a list inside a loop (if x in some_list:), and time it against the same test on set(some_list) for your real data size.
  3. Take two dicts you already compare field by field and rewrite the comparison with d1.keys() & d2.keys(), d1.keys() - d2.keys() and d1.items() ^ d2.items().
  4. Search your code for .union(, .intersection( and .difference( called with a list or tuple, and for | or & between a set and something else. The first kind works; decide whether the second kind is a bug waiting for the day the argument is not a set.

Practice

Fifteen lines, the notes that got three of them wrong, and two katas that had tested nothing. Write down what each prints before running any of them. s1 = {'a', 'b', 'c'} and s2 = {'c', 'd', 'e'}. Lines 12 to 15 are four katas on the order of -, &, ^ and |, as repaired by the math library's set katas ↗; write the steps, not only the set.

  1. s1 | s2
  2. s1.intersection(s2)
  3. s1 ^ s2
  4. len({True, 1, 1.0, '1'})
  5. set((1, 2, 3)) & set((2, 3, 4)) & set((3, 4, 5))
  6. {1, 2, 3} ^ {3, 4, 5} ^ {5, 6, 7} ^ {7, 8, 1}
  7. {1} ^ {1} ^ {1}
  8. s1 | ['z']
  9. s1.union(['z'])
  10. set().issubset([])
  11. type({})
  12. {1, 2, 3} | {3, 4, 5} & {5, 6, 7}
  13. {1, 2, 3, 4} - {3, 4, 5} & {4, 5, 6}
  14. {1, 2} | {2, 3} ^ {1, 2} & {2, 4}
  15. {1, 2} | {2, 3} ^ {1, 3} - {3, 4} & {1, 4}

Then: say why line 7 is not the empty set, and what line 6 would be if chained ^ meant "in exactly one of the sets". For line 15, say which operator Python applies first and the order of the other three. For line 14, say why a reader who had ^ and & the wrong way round would still have got it right if the last set were {3, 4} instead of {2, 4}.

Answers

Verified output of a_set_is_a_hash_table_kata_py.py — regenerated by tools/run_examples.py, never hand-typed.

 1. s1 | s2                                            {'a', 'b', 'c', 'd', 'e'}
 2. s1.intersection(s2)                                {'c'}
 3. s1 ^ s2                                            {'a', 'b', 'd', 'e'}
 4. len({True, 1, 1.0, '1'})                           2
 5. set((1, 2, 3)) & set((2, 3, 4)) & set((3, 4, 5))   {3}
 6. {1, 2, 3} ^ {3, 4, 5} ^ {5, 6, 7} ^ {7, 8, 1}      {2, 4, 6, 8}
 7. {1} ^ {1} ^ {1}                                    {1}
 8. s1 | ['z']                                         TypeError
 9. s1.union(['z'])                                    {'a', 'b', 'c', 'z'}
10. set().issubset([])                                 True
11. type({})                                           <class 'dict'>
12. {1, 2, 3} | {3, 4, 5} & {5, 6, 7}                  {1, 2, 3, 5}
13. {1, 2, 3, 4} - {3, 4, 5} & {4, 5, 6}               set()
14. {1, 2} | {2, 3} ^ {1, 2} & {2, 4}                  {1, 2, 3}
15. {1, 2} | {2, 3} ^ {1, 3} - {3, 4} & {1, 4}         {1, 2, 3}

Lines 14 and 15 under every bracketing; Python's is marked.
Line 14 as A | B ^ A & C with A = {1, 2}, B = {2, 3}, C = {2, 4}:
   (A | (B ^ (A & C)))      {1, 2, 3}     Python: & first, then ^, then |
   (A | ((B ^ A) & C))      {1, 2}
   ((A | B) ^ (A & C))      {1, 3}
   ((A | (B ^ A)) & C)      {2}
   (((A | B) ^ A) & C)      set()
   1 of 5 bracketings gives {1, 2, 3}; with C = {3, 4}, 3 of 5 do, because
   A & C is then set() and B ^ set() is B: the ^ step does nothing.
Line 15 as A | B ^ C - D & E with A = {1, 2}, B = {2, 3}, C = {1, 3}, D = {3, 4}, E = {1, 4}:
   Python reads (A | (B ^ ((C - D) & E))) = {1, 2, 3}: - first, then &, then ^, then |
   1 of 14 bracketings gives {1, 2, 3}; as first written, A | B ^ C - A & D with
   C = {3, 4} and D = {2, 4}, 2 of 14 did: (C - A) & D is disjoint from A, and then
   (A | B) ^ X == A | (B ^ X), so ^ against | could never show.

Line 7 is {1} because ^ keeps what is in an odd number of the sets, and 1 is in three. Line 6 happens to agree with "exactly one" only because every shared element there is in exactly two sets.

Lines 12 to 15 are Python's ladder, tightest first -, &, ^, |, which is C's. An answer that matches is not yet a test of the order: line 14 with {3, 4} at the end has an empty & step, so three readings of five give the same set, and the kata as first written, A | B ^ C - A & D, could not separate ^ from | for any choice of sets, because (C - A) & D is disjoint from A. The second part of the answer counts the bracketings that agree, which is the check that an assert on the final set skips.

See also