How do you use HashSet<T> in C#? Explain Add returning bool, the set operations (UnionWith, IntersectWith, ExceptWith, SetEquals), custom comparers, and why HashSet.Contains beats List.Contains. When would you use SortedSet<T> or FrozenSet<T> instead?

1. Internal structure

HashSet<T> uses the same design as Dictionary<TKey,TValue>, just without values:

private int[] _buckets;      // 1-based index into _entries
private Entry[] _entries;    // { int HashCode; int Next; T Value; }
private int _count, _freeList, _freeCount, _version;
private IEqualityComparer<T>? _comparer;

• Bucket count is a prime; index = hash mod buckets (fast modulo on 64-bit).
• Collisions are chained through Next indexes inside the entries array.
• Removed slots go onto a free list and are reused.
• Resizing doubles to the next prime and rehashes from stored hash codes.

So Add/Contains/Remove are O(1) average, O(n) worst case with pathological hashing.

2. How set operations are implemented

• UnionWith(other): Add each element of other — O(m).
• ExceptWith(other): Remove each element of other — O(m). If other is the same set, clears.
• IntersectWith(other): if other is a HashSet<T> with an equal comparer, iterate this set and remove elements not in other (O(n)); otherwise, build a bit array marking elements found in other, then remove unmarked ones.
• SetEquals(other): with a compatible HashSet, compare counts then check containment; otherwise, may need to build a temporary set.
• IsSubsetOf with compatible sets short-circuits when Count > other.Count.

The "same comparer" fast paths are why it's important to construct sets consistently.

3. SortedSet<T> internals

SortedSet<T> is a red-black tree (a self-balancing binary search tree):

• Each node is a separate heap object (item, left, right, colour) — more memory and less cache-friendly than hash sets.
• Operations are O(log n) with at most a constant number of rotations per insert/delete.
• In-order traversal gives sorted enumeration; Min/Max are O(log n) (walk left/right).
• GetViewBetween(lower, upper) returns a live view over a range, e.g. all timestamps within a window.
• Duplicates (by comparer) are rejected, so a comparer that returns 0 for distinct items (e.g. comparing only by date) silently drops items.

4. FrozenSet<T> internals

ToFrozenSet() analyses the elements and picks an implementation:

• For small sets, a simple array scan may be fastest.
• For integers, a specialised hash or even a bitmap for dense ranges.
• For strings, it can examine lengths and specific character positions to find a cheap discriminating hash (only hashing a few characters instead of the whole string), and may bucket by length so lookups for impossible lengths fail immediately.

Construction can cost much more than building a HashSet, so FrozenSet pays off only when the set is long-lived and looked up frequently. It's immutable and therefore thread-safe.

5. Memory considerations

A HashSet<int> stores, per element, a 12-byte entry (hash, next, value) plus 4 bytes of bucket — roughly 4× the memory of an int[]. A SortedSet<int> uses a ~40-byte node object per element. For tens of millions of integers, consider sorted arrays with BinarySearch, or BitArray for dense ranges.

6. LINQ vs in-place set operations

a.Intersect(b) builds a HashSet from b internally each time you enumerate, and yields distinct elements from a found in it. It doesn't modify anything and is lazy. Use LINQ for one-off expressions on sequences; use HashSet<T> methods when you already have sets or need repeated operations.

Try it yourself

1. Benchmark List.Contains vs HashSet.Contains vs FrozenSet.Contains for sizes 5, 100 and 100,000.
2. Create a SortedSet<Order> with a comparer that compares only CreatedAt and add two orders with the same timestamp.
3. Use GetViewBetween to query a range of dates from a SortedSet<DateTime>.
4. Compare IntersectWith performance with a HashSet argument vs a List argument.

using System.Collections.Frozen;

// De-duplicate and detect duplicates
var seen = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
foreach (var email in incomingEmails)
{
    if (!seen.Add(email))
        Console.WriteLine($"Duplicate: {email}");
}

// Set algebra (in place)
var required = new HashSet<string> { "read", "write", "admin" };
var granted  = new HashSet<string> { "read", "write" };
var missing = new HashSet<string>(required);
missing.ExceptWith(granted);                 // { "admin" }
bool exact = granted.SetEquals(["write", "read", "read"]);  // true

// Get the stored instance back
seen.TryGetValue("[email protected]", out string? original);

// Sorted set with range query
var prices = new SortedSet<decimal> { 9.5m, 20m, 14m, 31m };
var midRange = prices.GetViewBetween(10m, 25m);   // 14, 20

// Built once, read many times
FrozenSet<string> blockedCountries = new[] { "XX", "YY" }.ToFrozenSet();
bool blocked = blockedCountries.Contains(countryCode);