C# / .NET Compendium PLEN
.NET / C# / Algorithms, data structures

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 to List<T>.Contains(), which is O(n). The key condition for correct operation is a consistent implementation of Equals/GetHashCode on the stored type (or providing your own IEqualityComparer<T>). The most common practical uses are eliminating duplicates and fast membership checks in a loop, which turns O(n*m) complexity into O(n+m) - one of the most practical, "free" performance improvements you can introduce into code.

Buy me a coffee