🔧 Advanced Set Implementation — Hash-Based Collections

Sets use hash tables similar to dictionaries, storing only keys with no values attached.

🎯 Set Implementation Internals

Sets store hashed keys in a hash table, providing O(1) average operations.

# Set structure (similar to dict but no values)
s = {1, 2, 3, 4, 5}

# Internal hash table
# Index: 0    1    2    3    4    5    6    7
# Entry: [1][--][2][--][3][--][4][5]

import sys

# Memory usage increases with size
empty_set = set()
print(f"Empty set: {sys.getsizeof(empty_set)} bytes")

small_set = {1, 2, 3}
print(f"3-item set: {sys.getsizeof(small_set)} bytes")

large_set = set(range(1000))
print(f"1000-item set: {sys.getsizeof(large_set)} bytes")

💡 Bitwise Set Operations

Sets support bitwise operators for mathematical operations.

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

# Union (all elements)
union = A | B  # {1, 2, 3, 4, 5, 6}

# Intersection (common elements)
intersection = A & B  # {3, 4}

# Difference (in A but not B)
difference = A - B  # {1, 2}

# Symmetric difference (in A or B but not both)
sym_diff = A ^ B  # {1, 2, 5, 6}

# Subset/superset checks
print(A <= B)  # False: A is not subset of B
print({1, 2} <= A)  # True: {1,2} is subset of A
print(A > {1, 2})  # True: A is superset of {1,2}

# These are faster than equivalent methods
# A & B vs A.intersection(B)
# Both O(min(len(A), len(B))) but operators are more concise

🎨 Advanced Set Patterns

# Finding unique elements
data = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
unique = set(data)  # {1, 2, 3, 4}

# Remove duplicates while preserving order
seen = set()
ordered_unique = [x for x in data if not (x in seen or seen.add(x))]
# [(x not in seen) and (seen.add(x) is None) is always true since add() returns None]

# Better approach: dict keys (preserve order in Python 3.7+)
ordered_unique = list(dict.fromkeys(data))  # [1, 2, 3, 4]

# Set comprehension
squares = {x**2 for x in range(1, 6)}  # {1, 4, 9, 16, 25}
even_squares = {x**2 for x in range(1, 6) if x % 2 == 0}  # {4, 16}

# Multiple operations chained
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}
C = {7, 8, 9, 10}

result = (A | B) - C  # Union then remove C elements
# {1, 2, 3, 4, 5, 6}

📊 Set Performance Characteristics

🔑 Key Takeaways

• ✅ Sets use hash tables for O(1) average operations

• ✅ Bitwise operators provide efficient set mathematics

• ✅ Intersection is fastest on smallest set

• ✅ Set comprehensions create new sets with filtered/transformed elements

• ✅ `discard()` is safer than `remove()` for missing elements

Ready to practice? Challenges | Quiz