Sets and Multisets

A hash table maps a key to a value. In some problems there is no value; the only question asked is “does this element exist”. Filtering out duplicates, testing whether an identifier is in a list, finding the common elements of two collections all belong to this class.

A set is an abstract data type focused on membership: every element either exists or does not, its count is not kept, and its order is not defined.

Set Operations

Operation	Meaning
add	Adds the element to the set; no change if it is already there
remove	Removes the element
contains	Membership test
union	All elements of both sets
intersection	Elements found in both
difference	Elements in the first but not the second
is_subset	Containment test

The first three work on a single element, the last four on a pair of sets. Their costs are considered differently: single-element operations can be independent of the element count, while set operations must traverse at least one set.

Implementation Options

A hash set is a hash table without a value. Single-element operations are average constant time; order is not preserved.

A sorted set is built on a structure that keeps elements in order (a balanced tree or a skip list). Single-element operations are logarithmic; in exchange, elements can be traversed in order and range queries can be done — such as “elements with a value between 10 and 20”.

The selection criterion is clear: a hash set if order or range is not needed, a sorted set if it is.

The Bitset

If the elements are integers between $0$ and $N-1$, and $N$ is of reasonable size, there is a third, much more efficient implementation: a single bit for every element.

A bitset keeps membership at the bit level. The bit-level operations from the How Computers Work course are used directly here.

class BitSet:
    """Holds integers in the range 0..N-1 at the bit level."""

    def __init__(self, universe: int) -> None:
        self.universe = universe
        self._bits = 0                          # a single large integer

    def add(self, value: int) -> None:
        self._bits |= 1 << value                # set the relevant bit

    def remove(self, value: int) -> None:
        self._bits &= ~(1 << value)             # clear the relevant bit

    def contains(self, value: int) -> bool:
        return ((self._bits >> value) & 1) == 1

    def union(self, other: "BitSet") -> "BitSet":
        result = BitSet(self.universe)
        result._bits = self._bits | other._bits
        return result

    def intersection(self, other: "BitSet") -> "BitSet":
        result = BitSet(self.universe)
        result._bits = self._bits & other._bits
        return result

    def elements(self) -> list[int]:
        return [i for i in range(self.universe) if self.contains(i)]

    def __len__(self) -> int:
        return bin(self._bits).count("1")       # number of set bits


a = BitSet(16)
b = BitSet(16)
for d in (1, 3, 5, 7):
    a.add(d)
for d in (3, 5, 9):
    b.add(d)

print(a.elements(), b.elements())              # [1, 3, 5, 7] [3, 5, 9]
print(a.intersection(b).elements())            # [3, 5]
print(a.union(b).elements())                   # [1, 3, 5, 7, 9]
print(len(a), a.contains(7), a.contains(8))    # 4 True False

It has two advantages, and both are significant.

Memory. One bit is used per element. A universe of a million elements fits into 125 kilobytes; holding the same set with a hash set requires tens of bytes per element.

Set operations are parallel at the word level. The intersection of two bitsets is a single AND operation; the processor handles 64 elements in one instruction. In a hash set, the same operation requires visiting elements one by one.

Its condition, however, is narrow: the universe must be small and dense. If the elements are a few values scattered among billions, a bitset turns into wasted memory. In that case, sparse representations or a hash set are preferred.

Bitsets are widely used to combine row sets in database indexes, to mark visited nodes in graph algorithms, and to hold permission sets.

The Multiset

A set reports whether an element exists; it does not report how many times. When a count is needed, a multiset is used: a counter is kept alongside every element.

def frequency(measurements: list[int]) -> dict[int, int]:
    """Counts how many times each value occurs."""
    counts: dict[int, int] = {}
    for measurement in measurements:
        counts[measurement] = counts.get(measurement, 0) + 1
    return counts


measurements = [12, 18, 7, 12, 25, 12, 18]
print(frequency(measurements))                 # {12: 3, 18: 2, 7: 1, 25: 1}
print(max(frequency(measurements).items(), key=lambda c: c[1]))   # (12, 3)

A multiset is really a mapping whose value is a count; the reason it is called a separate structure is that set operations are defined through the counters: union takes the larger count, intersection the smaller.

Its typical use is counting problems: word frequencies, the most frequent values, sample distributions. The frequency analyses in the data analytics curriculum are built on this structure.

Set or List

A common performance mistake is doing a membership test on a list. Search in a list is linear; the same test on a set is average constant.

ids = list(range(100_000))
ids_set = set(ids)

# Membership on a list: every query can scan the whole list.
print(99_999 in ids)            # True — 100,000 comparisons in the worst case
# Membership on a set: a single step via hashing.
print(99_999 in ids_set)        # True — a bucket computation and a few comparisons

The difference is multiplied by the number of tests: performing $m$ queries on a list is $O(n \cdot m)$, on a set $O(m)$. A membership test performed inside a loop is therefore a standard review point.

Converting to a set also has a cost — adding every element is $O(n)$. Converting for a single query is pointless; as the number of queries grows, the conversion pays for itself.

The Cost of Set Operations

When computing the intersection of two sets, traversing the smaller set and testing membership in the larger one is cheaper than doing it the other way around:

$$O(\min(\lvert A\rvert, \lvert B\rvert)) \quad \text{instead of} \quad O(\lvert A\rvert)$$

This detail makes a noticeable difference when working with large data sets, and most library implementations do it automatically.

Sorted sets, however, offer a different route: advancing in a single pass, as if merging two sorted arrays, gives every set operation at a cost of $O(\lvert A\rvert + \lvert B\rvert)$ and requires no extra memory.

Cost Table

Structure	Membership	Insertion	Intersection	Order
Hash set	$O(1)$ average	$O(1)$ average	$O(\min(\lvert A\rvert, \lvert B\rvert))$	No
Sorted set	$O(\log n)$	$O(\log n)$	$O(\lvert A\rvert + \lvert B\rvert)$	Yes
Bitset	$O(1)$	$O(1)$	$O(N / w)$*	By value

* $w$ is the processor’s word width; $N$ the universe size.

Summary

• A set is an abstract type focused on membership; an element either exists or does not, and its count and order are not kept.
• A hash set performs single-element operations in average constant time but does not preserve order; a sorted set provides order and range queries at logarithmic cost.
• A bitset uses a single bit per element in small, dense integer universes and performs set operations in parallel at the word level.
• A multiset keeps a counter alongside each element; it is the natural structure for counting problems.
• When intersecting two sets, traversing the smaller one brings the cost down to its size.

Next Step

Up to this point, sets have been treated independently. In some problems, the question asked is different: “are these two elements in the same group?” and groups merge over time. The next lesson covers the disjoint-set structure that answers this question in nearly constant time.