Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 182 ยท Collections

HashSet, SortedSet and Set Operations

Learn C# sets - HashSet and SortedSet, uniqueness, Add returning a bool, union, intersection, difference, subset checks, custom comparers and what each operation costs.

Sometimes the only question you care about is "have I seen this before?" Is this email address already registered? Which words appear in both documents? Which permissions does a user have that the role does not grant? A List<T> can answer all of these, but it answers slowly, because it has to compare your value with its items one by one. A set is a collection built for exactly this kind of question: it holds each value at most once, and it can tell you whether a value is inside in constant time.

.NET has two main sets. HashSet<T> is the fast, unordered one. SortedSet<T> keeps its items in order and is a little slower. Both implement ISet<T>, which adds the classic set operations: union, intersection, difference and subset tests. This lesson covers creating sets, the useful return value of Add, the four set operations, how equality decides what "the same item" means, and what each operation costs. If you have not met lists yet, read List of T first; for key-value storage, see Dictionary.

Uniqueness: a set ignores duplicates

A HashSet<T> stores each distinct value once. Adding a value that is already inside does nothing, and it does not throw. Instead, Add returns a bool: true if the item was new, false if it was already there.

C# Add returns true or false

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

That return value is the idiom for "find the first duplicate" and for "process each item only once". You do not need to call Contains first and Add second, which would hash the value twice.

C# Finding the first duplicate

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Passing a sequence to the constructor adds every item and silently drops repeats. We call Order() (a LINQ method from .NET 7) before printing, for a reason explained next.

A HashSet<T> has no guaranteed order. For int values you will often see insertion order in practice, but that is an implementation detail. For strings the order changes from one program run to the next, because .NET randomizes string hash codes on purpose. If you need a stable output, sort the items before you print them, or use a SortedSet<T>.

How a hash set finds things

You do not need the internals to use a set, but a rough picture explains its speed and its rules. A HashSet<T> keeps an array of "buckets". To add or find a value, it calls GetHashCode() on it, turns that number into a bucket index, and then looks only at the few items in that bucket, comparing them with Equals. That is why Contains, Add and Remove take roughly the same time whether the set holds ten items or ten million: an operation costs O(1) on average.

The same picture gives you the rule that causes the most bugs. Two values that are "equal" must produce the same hash code. For int, string, Guid, enums, records and tuples this is already handled. For your own classes, you decide what equality means, as the next section shows.

Equality decides what "duplicate" means

By default a set compares items with EqualityComparer<T>.Default. For string that means case-sensitive, ordinal comparison. For a plain class it means reference equality: two objects with identical fields are still different items.

C# Reference equality vs value equality

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The class version holds two items because each new Point(...) is a separate object. The record version holds one, because a record generates value-based Equals and GetHashCode for you. Tuples also compare by value. When you want a class to behave well in sets and dictionary keys, override Equals and GetHashCode together, or make it a record. See classes for the basics of objects.

Custom comparers

You do not have to change a type to change how a set compares it. Every set constructor accepts an IEqualityComparer<T>. The most common case is case-insensitive text:

C# A case-insensitive set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Use StringComparer.OrdinalIgnoreCase for identifiers, file extensions and keys. Reserve culture-aware comparers for text shown to people. The set keeps whichever spelling was added first, so "admin" was rejected and "Admin" stays.

The set operations

The real power of sets is combining them. Take two sets, a and b. The operations answer different questions:

Operation Method Result
Union UnionWith Everything in a or b
Intersection IntersectWith Only items in both
Difference ExceptWith Items in a that are not in b
Symmetric difference SymmetricExceptWith Items in exactly one of the two

All four are in-place: they change the set you call them on, and they take any IEnumerable<T> as the argument. Because they mutate, work on a copy when you need to keep the original. A copy constructor does that: new HashSet<int>(a).

C# Union, intersection, difference

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

A collection expression such as [1, 2, 3] can initialize a HashSet<int> directly since C# 12; see collection expressions.

A realistic use: find what changed between two lists of user permissions.

C# What changed between two permission lists

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

LINQ versions that do not mutate

LINQ has Union, Intersect, Except and Distinct, which return new sequences and leave the inputs alone. They use sets internally, so they are also O(n + m). Choose the LINQ version when you want a quick, readable expression, and the HashSet methods when you already hold a set and want to update it. See LINQ basics for more.

Subset and overlap questions

The ISet<T> interface also answers yes/no questions about how two collections relate. They do not change anything.

Method True when
IsSubsetOf(other) every item of this set is in other
IsSupersetOf(other) this set contains every item of other
IsProperSubsetOf(other) subset, and other has at least one extra item
IsProperSupersetOf(other) superset, and this set has at least one extra item
Overlaps(other) at least one item is shared
SetEquals(other) same items, ignoring order and duplicates
C# Subset checks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

SetEquals is the right way to compare "same content" regardless of order. Comparing with == would test whether both variables point at the same object, which is rarely what you mean.

SortedSet: a set that stays in order

SortedSet<T> stores items in a balanced tree (a red-black tree), so it enumerates them in sorted order at all times. It supports everything above, and adds Min, Max, Reverse() and range queries through GetViewBetween.

C# SortedSet keeps items ordered

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The cost is speed: Add, Remove and Contains are O(log n) instead of O(1). For a million items, that is about 20 steps instead of about 1. In exchange you get ordered iteration for free, plus fast "smallest item" and "range" queries. A HashSet can give you sorted output too, but only by sorting at the end, which costs O(n log n) each time you ask.

Note that GetViewBetween returns a view onto the same data. In older .NET versions, calling Count on a view was O(n); treat views as a convenient way to iterate a range, not as a cheap copy.

Costs at a glance

Operation HashSet SortedSet
Add / Remove / Contains O(1) average O(log n)
Enumerate in order not ordered O(n), already sorted
Smallest / largest item O(n) scan O(log n)
UnionWith(other) O(m) O(m log n)
IntersectWith(other) O(n + m) O(n + m) in practice
Memory per item array slot plus hash data tree node with two pointers and a colour

Here n is the size of the set and m the size of the argument. Both sets cost memory for their structure, so for tiny collections (fewer than about ten items) a plain List<T> with Contains can be just as fast.

When to use which

Use HashSet<T> when you need uniqueness or fast membership tests and do not care about order. It is the default choice: visited nodes in a graph search, unique tags, "seen" markers, de-duplication.

Use SortedSet<T> when you need the items ordered, need the minimum or maximum repeatedly, or need range queries.

Avoid a set when you need an index (set[3] does not exist), when duplicates are meaningful (use a list, or a dictionary of counts), or when you need to keep insertion order (use a list plus a set side by side).

Do not mutate a set while you foreach over it. Changing the set during enumeration invalidates the enumerator and throws InvalidOperationException. HashSet<T>.RemoveWhere(predicate) is the safe way to remove many items at once.

C# RemoveWhere and the visited-set pattern

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Without the visited set, the cycle between A and C would loop forever. The stack used here is covered in Stack, Queue, LinkedList and PriorityQueue.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does HashSet<int>.Add(5) return when 5 is already in the set?

    Add never throws for duplicates. It returns false to say nothing was added, which makes it handy for detecting repeats.
  2. 2. Why do two new Point(1, 2) objects of a plain class count as two items in a HashSet?

    The default comparer calls Equals, which for classes means the same object. Records and tuples compare by value instead.
  3. 3. Which call leaves you with the items that are in set a but not in set b?

    ExceptWith removes from a everything that b contains. Note that it changes a, so copy first if you need the original.
  4. 4. What is the main trade-off of SortedSet<T> compared with HashSet<T>?

    A sorted set uses a balanced tree, giving ordered iteration, Min, Max and range views at logarithmic cost per operation.
  5. 5. How should you print the contents of a HashSet<string> so the output is the same on every run?

    A hash set has no guaranteed order, and string hash codes are randomized per process, so sort before printing.

Summary

  • A set stores each value once; HashSet<T>.Add returns false for a repeat.
  • HashSet<T> is unordered with O(1) average Add, Remove and Contains; SortedSet<T> stays ordered at O(log n).
  • Duplicates are decided by the comparer: reference equality for plain classes, value equality for records, tuples and strings (ordinal by default).
  • Pass a comparer such as StringComparer.OrdinalIgnoreCase to change what "the same" means.
  • UnionWith, IntersectWith, ExceptWith and SymmetricExceptWith modify the set in place; copy first to keep the original.
  • IsSubsetOf, IsSupersetOf, Overlaps and SetEquals answer relationship questions without changing anything.
  • Never rely on hash set order; sort before printing.

Next: Stack, Queue, LinkedList and PriorityQueue