Sets and multisets

What this chapter covers

The last two chapters built a hash table and studied its hash function. This one puts them to work on the two questions programmers ask more than any other: "have I seen this before?" and "how many of each?" A set is a hash table that stores only keys, so membership is O(1) and duplicates are impossible. A multiset keeps a count beside each key, so it answers how many times. On top of O(1) membership, sets carry an algebra — union, intersection, difference — that turns whole-collection questions into one-liners. This chapter builds both and shows the single most useful pattern in the book: the "seen" set that collapses an O(n²) loop to O(n).

A bit of history

The set is the oldest idea in this book by far — it predates computing by decades. Georg Cantor founded set theory in the 1870s, and its operations, union and intersection and difference, are the ones this chapter implements unchanged. When programming languages wanted a data structure for collections without order or repetition, they took Cantor's sets almost literally: the SETL language in the 1970s, designed by Jack Schwartz, made sets a first-class type and showed you could write remarkably compact programs by thinking in set operations. Python inherited that lineage — its set and set comprehensions are SETL's descendants — and the multiset, the "bag" that allows repetition with a count, comes from combinatorics, formalized in the same tradition. So the algebra is 150 years old; only the O(1) hash-table implementation underneath is modern.

The intuition

A set is a bag you can only ask one question of: is this thing in you? Because it's backed by a hash table, the answer is O(1) — you hash the element and check its bucket, no scanning. Adding an element that's already present does nothing, which is what makes a set deduplicate for free: pour a list into a set and duplicates collapse.

The algebra falls straight out of O(1) membership. Union is "everything in either" — add both sides into one set. Intersection is "things in both" — walk the smaller set and keep the elements the larger one also contains, each check O(1). Difference is "in me but not you." All three are cheap because the underlying "is X in this set?" is cheap. A multiset relaxes the no-duplicates rule by storing a count instead of just presence, which turns it into the natural tool for tallying — word frequencies, vote counts, inventory.

Complexity: how it scales

Membership, add, and remove inherit the hash table's average $O(1)$ — hash the element, touch one bucket. The set operations build on that: union is $O(n + m)$ because it adds every element of both sets; difference is $O(n)$, one membership check per element of the left side; and intersection is $O(\min(n, m))$ if you're careful to iterate the smaller set and probe the larger, since each probe is O(1). That "iterate the smaller" detail matters — get it backwards and you do more work for the same answer. Space is $O(n)$.

The chart builds a set, runs a batch of membership queries, and intersects it with another — the everyday set workload — timed against Python's set:

Both lines are straight — linear total work, O(1) per operation — which is the whole reason sets are fast.

What it's good at, what it isn't

A set is the right tool the instant your question is about membership or uniqueness. Deduplicating, testing "is this in the allowed list," finding what two collections share, tracking what you've already visited — all become O(1)-per-element instead of O(n). The multiset extends that to counting, which is its own everyday superpower. These are among the most-reached-for structures in real code, precisely because so many problems reduce to "seen it?" or "how many?"

What a set gives up is everything about order and position. It has no first or last, no index, no sorted iteration, and it silently discards duplicates — so if any of those matter, a set is the wrong tool and you want a list or a sorted structure. And like all hashing, its O(1) is an average that rests on a decent hash and bounded load.

The data, or the inputs

The face-off builds sets of distinct integers, fires a batch of membership queries (half hits, half misses), and intersects two overlapping sets — exercising exactly the operations the chapter is about. The animation uses two tiny six-element sets with a three-element overlap so you can watch an intersection get computed one membership probe at a time.

Build it, one function at a time

Adding an element puts it in its bucket, but only if it's not already there — a set holds each element once:

def add(self, key):
    """O(1) average: put the key in its bucket, unless it's already there —
    a set holds each element at most once. Grow to keep buckets short."""
    bucket = self._buckets[self._index(key)]
    if key in bucket:
        return
    bucket.append(key)
    self._n += 1
    if self._n > 0.75 * self._cap:
        self._resize(self._cap * 2)

Membership is the operation everything else is built on — a single O(1) bucket check:

def contains(self, key):
    """O(1) average: membership is a scan of just the key's bucket."""
    return key in self._buckets[self._index(key)]

def __contains__(self, key):
    return self.contains(key)

The algebra then reads almost like its mathematical definition. Union adds both sides; intersection walks the smaller set and keeps what the larger also has; difference keeps what the other lacks:

def union(self, other):
    """O(n + m): every element in either set."""
    result = HashSet(self)
    for x in other:
        result.add(x)
    return result

def intersection(self, other):
    """O(min(n, m)): elements in both. Iterate the SMALLER set and probe the
    larger — each probe is O(1), so the total is bounded by the smaller size."""
    small, large = (self, other) if len(self) <= len(other) else (other, self)
    result = HashSet()
    for x in small:
        if x in large:
            result.add(x)
    return result

def difference(self, other):
    """O(n): elements in self but not in other."""
    result = HashSet()
    for x in self:
        if x not in other:
            result.add(x)
    return result

And the multiset swaps "present or not" for a count, which is all it takes to turn a set into a tally:

class Multiset:
    """A set that keeps counts — how many of each element. It's a hash table from
    element to count, so add/count/remove are all O(1) average."""

    def __init__(self, iterable=None):
        self._counts = {}
        if iterable is not None:
            for x in iterable:
                self.add(x)

    def add(self, key, n=1):
        self._counts[key] = self._counts.get(key, 0) + n

    def count(self, key):
        return self._counts.get(key, 0)

    def remove(self, key, n=1):
        if key in self._counts:
            self._counts[key] -= n
            if self._counts[key] <= 0:
                del self._counts[key]

    def most_common(self, k=None):
        items = sorted(self._counts.items(), key=lambda kv: -kv[1])
        return items[:k] if k is not None else items

    def __len__(self):
        return sum(self._counts.values())

Watch it work

Here's an intersection computed the way the code does it — one membership probe at a time. The top row is set A, the bottom is set B, and we're computing A ∩ B by checking each element of A for membership in B. Orange is the element being checked; green means it's in both sets (so it joins the intersection); gray means it's only in A. Step through it: 1, 2, and 3 miss, then 4, 5, and 6 hit — each hit an O(1) probe into B, not a scan. The intersection {4, 5, 6} builds up as the green cells light up in both rows:

The complete code

Both versions in one place — flip between them. The from-scratch tab has our HashSet with its algebra and the Multiset. The library tab is what you'd use: set with the |, &, - operators, and collections.Counter for the multiset.

"""Sets and multisets — hash tables that answer the two most common questions in
programming: "have I seen this before?" and "how many of each?"

A set is a hash table that stores only keys, so membership is O(1). A multiset (or
"bag") keeps a count alongside each key, so it also answers how many times. On top
of O(1) membership, sets add an algebra — union, intersection, difference — that
turns whole-collection questions into a few lines.
"""


class HashSet:
    """A set on a chained hash table: keys only, O(1) membership on average."""

    def __init__(self, iterable=None, capacity=8):
        self._cap = capacity
        self._buckets = [[] for _ in range(capacity)]
        self._n = 0
        if iterable is not None:
            for x in iterable:
                self.add(x)

    def _index(self, key):
        return hash(key) % self._cap

    # region: add
    def add(self, key):
        """O(1) average: put the key in its bucket, unless it's already there —
        a set holds each element at most once. Grow to keep buckets short."""
        bucket = self._buckets[self._index(key)]
        if key in bucket:
            return
        bucket.append(key)
        self._n += 1
        if self._n > 0.75 * self._cap:
            self._resize(self._cap * 2)
    # endregion

    # region: contains
    def contains(self, key):
        """O(1) average: membership is a scan of just the key's bucket."""
        return key in self._buckets[self._index(key)]

    def __contains__(self, key):
        return self.contains(key)
    # endregion

    # region: remove
    def remove(self, key):
        """O(1) average: drop the key from its bucket if present."""
        bucket = self._buckets[self._index(key)]
        if key in bucket:
            bucket.remove(key)
            self._n -= 1
            return True
        return False
    # endregion

    def _resize(self, new_cap):
        old = self._buckets
        self._cap = new_cap
        self._buckets = [[] for _ in range(new_cap)]
        self._n = 0
        for bucket in old:
            for k in bucket:
                self.add(k)

    def __len__(self):
        return self._n

    def __iter__(self):
        for bucket in self._buckets:
            yield from bucket

    # region: setops
    def union(self, other):
        """O(n + m): every element in either set."""
        result = HashSet(self)
        for x in other:
            result.add(x)
        return result

    def intersection(self, other):
        """O(min(n, m)): elements in both. Iterate the SMALLER set and probe the
        larger — each probe is O(1), so the total is bounded by the smaller size."""
        small, large = (self, other) if len(self) <= len(other) else (other, self)
        result = HashSet()
        for x in small:
            if x in large:
                result.add(x)
        return result

    def difference(self, other):
        """O(n): elements in self but not in other."""
        result = HashSet()
        for x in self:
            if x not in other:
                result.add(x)
        return result
    # endregion


# region: multiset
class Multiset:
    """A set that keeps counts — how many of each element. It's a hash table from
    element to count, so add/count/remove are all O(1) average."""

    def __init__(self, iterable=None):
        self._counts = {}
        if iterable is not None:
            for x in iterable:
                self.add(x)

    def add(self, key, n=1):
        self._counts[key] = self._counts.get(key, 0) + n

    def count(self, key):
        return self._counts.get(key, 0)

    def remove(self, key, n=1):
        if key in self._counts:
            self._counts[key] -= n
            if self._counts[key] <= 0:
                del self._counts[key]

    def most_common(self, k=None):
        items = sorted(self._counts.items(), key=lambda kv: -kv[1])
        return items[:k] if k is not None else items

    def __len__(self):
        return sum(self._counts.values())
# endregion

"""Python's `set` is the hash set, and `collections.Counter` is the multiset —
both hash tables in C. `set` gives O(1) membership and the same union/intersection/
difference algebra (as the operators |, &, -); `Counter` keeps counts and adds
`most_common`.

So the face-off is our HashSet and Multiset against the built-ins they reimplement.
"""
from collections import Counter


# region: set_ops
def set_union(a, b):
    return set(a) | set(b)


def set_intersection(a, b):
    return set(a) & set(b)


def set_difference(a, b):
    return set(a) - set(b)
# endregion


# region: counter
def multiset_counter(iterable):
    """A Counter is a multiset: element -> count, with most_common built in."""
    return Counter(iterable)
# endregion

Scratch vs library

Same structure, same O(1) operations, so once again the gap is a constant — and a big one, because ours is a Python hash set doing in bytecode what set does in C. Building a 160000-element set, probing it, and intersecting took our HashSet about 580 ms against the built-in set's 35 ms — roughly 17 times slower. That's the now-familiar tax of reimplementing a core container in Python, and it's why you'd always use the built-in. The value of building it is that the set operations stop being magic: when you write a & b, you now know it's walking the smaller set and probing the larger, and you know why intersecting a tiny set with a huge one is cheap while unioning two huge ones isn't.

Where you'll actually meet it

Sets and multisets are everywhere once you look. Every deduplication (list(set(xs))) is a set. Every graph and tree traversal in this book carries a "visited" set to avoid re-processing nodes. Databases use set operations for UNION, INTERSECT, and DISTINCT. Access control checks whether your roles intersect the required roles. Spell-checkers and autocomplete test dictionary membership. And Counter — the multiset — tallies word frequencies, log-line counts, votes, and inventory in a single line. Any time a problem says "unique," "shared," "already seen," or "how many of each," it's a set or multiset.

Takeaways

A set is a hash table storing only keys: O(1) membership, no duplicates, and an algebra of union, intersection, and difference that stays cheap because it's built on that O(1) lookup. A multiset keeps counts instead of mere presence, making it the natural counter. The one pattern to carry everywhere is the seen-set: replacing "scan to check if I've seen this" with an O(1) membership test, which quietly removes a factor of n from more algorithms than any other single trick.

That closes the hashing tier — hash tables, hash functions, and the sets and counts built on them. Hashing buys O(1) at the cost of all order. The next tier changes subject entirely: recursion and sorting, starting with the idea that lets an algorithm call itself, and the call stack from chapter four that makes it work.