Sets
A set is an unordered collection of distinct elements with no duplicates. In mathematics, set theory (Zermelo–Fraenkel axioms) provides the foundation for most of modern mathematics; in computing, sets appear as both a concrete data structure and a conceptual tool for reasoning about membership, relationships, and uniqueness constraints. The key property is that each value either belongs to the set or does not — there is no notion of multiplicity (for that, see multisets/bags). Most language standard libraries implement sets using hash tables (for O(1) average membership tests) or balanced BSTs (for O(log n) membership with sorted iteration).
Key Concepts
Set Operations
| Operation | Symbol | Meaning |
|---|---|---|
| Union | A ∪ B | All elements in A or B |
| Intersection | A ∩ B | Elements in both A and B |
| Difference | A − B | Elements in A but not B |
| Symmetric difference | A △ B | Elements in exactly one of A or B |
| Subset | A ⊆ B | Every element of A is in B |
| Superset | A ⊇ B | Every element of B is in A |
Hash Set vs. Tree Set — Hash-based sets (Python set, Java HashSet, Go map[T]struct{}) provide O(1) average-case membership, add, and remove, but iteration order is undefined and keys must be hashable. Tree-based sets (Java TreeSet, C++ std::set) store elements in sorted order using a self-balancing BST, giving O(log n) operations and ordered iteration. Choose based on whether sorted traversal is needed.
Membership Testing — The primary advantage of a set over a list is membership testing. Checking x in list is O(n); checking x in set is O(1) on average. This distinction is critical in algorithms that perform many membership queries — deduplication, visited-node tracking in graph traversal, and filtering.
Set as a Filter for Uniqueness — Converting a collection to a set then back is the idiomatic way to deduplicate. This works only when element order is unimportant and elements are hashable/comparable. For order-preserving deduplication, an ordered dict or insertion-ordered set is needed.
Bloom Filters — A probabilistic data structure that represents a set using a bit array and multiple hash functions. A Bloom filter can definitively say an element is not in the set, but may produce false positives (reporting membership when the element is absent). Space usage is far smaller than a full set, making Bloom filters valuable for cache pre-screening, duplicate URL detection in crawlers, and database query optimization.
Bit Sets — When the universe of possible elements is small and known in advance (e.g., integers 0–63), a set can be represented as a bitmask, with union as bitwise OR, intersection as bitwise AND, and difference as A & ~B. Bit set operations execute in O(1) on fixed-width integers and are O(n/64) for arbitrary-length bitsets, making them extremely cache-friendly.
Set Theory in Database Design — SQL UNION, INTERSECT, and EXCEPT are set operations applied to query result tables. A foreign key relationship encodes a subset constraint: the set of values in the referencing column must be a subset of primary key values in the referenced table.
Common Pitfalls
- Mutating an element that is stored in a hash set invalidates its hash, making it unreachable
- Assuming set iteration order in languages that do not guarantee it
- Using a list when O(n) membership checks are performed in a hot loop — the fix is almost always a set conversion
Best Practices
- Use
frozenset(Python) or equivalent immutable set types as dictionary keys or set elements when nesting sets - Pre-size sets when the approximate cardinality is known to reduce rehashing
- For integer sets over a bounded domain, consider bitset representations for cache efficiency