Skip to content

Sets or Hashsets

Sets or Hashsets are a collection of unique elements. They are implemented using a hash table, which allows for fast lookups, insertions, and deletions. The time complexity for these operations is O(1) on average.

Hashtables use a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. When a collision occurs (i.e., when two different keys hash to the same index), the hash table uses a method to resolve the collision, such as chaining or open addressing.

Example:

word: "hello"

Hash function: hash("hello") -> 12345

Index: 12345 % 100 = 45

The word "hello" would be stored in the bucket at index 45. If another word, say "world", also hashes to index 45, it would be stored in the same bucket, and the hash table would need to resolve the collision to ensure both words can be accessed efficiently.

index bucket
0
1
...
45 "hello", "world"

Values must be hashable, commonly immutable types like strings, integers, and tuples. Mutable types like lists and dictionaries cannot be used as elements in a set because they cannot be hashed.

1
2
my_set = {1, 2, 3, 4, 5}
my_set, type(my_set)

({1, 2, 3, 4, 5}, set)

Unique elements in a list

1
2
numbers = [1, 2, 3, 3, 4, 5, 5, 6]
set(numbers)

{1, 2, 3, 4, 5, 6}

Adding an element to a set - O(1)

1
2
3
my_set = {1, 2, 3, 4, 5}
my_set.add(6)
my_set

{1, 2, 3, 4, 5, 6}

Removing an element from a set - O(1)

1
2
3
my_set = {1, 2, 3, 4, 5}
my_set.remove(5)  # This will raise an error if 5 is not present
my_set

{1, 2, 3, 4}

Removing an element from a set, while ignoring errors

1
2
3
my_set = {1, 2, 3, 4, 5}
my_set.discard(6)  # This won't raise an error if 6 is not present
my_set

{1, 2, 3, 4, 5}

Removing first stored element from a set

1
2
3
my_set = {1, 2, 3, 4, 5}
print(my_set.pop())  # This will remove the first inserted element FIFO
print(my_set)

1

{2, 3, 4, 5}

Clearing a set

1
2
3
my_set = {1, 2, 3, 4, 5}
my_set.clear()
my_set  # This will print an empty set

set()

Check if an element is in the set - O(1)

1
2
my_set = {1, 2, 3, 4, 5}
3 in my_set

True

Union of two sets

1
2
3
set1 = {1, 2, 3, 4, 5, 6}
set2 = {4, 5, 6, 7, 8, 9}
set1.union(set2)

{1, 2, 3, 4, 5, 6, 7, 8, 9}

Intersection of two sets

1
2
3
4
set1 = {1, 2, 3, 4, 5, 6}
set2 = {4, 5, 6, 7, 8, 9}
intersection_set = set1.intersection(set2)
intersection_set

{4, 5, 6}

Update set1 with the intersection of set1 and set2

1
2
3
4
set1 = {1, 2, 3, 4, 5, 6}
set2 = {4, 5, 6, 7, 8, 9}
set1.intersection_update(set2)
set1

{4, 5, 6}

Difference of two sets

1
2
3
set1 = {1, 2, 3, 4, 5, 6}
set2 = {4, 5, 6, 7, 8, 9}
set1.difference(set2)

{1, 2, 3}

Symmetric difference of two sets

1
2
3
set1 = {1, 2, 3, 4, 5, 6}
set2 = {4, 5, 6, 7, 8, 9}
set1.symmetric_difference(set2)

{1, 2, 3, 7, 8, 9}

are all set1 elements present in set2?

1
2
3
set1 = {1, 2, 3}
set2 = {3, 4, 5}
set1.issubset(set2)

False

are all set2 elements present in set1?

1
2
3
set1 = {1, 2, 3}
set2 = {3, 4, 5}
set1.issuperset(set2)

False