Authored by Tony Feng

Created on March 27th, 2022

Last Modified on March 27th, 2022

Understanding Sets

Main Concepts

• A Set is an unordered collection data type that is iterable, mutable and has no duplicate elements.
• The major advantage of using a set, as opposed to a list, is that it has a highly optimized method for checking whether a specific element is contained in the set or whether some elements are repeated. This is based on a data structure known as hash table.
• Since sets are unordered, we cannot access items using indexes.

Main Characteristics

• Unordered
• Unchangeable
• Unindexed

Operations

• Search
  • Collision - O(K)
  • No Collision - O(1)
• Insert - O(1)
  • Collision - O(K)
  • No Collision - O(1)
• Delete - O(1)
  • Collision - O(K)
  • No Collision - O(1)

Set Implementation in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# Create a set
s = set()    

# Add an element - O(1)
s.add(2)
s.add(3)
s.add(1)

# Remove an element - O(1)
s.remove(2) 

# Check if the value exists - O(1)
1 in s

# Get the length of the set
len(s)

Set Implementation in Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// Create
HashSet<Integer, String> s = new HashSet<>();

// Add - O(1)
s.add(2);
s.add(3);
s.add(1);

// Remove an element - O(1)
s.remove(1); // arg is the value

// Check if the value exists - O(1)
Boolean check = s.contains(2);

// Get the length of the hash table - O(1)
int len = s.size()

Reference

• GreeksforGreeks - Sets in Python
• 手把手带你刷Leetcode力扣 - 集合 Set
• 手把手带你刷Leetcode力扣 - Python3集合常用操作
• 手把手带你刷Leetcode力扣 - Java集合常用操作