beginner

Sets in Python

By DataPlayArena Technical Review BoardUpdated 2026-07-208 min readRuntime Verified

Overview

A set in Python is an unordered, mutable collection of unique, hashable elements. Under the hood, sets are implemented using hash tables (similar to Python dictionaries, but containing only keys without associated values). This architecture provides average-case $O(1)$ time complexity for membership testing, additions, and deletions, making sets an indispensable tool for data deduplication, relational filtering, and mathematical set theory operations in data pipelines.

What You Will Learn

In this lesson, you will master:
  • Set Fundamentals: Unordered nature, element uniqueness, and hashability requirements.
  • Set Operations: Union (|), Intersection (&), Difference (-), and Symmetric Difference (^).
  • Set Theory in Data Pipelines: Deduplication, reconciliation, and delta tracking between data streams.
  • Mutable vs Immutable: Understanding the role of frozenset for hashable nested collections.
  • Performance Optimization: Comparing $O(1)$ set lookups against $O(N)$ list scans in high-throughput applications.

Core Concepts & Mechanics

1. Hash Table Mechanics & $O(1)$ Lookups

When an element is added to a set, Python calls hash(item) to calculate its hash code and maps it to a specific memory bucket.

python
# Membership testing performance
import time

large_list = list(range(1_000_000))
large_set = set(large_list)

# Looking up the last element:
# List scan requires checking 1,000,000 items -> O(N)
# Set lookup computes hash(999_999) -> O(1) instant jump

Because hash tables require unique and immutable keys:

  • Allowed in Sets: Integers, floats, strings, tuples (if containing immutable items), frozenset.
  • Not Allowed in Sets: Lists, dicts, regular sets (TypeError: unhashable type: 'list').

2. Set Creation Syntax

To create an empty set, you must use set(). Using {} creates an empty dictionary:

python
empty_dict = {}       # type is <class 'dict'>
empty_set = set()     # type is <class 'set'>
populated_set = {1, 2, 3, 4}

Mathematical Set Operations

Sets provide operators and methods for comparing two or more collections:

python
group_a = {"user_1", "user_2", "user_3", "user_4"}
group_b = {"user_3", "user_4", "user_5", "user_6"}

# 1. Union: Elements in either group (A ∪ B)
all_users = group_a | group_b
# Same as: group_a.union(group_b)
# Result: {'user_1', 'user_2', 'user_3', 'user_4', 'user_5', 'user_6'}

# 2. Intersection: Elements present in BOTH groups (A ∩ B)
common_users = group_a & group_b
# Same as: group_a.intersection(group_b)
# Result: {'user_3', 'user_4'}

# 3. Difference: Elements in A but NOT in B (A \ B)
only_in_a = group_a - group_b
# Same as: group_a.difference(group_b)
# Result: {'user_1', 'user_2'}

# 4. Symmetric Difference: Elements in EITHER A or B, but NOT both (A △ B)
exclusive_users = group_a ^ group_b
# Same as: group_a.symmetric_difference(group_b)
# Result: {'user_1', 'user_2', 'user_5', 'user_6'}
Operator vs Method Difference

The operators (|, &, -, ^) require both sides to be set objects. The corresponding methods (.union(), .intersection(), etc.) accept any iterable (lists, tuples, generators) as arguments.


Practical Applications in Data Engineering

1. Data Reconciliation (Detecting Added, Removed & Unchanged IDs)

When syncing records between an operational database and a data warehouse:

python
def reconcile_records(source_ids: list[str], target_ids: list[str]):
    source_set = set(source_ids)
    target_set = set(target_ids)
    
    records_to_insert = source_set - target_set   # In source but not yet in target
    records_to_delete = target_set - source_set   # In target but dropped from source
    records_to_update = source_set & target_set   # In both (check for updated timestamps)
    
    return {
        "insert": records_to_insert,
        "delete": records_to_delete,
        "retain": records_to_update
    }

delta = reconcile_records(["A1", "A2", "A3"], ["A2", "A3", "A4"])
print(delta)
# Output: {'insert': {'A1'}, 'delete': {'A4'}, 'retain': {'A2', 'A3'}}

2. Immutable Sets with frozenset

Since regular sets are mutable, you cannot create a set of sets or use sets as dictionary keys. frozenset provides an immutable alternative:

python
# Grouping permissions by roles
role_permissions = {
    frozenset(["read", "view"]): "viewer_role",
    frozenset(["read", "write", "delete"]): "admin_role",
}

user_perms = frozenset(["view", "read"])
print(role_permissions.get(user_perms))  # Output: 'viewer_role'

Common Mistakes & Gotchas

  • Assuming Insertion Order: Unlike Python 3.7+ dictionaries which maintain insertion order, standard sets do not guarantee order. Iterating over a set may yield elements in unpredictable order across runs.
  • Mutating While Iterating: Adding or removing items from a set while iterating through it raises RuntimeError: Set changed size during iteration. Iterate over a copy (for item in list(my_set):) instead.
  • Overusing Sets on Very Small Collections: For tiny collections (1–3 items), iterating a tuple or list can sometimes be faster than computing hash codes and allocating hash table buckets.

Performance & Best Practices

  • Deduplication with Preservation: If you need to deduplicate a sequence while strictly preserving its original order, use dict.fromkeys() instead of list(set(seq)):
    python
    items = ["apple", "banana", "apple", "cherry", "banana"]
    ordered_unique = list(dict.fromkeys(items))
    print(ordered_unique)  # ['apple', 'banana', 'cherry']
    
  • In-place Set Updates: When working with massive sets, use in-place methods (intersection_update, difference_update, update) to mutate the existing set in place and save allocation overhead rather than allocating a new set with operators.

Interview Perspective

Python Interview Question: What is the underlying data structure of a set, and what causes an unhashable type error?

Key Talking Points for Candidates:

  1. Hash Table Architecture: Python sets are implemented as open-addressing hash tables with perturbation-based collision resolution.
  2. Hashability Contract: An object is hashable if it has an invariant hash code throughout its lifecycle (__hash__) and can be compared to other objects (__eq__).
  3. Unhashable Types: Mutable collections like list, dict, and set do not implement __hash__ because their values can change post-insertion, which would invalidate their bucket placement and corrupt the table.

Interactive Practice Challenge

Challenge: Find Orphan Customer IDs

You are given two lists: all_customers (all registered user IDs) and active_orders (user IDs who placed at least one order this month). Write a function that returns the count of inactive customers who have never placed an order this month.

DPA

DataPlayArena Technical Editorial Board

Curated & maintained by enterprise data platform engineers with 10+ years in distributed systems.

Runtime Verification Standards: Every code example, query, and architecture diagram in this tutorial is compiled and verified against real runtimes (Apache Spark 3.5, Python 3.11, PostgreSQL, and DuckDB). If you spot any errata or want to suggest improvements, please submit feedback.