C# HashSet vs SortedSet: Choosing the Right Collection

When you need to store unique elements in C#, two collection types come to mind: HashSet<T> and SortedSet<T>. Both prevent duplicates, but they differ fundamentally in how they store and retrieve data. This article compares c# hashset vs sortedset to help you decide which one fits your scenario.

The Core Difference: Hashing vs. Ordering

The most important distinction is that HashSet<T> uses a hash table internally, while SortedSet<T> uses a balanced binary search tree (typically a red-black tree). This leads to two different behaviors:

• HashSet<T> does not preserve any order. Elements are stored based on their hash codes, so iteration order is unpredictable and can change when the set is modified.
• SortedSet<T> maintains elements in sorted order according to a comparer. The default comparer for numeric types sorts ascending, but you can supply a custom IComparer<T> to define your own ordering.

Both implement ISet<T>, so they support set operations like UnionWith, IntersectWith, and ExceptWith. The choice between them depends on whether ordering matters and what performance characteristics you need.

Lookup and Insertion Performance

The algorithmic complexity of common operations differs significantly:

• HashSet<T> offers average-case O(1) time for Add, Contains, and Remove. This is because hash-based lookup computes the bucket directly from the element's hash code.
• SortedSet<T> offers O(log n) time for the same operations. The tree structure requires traversing from the root to maintain sorted order.

In practice, for large collections where membership checks are frequent and ordering is irrelevant, HashSet<T> is usually faster. However, the constant factors matter: hash computation and collision handling can add overhead, while tree operations involve pointer chasing. If you only need to insert and iterate in sorted order, SortedSet<T> may be more efficient than repeatedly sorting a HashSet<T>.

Memory and Allocation Behavior

Memory usage also differs. HashSet<T> allocates an array of buckets and stores elements in linked lists or arrays within those buckets. The capacity grows as elements are added, and the internal array is resized when the load factor exceeds a threshold. This can cause occasional reallocation and copying.

SortedSet<T> allocates a node for each element, with each node containing the value plus references to left and right children and the parent. This per-node overhead is higher than a simple array slot, but there is no need for resizing or rehashing. For very large collections, the tree may use more memory per element, but it avoids the wasted space of hash table buckets.

If memory is a concern and you need predictable allocation, SortedSet<T> might be preferable. If you need to minimize per-element overhead and don't care about order, HashSet<T> is often more compact.

When to Use HashSet<T>

Use HashSet<T> when:

• You only need to test membership or eliminate duplicates.
• The order of elements is irrelevant.
• You perform frequent Contains calls and want average O(1) lookup.
• You need to perform set operations like union, intersection, or difference.

Typical scenarios include caching unique IDs, validating that a list contains no duplicates, or tracking seen items during graph traversal. For example, checking whether a user ID already exists in a collection is faster with HashSet<T> than with a List<T> or SortedSet<T> when the collection is large.

When to Use SortedSet<T>

Use SortedSet<T> when:

• You need elements to remain sorted at all times.
• You want to retrieve the minimum or maximum element efficiently (Min and Max properties).
• You need range queries, such as getting all elements between two values using GetViewBetween.
• You want to avoid the cost of sorting a HashSet<T> after each modification.

A common use case is a leaderboard or a sorted list of unique scores. If you frequently need the top N items, SortedSet<T> provides them in order without an explicit sort. Another example is a priority queue where you need the lowest-priority item first, though SortedSet<T> is not a full priority queue because it doesn't support duplicate keys.

Code Example: Basic Usage and Iteration

The following code demonstrates the difference in iteration order:

using System;
using System.Collections.Generic;

var numbers = new[] { 5, 1, 3, 2, 4 };

var hashSet = new HashSet<int>(numbers);
var sortedSet = new SortedSet<int>(numbers);

Console.WriteLine("HashSet iteration:");
foreach (var n in hashSet)
{
    Console.Write(n + " ");
}

Console.WriteLine("\nSortedSet iteration:");
foreach (var n in sortedSet)
{
    Console.Write(n + " ");
}

The HashSet output order is not guaranteed; it may vary between runs and .NET versions. The SortedSet always outputs 1 2 3 4 5. If your application relies on stable ordering, SortedSet is the correct choice.

Handling Custom Types and Comparers

Both collections rely on equality or comparison logic. For HashSet<T>, you must ensure that GetHashCode and Equals are properly implemented, or you can pass an IEqualityComparer<T> to the constructor. For SortedSet<T>, you need an IComparer<T> that defines a total order.

Consider a Person class with Name and Age properties. To use HashSet<Person> with value equality, you would override Equals and GetHashCode. To use SortedSet<Person> sorted by age, you would implement IComparer<Person>:

public class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
}

public class AgeComparer : IComparer<Person>
{
    public int Compare(Person x, Person y)
    {
        return x.Age.CompareTo(y.Age);
    }
}

var people = new SortedSet<Person>(new AgeComparer());
people.Add(new Person { Name = "Alice", Age = 30 });
people.Add(new Person { Name = "Bob", Age = 25 });

If you omit the comparer, SortedSet<Person> will use the default comparer, which requires Person to implement IComparable<Person>. Similarly, HashSet<Person> without an equality comparer uses the default EqualityComparer<Person>.Default, which calls GetHashCode and Equals. Getting these details wrong can lead to unexpected duplicate elements or incorrect ordering.

Concurrency and Thread Safety

Neither HashSet<T> nor SortedSet<T> is thread-safe for concurrent reads and writes. If multiple threads modify the collection without synchronization, you risk corruption or exceptions. For read-only access, both are safe as long as no writes occur.

If you need concurrent operations, consider using ConcurrentDictionary<TKey, TValue> with dummy values to simulate a set, or use locking around the collection. The .NET ConcurrentBag<T> allows duplicates, so it is not a direct replacement. For a sorted concurrent set, you may need to implement your own synchronization or use third-party libraries. This is a significant consideration in multi-threaded applications.

Decision Criteria: A Practical Guide

The table below summarizes the key differences to help you choose:

Choose HashSet<T> when your primary need is fast lookup and you do not care about order. Choose SortedSet<T> when you need sorted data, range queries, or frequent min/max retrieval. In scenarios where you need both fast lookup and sorted order, you might consider maintaining a Dictionary<TKey, TValue> alongside a SortedSet<T>, but that adds complexity. The right choice depends on the specific operations your application performs most often.