Sets as collections of unique items, hash vs tree-based sets, set algebra (union, intersection, difference), frozen and immutable variants, and common performance wins over List.Contains.
A set stores unique items and answers "is X in it?" quickly.
HashSet<T>: hash table without values. Add, Remove, Contains are O(1) average. No ordering.SortedSet<T>: red-black tree. O(log n) operations, items kept sorted, supports Min, Max and GetViewBetween ranges.FrozenSet<T> (.NET 8+): built once, optimised for fast reads; immutable.ImmutableHashSet<T>: immutable with cheap "modified copies", for snapshot-style sharing.Set algebra: UnionWith, IntersectWith, ExceptWith, SymmetricExceptWith, IsSubsetOf, Overlaps, SetEquals. The biggest everyday win is replacing List.Contains (O(n)) in loops with HashSet.Contains (O(1)).
| Type | Structure | Contains/Add | Ordered | Mutable | Thread-safe reads with writers | Use when |
|---|---|---|---|---|---|---|
HashSet<T> |
Hash table | O(1) average | No | Yes | No | General membership and dedup |
SortedSet<T> |
Red-black tree | O(log n) | Yes | Yes | No | Need order, ranges, min/max |
FrozenSet<T> |
Read-optimised hash, layout chosen from the keys at build time | O(1), fastest reads | No | No | Yes (never changes) | Built once at startup, read millions of times |
ImmutableHashSet<T> |
Balanced (AVL) tree of hash buckets | O(log n) | No | No (returns new sets) | Yes (snapshots) | Shared snapshots, functional updates |
A = {1, 2, 3, 4} B = {3, 4, 5}
A ∪ B UnionWith {1, 2, 3, 4, 5}
A ∩ B IntersectWith {3, 4}
A ∖ B ExceptWith {1, 2}
A △ B SymmetricExceptWith {1, 2, 5}
The HashSet<T> methods modify the set in place. LINQ's Union, Intersect, Except and Distinct return new sequences and use hash sets internally.
A notification job had to skip users who had unsubscribed. It loaded 300,000 unsubscribed IDs into a List<Guid> and called unsubscribed.Contains(user.Id) for each of 2 million users. That is up to 600 billion comparisons, and the job ran for hours. Changing to HashSet<Guid> made each check O(1): the job finished in under a minute. Later the ID list was loaded at startup into a FrozenSet<Guid> since it changed only nightly.
Checks practical collection choice and awareness of modern .NET options.
Green flags
HashSet<T> is O(1) average and unordered, while SortedSet<T> is O(log n) and ordered.FrozenSet<T>, ImmutableHashSet<T>, bounded dedup.Red flags
List<T>.Contains in loops without concern.HashSet<T> is ordered.HashSet<T>Same design as Dictionary<TKey, TValue> without the value: a buckets array plus an entries array with chain indices. Same Equals/GetHashCode contract and comparer support:
var tags = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
Add returns false if the item already exists, which is handy for dedup while streaming. EnsureCapacity and TrimExcess work as they do for Dictionary.
SortedSet<T>A self-balancing red-black tree: every operation is O(log n) and in-order enumeration gives sorted output. GetViewBetween(lower, upper) returns a live view of a range, useful for time windows or ranges of IDs. It needs an IComparer<T> (or IComparable<T> items) instead of hashing.
[20]B
/ \
[10]R [30]R
/ \ / \
[5]B [15]B [25]B [40]B
FrozenSet<T> |
ImmutableHashSet<T> |
|
|---|---|---|
| Creation cost | Higher (analyses keys to pick the fastest layout) | Moderate |
| Read speed | Fastest | Slower than HashSet<T> (tree walk to the bucket) |
| "Modification" | Not supported; rebuild | Add returns a new set sharing most structure |
| Best for | Static lookups (allow-lists, config, routing tables) | Versioned state, snapshots updated occasionally |
None of the mutable sets are thread-safe for writes. Options:
| Pattern | When |
|---|---|
lock around a HashSet<T> |
Low contention, multi-step updates |
ConcurrentDictionary<T, byte> used as a set (TryAdd, ContainsKey, TryRemove) |
Many threads adding and checking |
Build a FrozenSet<T> and swap the reference |
Read-mostly data refreshed on a schedule |
ImmutableHashSet<T> with ImmutableInterlocked.Update |
Frequent small changes, readers need consistent snapshots |
Distinct(), Union(), Intersect(), Except(), plus the ...By variants (DistinctBy, ExceptBy).ids.Contains(x.Id) to SQL; very large lists can hurt query plans, so consider table-valued parameters, a JSON parameter or a temp table.For dense small-integer domains (feature flags 0–255, seat numbers), a BitArray or ulong bitmask uses far less memory and supports set operations with bitwise AND/OR.
List<int>.Contains versus HashSet<int>.Contains versus FrozenSet<int>.Contains for 100,000 items.SortedSet<DateTime>.GetViewBetween to count events in the last 5 minutes.IsSubsetOf to check that a user's requested scopes are within their granted scopes.// Membership checks in a loop: O(1) per check
var unsubscribed = new HashSet<Guid>(await repo.GetUnsubscribedIdsAsync(ct));
foreach (var user in users)
{
if (unsubscribed.Contains(user.Id)) continue;
await notifier.SendAsync(user, ct);
}
// Built once, read many times
private static readonly FrozenSet<string> AllowedCountries =
new[] { "AU", "NZ", "SG", "GB" }.ToFrozenSet(StringComparer.OrdinalIgnoreCase);
// Set algebra for permissions
var granted = new HashSet<string> { "orders:read", "orders:write", "reports:read" };
var requested = new HashSet<string> { "orders:read", "admin" };
if (!requested.IsSubsetOf(granted))
{
var missing = new HashSet<string>(requested);
missing.ExceptWith(granted); // { "admin" }
return Results.Problem($"Missing scopes: {string.Join(", ", missing)}", statusCode: 403);
}
// Dedup while streaming (Add returns false for duplicates)
var seen = new HashSet<string>(StringComparer.Ordinal);
await foreach (var evt in events.WithCancellation(ct))
{
if (!seen.Add(evt.Id)) continue; // duplicate delivery
await HandleAsync(evt, ct);
}
// Ordered set with a range view
var timestamps = new SortedSet<DateTimeOffset>(LoadTimestamps());
var lastFiveMinutes = timestamps.GetViewBetween(DateTimeOffset.UtcNow.AddMinutes(-5), DateTimeOffset.UtcNow);
Console.WriteLine(lastFiveMinutes.Count);
Mistake: Calling List<T>.Contains inside a loop.
Why it is wrong: Each call scans the list, so the loop is O(n × m).
Instead: Build a HashSet<T> once and check membership in O(1).
Mistake: Expecting HashSet<T> to keep insertion or sorted order.
Why it is wrong: It has no ordering guarantee, and order can change after removals and re-adds.
Instead: Use SortedSet<T> for sorted order, or keep a separate list for insertion order.
Mistake: Forgetting the comparer for strings.
Why it is wrong: "AU" and "au" become different items, so dedup and allow-lists silently fail.
Instead: Pass StringComparer.OrdinalIgnoreCase (or the right comparer) when creating the set.
Mistake: Adding to a shared HashSet<T> from several threads.
Why it is wrong: Concurrent inserts corrupt the internal arrays, losing items or throwing.
Instead: Use a lock, ConcurrentDictionary<T, byte>, or swap frozen or immutable snapshots.
Mistake: Using ImmutableHashSet<T> for hot read paths.
Why it is wrong: Its lookups walk a tree and are noticeably slower than HashSet<T>.
Instead: Use FrozenSet<T> for static read-heavy data, and immutable sets when you need cheap versioned copies.
Mistake: Unbounded dedup sets in long-running consumers. Why it is wrong: The set grows forever and eventually exhausts memory. Instead: Bound it (time window, LRU) or dedup in durable storage with expiry.
Sets are the simplest high-impact optimisation in everyday code: replacing an O(n) membership scan in a loop with a hash set routinely turns minutes into milliseconds. Beyond that, I choose the set by access pattern and sharing:
| Access pattern | Choice |
|---|---|
| General mutable work in one thread or request | HashSet<T> |
| Need ordering, ranges or min/max | SortedSet<T> |
| Static data read on hot paths | FrozenSet<T> |
| Shared snapshots that change occasionally | ImmutableHashSet<T> |
| Many threads adding and checking | ConcurrentDictionary<T, byte> |
| Small dense integer domain | Bitmask or BitArray |
I also treat set algebra as a modelling tool (permissions, feature flags, diffs between desired and actual state in reconcilers), which often makes code clearer than nested loops. And for long-running dedup, I always ask how the set is bounded.
A hash table turns a key into an integer hash, maps it to a bucket (hash % bucketCount), and stores the entry there. Lookups compute the same hash, go straight to the bucket, and compare keys with Equals. Average cost is O(1); worst case (everything in one bucket) is O(n).
.NET's Dictionary<TKey,TValue> keeps an int[] buckets and an Entry[] entries array; colliding entries form a chain via a next index inside the entries array. When full, it resizes to roughly double (a prime size) and rehashes.
Contract: if a.Equals(b) then a.GetHashCode() == b.GetHashCode(), and a key's hash must not change while it is in the dictionary. Good hashes spread keys evenly.
A tree is a hierarchy of nodes with one root, where each node has children and no cycles. A binary tree limits each node to two children (left, right). A binary search tree (BST) adds an ordering rule: left subtree < node < right subtree, so search, insert and delete take O(height).
If the tree is balanced, height is O(log n); if you insert sorted data into a plain BST it degenerates into a linked list with O(n) height. Self-balancing trees (red-black, AVL) keep O(log n); .NET's SortedSet and SortedDictionary are red-black trees.
Traversals: in-order (sorted output for a BST), pre-order (copy/serialise), post-order (delete/evaluate), level-order (BFS).
Trees are everywhere: database B+ tree indexes, file systems, JSON/XML/DOM, Roslyn syntax trees, expression trees, org charts.
Main problems:
List<Order> shared across requests: not thread-safe and unbounded (memory leak).Find and Add scan the list: O(n) each, so adding n orders is O(n²). Use a Dictionary<int, Order> (or ConcurrentDictionary).Recent sorts everything and materialises twice for 10 items. Use a size-10 heap, keep orders indexed by time, or query the database with an index.IsBlocked allocates a list per call and is case-sensitive. Use a static readonly FrozenSet<string> with StringComparer.OrdinalIgnoreCase.ProcessPending uses RemoveAt(0) as a queue: O(n²). Use Queue<T> (or Channel<T> if fed concurrently).CountByStatus does two lookups per item. Use CollectionsMarshal.GetValueRefOrAddDefault, TryGetValue, or CountBy (.NET 9).Also question whether an in-process cache belongs here at all (IMemoryCache/HybridCache with size limits and expiry).
Last updated 23 Oct 2026.