HashSet vs SortedSet in C#: Ordered Sets and Performance

Updated on October 23, 2026

We use HashSet<T> when we only need unique elements and fast lookups, and SortedSet<T> when those elements must stay in sorted order. A HashSet<T> finds an element in constant time but keeps no order, while a SortedSet<T> keeps everything sorted and pays O(log n) per operation.

Our default is HashSet<T>. A SortedSet<T> wins when we read the elements in order again and again, when we need the smallest or largest element, or when we need every element between two values. The two classes live in the same System.Collections.Generic namespace and share most of their methods, so switching later is cheap.

So without further ado, let’s get started!

Does a HashSet Keep Its Elements in Order?

No. A HashSet is a collection of unique elements that uses a hash table for storage, and it keeps neither insertion order nor sorted order. Microsoft’s documentation for HashSet<T> describes a set as a collection “whose elements are in no particular order”.

The order we see when we loop over a HashSet<T> comes from where it happens to store each element. With a handful of numbers and no removals, it often looks like insertion order. That is an accident of the implementation. Nothing guarantees it, and one Remove() followed by an Add() is enough to break it.

If we need the elements sorted, a SortedSet<T> keeps them in ascending order after every insert and removal.

If we need them in the order we added them, .NET 10 has no OrderedSet<T>. The closest built-in type is OrderedDictionary<TKey,TValue>, added in .NET 9, which keeps its keys in insertion order and still finds a key by hash.

Adding and removing elements also has constant time complexity on average, and a HashSet cannot access elements by index. To go into details about this collection, check out our guide to HashSet in C#.

Let’s see the order break with a few integers:

var hashSet = new HashSet<int> { 1, 2, 3, 4, 5 };
hashSet.Remove(2);
hashSet.Add(6);

Console.WriteLine(string.Join(", ", hashSet));

var sortedSet = new SortedSet<int> { 5, 1, 4, 2, 3 };
sortedSet.Remove(2);
sortedSet.Add(6);

Console.WriteLine(string.Join(", ", sortedSet));

Here, the HashSet<int> puts the new 6 into the slot that 2 left behind, so it prints in the middle. The SortedSet<int> received its numbers out of order and still prints them sorted:

1, 6, 3, 4, 5
1, 3, 4, 5, 6

We should never write code that depends on the first line. A different .NET version or a few more removals can change it, and that is exactly what “no particular order” allows.

When we need insertion order, OrderedDictionary<TKey,TValue> can stand in for an ordered set. We use the elements as keys and ignore the values:

var visited = new OrderedDictionary<string, bool>();
visited.TryAdd("home", true);
visited.TryAdd("pricing", true);
visited.TryAdd("home", true);
visited.TryAdd("docs", true);

Console.WriteLine(string.Join(", ", visited.Keys));

The second TryAdd("home", true) returns false and changes nothing, so the keys keep the order of their first visit:

home, pricing, docs

Is a SortedSet Just a Sorted HashSet?

Almost, but not quite. A SortedSet<T> is a collection of unique elements sorted according to their natural ordering or a specified comparer. Like HashSet<T>, it implements ISet<T>, so the two share Add(), Contains(), Remove() and the set operations.

The storage is different. Instead of a hash table, a SortedSet<T> keeps its elements in a red-black tree, a binary search tree that rebalances itself on every insert and removal. That keeps the tree shallow, so a lookup takes O(log n) steps instead of the constant time a HashSet<T> needs.

The test for a duplicate is different too, and this is the part that surprises people. A HashSet<T> asks Equals() and GetHashCode(). A SortedSet<T> asks only its comparer, and an element that compares as equal to one already in the set counts as a duplicate, even when all its other properties differ.

Let’s see that comparer rule in action. We sort a few books by the year they came out, with the Book record in its own file:

public record Book(string Title, int Year);

var byYear = Comparer<Book>.Create((a, b) => a.Year.CompareTo(b.Year));

var sortedBooks = new SortedSet<Book>(byYear)
{
    new("Dune", 1965),
    new("The Moon Is a Harsh Mistress", 1966),
    new("Flowers for Algernon", 1966)
};

Console.WriteLine(sortedBooks.Count);

This prints 2. Our comparer says the two 1966 books are equal, so the SortedSet<Book> silently keeps the first one and drops “Flowers for Algernon”. A HashSet<Book> with the same three books keeps all three, because the records differ by Equals(). If we want a sorted set of books by year, the comparer has to break ties, for example by comparing the titles when the years are equal.

A SortedSet does not permit duplicate elements. Trying to add a duplicate element will not affect the set, and Add() returns false. It does accept null for reference types, and the default comparer sorts null before everything else.

To learn more about how SortedSet works, check out our guide to SortedSet in C#.

What Do HashSet and SortedSet Have in Common?

HashSet<T> and SortedSet<T> objects store unique elements because they implement the ISet<T> interface. Since .NET 5, both also implement IReadOnlySet<T>, so a method that only reads a set can accept either one.

Both data structures find an element much faster than lists and arrays do. List<T>.Contains() checks the elements one by one, which makes it an O(N) operation, while both sets skip almost all of that work.

What Are the Differences Between HashSet and SortedSet?

HashSet<T> and SortedSet<T> objects use different data structures to store data, and almost every other difference follows from that one choice.

The HashSet<T> class uses a hash table to organize its elements. That makes Contains(), Add() and Remove() constant time on average, but the elements come back in no particular order.

A SortedSet<T> class uses a balanced binary tree to maintain elements in a specific order. The same three operations cost O(log n), so it has slower retrieval operations than a HashSet<T>. In return, the elements are always sorted, and reading them in order costs nothing extra.

The two also disagree on what a duplicate is. A HashSet<T> uses Equals() and GetHashCode(), or an IEqualityComparer<T> we pass in. A SortedSet<T> uses an IComparer<T>.

Neither class has an indexer, so set[0] does not compile on either one. When position matters, we copy the elements into a List<T> first.

A SortedSet<T> can retrieve a subset of elements within a specific range using the SortedSet<T>.GetViewBetween(T, T) method, which is not available in the HashSet<T> class. The result is a live view, not a copy, so changes to the view show up in the original set and the other way round.

Additionally, SortedSet<T> allows us to retrieve the minimum and maximum elements through its SortedSet<T>.Max and  SortedSet<T>.Min properties, while the HashSet<T> class lacks them. It gets that order from its Comparer property, an IComparer<T> that we can pass to the constructor or leave as the default for T.

Let’s analyze how HashSet and SortedSet objects perform theoretically and then use benchmarks to test those theories.

What Is the Time Complexity of HashSet and SortedSet?

Big O analysis is a way of determining the efficiency and complexity of how an algorithm performs. For a HashSet<T>, the numbers below are the usual case. A type with a poor GetHashCode() puts many elements into the same bucket, and then a lookup slows down toward O(N).

So, how do HashSet and SortedSet objects perform?

We can use Big O analysis to assess how the data structures perform when handling crucial CRUD operations:

HashSet<T> and SortedSet<T> classes scale the same way when iterating through elements, as the operation depends on the input size, hence, has a performance of O(N).

Additionally, the HashSet<T> is faster than a SortedSet<T> when searching elements, as it has a constant time lookup performance of O(1), while the latter has O(log N) performance. Each step down the tree roughly halves what is left to search, so it never walks the elements one by one. Microsoft’s SortedSet<T>.Contains() reference says: “This method is an O(log n) operation.”

When adding or removing elements, the HashSet<T> class performs better than the SortedSet<T> class. The HashSet<T> class uses a hash table to organize its elements; inserting an element is an O(1) operation on average. When the set outgrows its internal array, that one Add() has to copy everything, which costs O(N). On the other hand, the SortedSet<T> uses a red-black tree, a binary search tree with at most a left and a right child on every node, which rebalances itself as it grows. Since the SortedSet<T> class ensures that the elements are in the correct order, every insertion operation places the new element in the correct location in the set, making it an O(log N) operation.

The HashSet<T> class only falls behind when we need its elements in sorted order. Enumerating them is O(N), like any collection, but they come out in no particular order, so we have to copy them and sort the copy, which takes O(N log N) time. On the other hand, the elements in the SortedSet<T> objects are already in the correct order, so reading them sorted takes O(N) time.

How Do HashSet and SortedSet Perform in Benchmarks?

We measure both classes with BenchmarkDotNet, one million random integers, and the same operations on each. All of the benchmark code goes into an Operations class in its own console project. We add the BenchmarkDotNet package to it, start the class file with using BenchmarkDotNet.Attributes;, mark the class with [MemoryDiagnoser], and call BenchmarkRunner.Run<Operations>(); from its Program.cs, after using BenchmarkDotNet.Running;. We run it with dotnet run -c Release. First, let’s implement a function that returns a list of integers. We are going to use it to initialize our SortedSet and HashSet objects:

private static List<int> RandomInts(int size)
{
    var rand = new Random();
    List<int> numbers = [];

    for (int i = 0; i < size - 1; i++)
    {
        numbers.Add(rand.Next());
    }

    numbers.Add(int.MaxValue - 1);

    return numbers;
}

Our RandomInts() method takes the number of integers to generate as its sole input. It uses the inbuilt Random class to generate random numbers and inserts each value into a List<int> object before returning it. Also, we add the integer int.MaxValue - 1, which we are going to use later. 

Next, let’s initialize our SortedSet and HashSet objects by using our RandomInts() method:

private readonly List<int> _numList;
private readonly HashSet<int> _hashSet;
private readonly SortedSet<int> _sortedSet;
private readonly int _searchValue;

public Operations()
{
    _numList = RandomInts(1000000);
    _hashSet = InitializeIntHashSet();
    _sortedSet = InitializeIntSortedSet();
    _searchValue = int.MaxValue - 1;
}

[Benchmark]
public HashSet<int> InitializeIntHashSet() 
{
    var hashSet = new HashSet<int>();

    foreach (var number in _numList) 
    {
        hashSet.Add(number);
    }

    return hashSet;
}

[Benchmark]
public SortedSet<int> InitializeIntSortedSet()
{
    var sortedSet = new SortedSet<int>();

    foreach (var number in _numList)
    {
        sortedSet.Add(number);
    }

    return sortedSet;
}

Here, we populate the HashSet<int> and SortedSet<int> objects with one million integers, which covers the iteration and insertion of elements operations. However, we must remember that these data structures hold unique elements; hence, the objects may have fewer values if _numList contains duplicates. 

Search and Remove Elements From the HashSet and SortedSet

Let’s check whether an element exists in our SortedSet and HashSet objects by invoking the Contains() method:

[Benchmark]
public bool SearchSortedSet()
{
    return _sortedSet.Contains(_searchValue);
}

[Benchmark]
public bool SearchHashSet()
{
    return _hashSet.Contains(_searchValue);
}

We expect these methods to return true as _searchValue is present in our SortedSet and HashSet objects.

Next, let’s implement functions to remove elements by invoking the Remove() method:

[Benchmark]
public HashSet<int> RemoveElementFromHashSet()
{
    _hashSet.Remove(_searchValue);

    return _hashSet;
}

[Benchmark]
public SortedSet<int> RemoveElementFromSortedSet()
{
    _sortedSet.Remove(_searchValue);

    return _sortedSet;
}

After the first call, _searchValue is gone, so every later call in the benchmark is a Remove() that finds nothing to remove. That still measures the expensive part, finding the element’s slot or tree node, and Remove() simply returns false instead of throwing.

Both the HashSet<T> and SortedSet<T> classes support the RemoveWhere(Predicate<T>) method. It has the same problem as Remove(), only worse: once the first call removes every odd number, the next calls have nothing left to remove. So we give each RemoveWhere() run a fresh copy of both sets:

private HashSet<int> _hashSetCopy = [];
private SortedSet<int> _sortedSetCopy = [];

[IterationSetup(Targets = [nameof(RemoveWhereFromHashSet), nameof(RemoveWhereFromSortedSet)])]
public void CopySets()
{
    _hashSetCopy = new HashSet<int>(_hashSet);
    _sortedSetCopy = new SortedSet<int>(_sortedSet);
}

[Benchmark]
public HashSet<int> RemoveWhereFromHashSet()
{
    _hashSetCopy.RemoveWhere(IsOdd);

    return _hashSetCopy;
}

[Benchmark]
public SortedSet<int> RemoveWhereFromSortedSet()
{
    _sortedSetCopy.RemoveWhere(IsOdd);

    return _sortedSetCopy;
}

private static bool IsOdd(int num)
{
    return num % 2 == 1;
}

The [IterationSetup] method runs before every iteration of the two benchmarks it targets, and BenchmarkDotNet leaves it out of the measurement. Now each RemoveWhere() call really removes about half a million numbers.

We use the IsOdd() method as our predicate for the RemoveWhere() method, which removes all the odd numbers from both objects. 

How to Get the Elements in Sorted Order

Sometimes, we need to sort the elements in our SortedSet or HashSet objects in a specific order:

[Benchmark]
public List<int> SortHashSetElements()
{
    return _hashSet.Order().ToList();
}

[Benchmark]
public List<int> SortSortedSetElements()
{
    return _sortedSet.ToList();
}

Since the elements in the _sortedSet are in the correct order, we invoke the ToList() method to enumerate them.

But, for _hashSet, we use the LINQ Order() method, added in .NET 7, to sort the elements in ascending order.

Alternatively, we can convert the _hashSet object into different collections, such as arrays, before sorting them:

var array = _hashSet.ToArray();
Array.Sort(array);

Performance Results

Finally, let’s assess how the SortedSet and HashSet objects perform when performing our CRUD operations:

| Method                     | Job        | InvocationCount | UnrollFactor | Mean               | Error              | StdDev             | Median             | Rank | Gen0      | Gen1      | Gen2     | Allocated  |
|--------------------------- |----------- |---------------- |------------- |-------------------:|-------------------:|-------------------:|-------------------:|-----:|----------:|----------:|---------:|-----------:|
| InitializeIntHashSet       | DefaultJob | Default         | 16           |  33,834,386.662 ns |    887,449.0717 ns |  2,574,650.8602 ns |  33,349,212.500 ns |    1 |  312.5000 |  312.5000 | 312.5000 | 43111111 B |
|                            |            |                 |              |                    |                    |                    |                    |      |           |           |          |            |
| InitializeIntSortedSet     | DefaultJob | Default         | 16           | 457,855,137.113 ns | 12,734,747.2173 ns | 36,945,813.4812 ns | 443,437,300.000 ns |    1 | 4000.0000 | 3000.0000 |        - | 39990888 B |
|                            |            |                 |              |                    |                    |                    |                    |      |           |           |          |            |
| RemoveElementFromHashSet   | DefaultJob | Default         | 16           |           3.975 ns |          0.0930 ns |          0.0824 ns |           3.953 ns |    1 |         - |         - |        - |          - |
|                            |            |                 |              |                    |                    |                    |                    |      |           |           |          |            |
| RemoveElementFromSortedSet | DefaultJob | Default         | 16           |          51.668 ns |          1.0229 ns |          1.0944 ns |          52.066 ns |    1 |         - |         - |        - |          - |
|                            |            |                 |              |                    |                    |                    |                    |      |           |           |          |            |
| RemoveWhereFromHashSet     | Job-CNUJVU | 1               | 1            |  31,648,009.091 ns |  2,516,730.5907 ns |  7,381,135.6965 ns |  29,238,600.000 ns |    1 |         - |         - |        - |          - |
|                            |            |                 |              |                    |                    |                    |                    |      |           |           |          |            |
| RemoveWhereFromSortedSet   | Job-CNUJVU | 1               | 1            | 124,515,219.231 ns |  2,378,048.1318 ns |  4,164,959.8039 ns | 124,039,450.000 ns |    1 |         - |         - |        - |  8193792 B |
|                            |            |                 |              |                    |                    |                    |                    |      |           |           |          |            |
| SearchSortedSet            | DefaultJob | Default         | 16           |          22.594 ns |          0.3421 ns |          0.3033 ns |          22.549 ns |    1 |         - |         - |        - |          - |
|                            |            |                 |              |                    |                    |                    |                    |      |           |           |          |            |
| SearchHashSet              | DefaultJob | Default         | 16           |           4.261 ns |          0.1187 ns |          0.1413 ns |           4.244 ns |    1 |         - |         - |        - |          - |
|                            |            |                 |              |                    |                    |                    |                    |      |           |           |          |            |
| SortHashSetElements        | DefaultJob | Default         | 16           |  65,221,413.393 ns |    697,473.2408 ns |    618,291.8611 ns |  65,102,493.750 ns |    1 |         - |         - |        - |  3999208 B |
|                            |            |                 |              |                    |                    |                    |                    |      |           |           |          |            |
| SortSortedSetElements      | DefaultJob | Default         | 16           |  52,079,154.106 ns |  1,030,397.1552 ns |  1,985,225.6556 ns |  51,913,044.444 ns |    1 |         - |         - |        - |  3999600 B |

We can see that the HashSet<T> class is faster than the SortedSet<T> classes in search, addition, and data removal processes. The HashSet<T> class performs better in these operations since it uses a hash table instead of a binary tree in a SortedSet<T> object as its underlying data structure. 

The RemoveWhere() pair shows the other cost of the tree. SortedSet<T>.RemoveWhere() first walks the whole tree through a queue of its nodes and copies every match into a List<T>, created with room for the entire set, and only then removes the matches one by one. HashSet<T>.RemoveWhere() removes in place and allocates nothing.

Although the test results show the SortedSet<T> class performs better than the HashSet<T> class when enumerating elements in sorted order, we should remember that the sorting process takes place when initializing the SortedSet<T>, which is slower than initializing the HashSet<T> class. Therefore, to sort elements in the SortedSet<T> object, we simply convert it into a List<T>, while in the HashSet<T> object, we have to order the elements before adding them into a List<T>. 

Should We Use a HashSet or a SortedSet?

Most of the time, the answer is a HashSet<T>. Here is when that changes:

If none of these rows fits, we probably need neither set. Duplicates allowed and position matters is a List<T>, and key-value pairs in key order is a sorted dictionary.

Conclusion

So, in this article, we learned the similarities and differences between the HashSet<T> and SortedSet<T> classes in C#, and what to use when we need an ordered set.

The HashSet<T> class is the way to go if we need to store unique elements and not care about their order. However, the SortedSet<T> class is our best bet for sorting unique data while adding elements. 

These collections have different performance characteristics depending on how we intend to use them. The HashSet<T> class is generally faster for lookup operations, while the SortedSet<T> class has better sorted enumeration performance.

Tested with .NET 10.0.10 (SDK 10.0.302), BenchmarkDotNet 0.15.8 and MSTest 4.5.1.