Set Data Structure: HashSet, SortedSet, Union, Intersection, and Difference (2026)
A set is an abstract data type that stores unique elements without duplicates. Sets are used for membership testing, deduplication, and set-theoretic operations like union, intersection, and difference. Two common implementations are hash sets (unordered, O(1) average operations) and sorted sets (ordered, O(log n) operations).
This tutorial covers HashSet and TreeSet implementations, set operations, and practical use cases with code in C++, Java, and Python.
HashSet and SortedSet Operations
A HashSet uses a hash table internally and offers O(1) average time for add, remove, and contains. Elements are unordered. C++ unordered_set, Java HashSet, and Python set are hash-based. A SortedSet (or TreeSet) uses a balanced BST (usually Red-Black Tree) and keeps elements in sorted order with O(log n) operations.
Both sets reject duplicate elements. Adding an element that already exists is a no-op. C++ set (ordered) and Java TreeSet provide ordered iteration, ceiling/floor queries, and range views.
// C++
unordered_set hs = {1, 2, 3};
hs.insert(4);
hs.erase(2);
if(hs.count(1)) cout << "found";
// Java
HashSet hs = new HashSet<>();
hs.add(1); hs.add(2);
hs.contains(1); // true
// Python
s = {1, 2, 3}
s.add(4)
s.discard(2)
1 in s # True Union, Intersection, and Difference
Union combines elements from two sets (all elements from both without duplicates). Intersection keeps only elements present in both sets. Difference (set subtraction) keeps elements from the first set that are not in the second. Symmetric difference keeps elements in either set but not both.
Python provides operators: | for union, & for intersection, - for difference, ^ for symmetric difference. C++ provides std::set_union, std::set_intersection, std::set_difference for sorted ranges. Java provides retainAll (intersection), addAll (union), removeAll (difference).
// C++ — set operations (sorted)
set a = {1,2,3}, b = {2,3,4};
vector res;
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res));
// res = {1,2,3,4}
// Java
Set a = new HashSet<>(Arrays.asList(1,2,3));
Set b = new HashSet<>(Arrays.asList(2,3,4));
a.retainAll(b); // intersection -> {2,3}
// Python
a = {1,2,3}; b = {2,3,4}
print(a | b) # {1,2,3,4}
print(a & b) # {2,3}
print(a - b) # {1} Frequently Asked Questions
What is the difference between a set and a list?
Sets store only unique elements and are unordered (hash set) or sorted (tree set). Lists allow duplicates and maintain insertion order.
When should I use a SortedSet over a HashSet?
Use a SortedSet when you need ordered iteration, range queries (e.g., find elements between x and y), or floor/ceiling operations. Use HashSet for faster O(1) lookups.
Originally published on Ayodhyyya. Last updated June 1, 2026.