---
title: 'Sets and Multisets'
source: 'https://academia.sh/en/courses/data-structures/sets'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:51+00:00'
license: 'CC BY-SA 4.0'
---

# Sets and Multisets

The membership-focused abstract type, hash-based and ordered implementations, bitsets, and counted 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.

```python
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.

```python
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.

```python
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.