HashSet\<T> in C#
What it is and how it works "under the hood"
HashSet<T> is a collection holding unique elements, based on a hash table - exactly the same mechanism as Dictionary<K,V>, just without values, only keys.
var uniqueIds = new HashSet<int>();
uniqueIds.Add(1); // true - dodano
uniqueIds.Add(2); // true - dodano
uniqueIds.Add(1); // false - it ALREADY EXISTS, the duplicate was not added
Console.WriteLine(uniqueIds.Count); // 2, nie 3
How hashing works - why O(1)
public class Order
{
public int Id { get; set; }
public override int GetHashCode() => Id.GetHashCode(); // KLUCZOWE dla HashSet<Order>
public override bool Equals(object obj) => obj is Order o && o.Id == Id;
}
When you call hashSet.Add(order), HashSet<T> calls GetHashCode() on the object to calculate which "bucket" of the internal array the element should go to. Checking "does the element already exist" consists of: computing the hash (O(1)), finding the right bucket (O(1)), and comparing (Equals) with the elements in that one bucket (usually 0-1 elements, not the whole collection) - hence on average O(1), as opposed to List<T>.Contains(), which has to search all the elements linearly, O(n).
This ties directly back to the earlier conversation about Equals/GetHashCode - if you override Equals without GetHashCode, HashSet<T> will work incorrectly (two "logically equal" objects may land in different buckets and the HashSet will treat them as different elements), exactly as I described in that example.
Set operations - mathematical set theory in practice
var setA = new HashSet<int> { 1, 2, 3, 4 };
var setB = new HashSet<int> { 3, 4, 5, 6 };
var union = new HashSet<int>(setA);
union.UnionWith(setB); // {1,2,3,4,5,6} - the union of the sets
var intersection = new HashSet<int>(setA);
intersection.IntersectWith(setB); // {3,4} - the intersection (the COMMON elements)
var difference = new HashSet<int>(setA);
difference.ExceptWith(setB); // {1,2} - the difference (elements ONLY in A)
var symmetricDiff = new HashSet<int>(setA);
symmetricDiff.SymmetricExceptWith(setB); // {1,2,5,6} - elementy w A LUB B, ale NIE w obu
Practical use #1 - eliminating duplicates
List<int> withDuplicates = new() { 1, 2, 2, 3, 3, 3, 4 };
var unique = new HashSet<int>(withDuplicates); // {1, 2, 3, 4}
// Alternatively through LINQ (internally it also uses a HashSet)
var uniqueLinq = withDuplicates.Distinct().ToList();
Practical use #2 - fast membership checks (a direct tie to Big-O)
// ❌ O(n) for EVERY check - with a large list, very expensive in a loop
List<int> blockedUserIds = GetBlockedUserIds(); // say, 10 000 elements
foreach (var user in allUsers) // 100 000 elements
{
if (blockedUserIds.Contains(user.Id)) // O(n) - SEARCHES the list linearly!
{
// ...
}
} // Overall: O(n * m) = 100 000 * 10 000 = 1 BILLION operations!
// ✅ O(1) per sprawdzenie
HashSet<int> blockedUserIds = GetBlockedUserIds().ToHashSet(); // JEDNORAZOWA konwersja O(m)
foreach (var user in allUsers) // 100 000 elements
{
if (blockedUserIds.Contains(user.Id)) // O(1) - natychmiastowe sprawdzenie!
{
// ...
}
} // Overall: O(n + m) = 110 000 operations
This is exactly the same optimisation pattern I mentioned with Big-O and Dictionary - HashSet<T> is the natural choice when you care only about "does the element exist", with no need to store an additional value associated with the key (that is what Dictionary<K,V> is for).
HashSet<T> vs Dictionary<K,V> - which one when
HashSet<T> |
Dictionary<K,V> |
|
|---|---|---|
| Stores | Only elements (keys) | Key-value pairs |
| When to use | "Does X exist in the set?" | "What value corresponds to key X?" |
| Example | A set of blocked IDs, unique tags | Mapping ID → object, a cache |
A custom IEqualityComparer<T> - non-standard comparison logic
public class OrderByIdComparer : IEqualityComparer<Order>
{
public bool Equals(Order x, Order y) => x?.Id == y?.Id;
public int GetHashCode(Order obj) => obj.Id.GetHashCode();
}
var orders = new HashSet<Order>(new OrderByIdComparer()); // comparison ONLY by Id, regardless of Equals on Order
This is exactly the IEqualityComparer<T> mechanism we discussed when comparing record/class - it works identically with HashSet<T> as with any other collection.
Summary
HashSet<T>is a hash-table-based structure giving on average O(1) for adding, removing and checking membership - as opposed toList<T>.Contains(), which is O(n). The key condition for correct operation is a consistent implementation ofEquals/GetHashCodeon the stored type (or providing your ownIEqualityComparer<T>). The most common practical uses are eliminating duplicates and fast membership checks in a loop, which turnsO(n*m)complexity intoO(n+m)- one of the most practical, "free" performance improvements you can introduce into code.